×

A comparative study of solution representations for the unrelated machines environment. (English) Zbl 1458.90366

Summary: Scheduling problems are quite difficult to solve since in many cases no exact algorithms exist which can obtain the optimal solution in a reasonable amount of time. Therefore, these problems are often solved by using various metaheuristic methods, like genetic algorithms. To use these methods, the first step which needs to be performed is to define an encoding scheme that will be used to represent the solutions. Until now, several encoding schemes were proposed for the unrelated machines environment, each of which comes with its own benefits and drawbacks. However, the performance of metaheuristic methods depends on the applied encoding scheme. Unfortunately, no extensive research was performed in the literature to compare different solution representations for the unrelated machines scheduling problem. Therefore, the choice of the solution representation used is mostly provisional and is usually not based on any existing knowledge of how it would perform on the considered problem. This can cause the algorithms to obtain suboptimal results, which can lead to wrong conclusions about the performance. Thus, the goal of this paper is to test seven solution representations that were used in previous studies to represent solutions for the unrelated machines scheduling problem. The selected solution representations were tested for optimising four scheduling criteria, while additionally measuring the execution time of the genetic algorithm when using each of the encodings. The obtained results demonstrate that the encoding which is based on the permutation of jobs obtains the best results, making it the superior encoding scheme for this type of scheduling problem.

MSC:

90B35 Deterministic scheduling theory in operations research
90C59 Approximation methods and heuristics in mathematical programming
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Allahverdi, A.; Gupta, J. N.; Aldowaisan, T., A review of scheduling research involving setup considerations, Omega, 27, 219-239 (1999)
[2] Allahverdi, A.; Ng, C.; Cheng, T.; Kovalyov, M. Y., A survey of scheduling problems with setup times or costs, European Journal of Operational Research, 187, 985-1032 (2008) · Zbl 1137.90474
[3] Baker, K. R.; Trietsch, D., Principles of Sequencing and Scheduling (2013), Wiley
[4] Balin, S., Non-identical parallel machine scheduling using genetic algorithm, Expert Systems with Applications, 38, 6814-6821 (2011)
[5] Bean, J. C., Genetic algorithms and random keys for sequencing and optimization, ORSA Journal on Computing, 6, 154-160 (1994) · Zbl 0807.90060
[6] Behnamian, J.; Zandieh, M.; Fatemi Ghomi, S., Parallel-machine scheduling problems with sequence-dependent setup times using an ACO, SA and VNS hybrid algorithm, Expert Systems with Applications, 36, 9637-9644 (2009)
[7] Branke, J.; Nguyen, S.; Pickardt, C. W.; Zhang, M., Automated design of production scheduling heuristics: a review, IEEE Transactions on Evolutionary Computation, 20, 110-124 (2016)
[8] Braun, T. D.; Siegel, H. J.; Beck, N.; Bölöni, L. L.; Maheswaran, M.; Reuther, A. I.; Robertson, J. P.; Theys, M. D.; Yao, B.; Hensgen, D.; Freund, R. F., A Comparison of eleven static heuristics for mapping a class of independent tasks onto heterogeneous distributed computing systems, Journal of Parallel and Distributed Computing, 61, 810-837 (2001) · Zbl 0990.68013
[9] Carter, A. E.; Ragsdale, C. T., A new approach to solving the multiple traveling salesperson problem using genetic algorithms, European Journal of Operational Research, 175, 246-257 (2006) · Zbl 1137.90690
[10] Chang, P.-C.; Chen, S.-H., Integrating dominance properties with genetic algorithms for parallel machine scheduling problems with setup times, Applied Soft Computing, 11, 1263-1274 (2011)
[11] Chen, B.; Potts, C. N.; Woeginger, G. J., A review of machine scheduling: complexity, algorithms and approximability, (Handbook of Combinatorial Optimization (1998), Springer US), 1493-1641
[12] Chyu, C.-C., & Chang, W.-S. (2010). A competitive evolution strategy memetic algorithm for unrelated parallel machine scheduling to minimize total weighted tardiness and flow time. In The 40th International Conference on Computers & Indutrial Engineering (pp. 1-6). IEEE.
[13] Costa, A.; Cappadonna, F. A.; Fichera, S., A hybrid genetic algorithm for job sequencing and worker allocation in parallel unrelated machines with sequence-dependent setup times, The International Journal of Advanced Manufacturing Technology, 69, 2799-2817 (2013)
[14] Cota, L.P., Haddad, M.N., Souza, M.J.F., Coelho, V.N., 2014. AIRP: a heuristic algorithm for solving the unrelated parallel machine scheduling problem. In: 2014 IEEE Congress on Evolutionary Computation (CEC), IEEE, pp. 1855-1862.
[15] Durasević, M., & Jakobović, D., 2017b. Evolving dispatching rules for optimising many-objective criteria in the unrelated machines environment. Genetic Programming and Evolvable Machines.
[16] Durasević, M., & Jakobović, D., 2016. Comparison of solution representations for scheduling in the unrelated machines environment. In: 2016 39th International Convention on Information and Communication Technology, Electronics and Microelectronics (MIPRO), IEEE, pp. 1336-1342.
[17] Durasević, M., & Jakobović, D., 2017a. Comparison of ensemble learning methods for creating ensembles of dispatching rules for the unrelated machines environment. Genetic Programming and Evolvable Machines.
[18] Durasević, M., & Jakobović, D. (2018). A survey of dispatching rules for the dynamic unrelated machines environment. Expert Systems with Applications.
[19] Durasević, M., Jakobović, D., & Knežević, K., 2016. Adaptive scheduling on unrelated machines with genetic programming. Applied Soft Computing, 48, 419-430.
[20] Eiben, A., & Smith, J. (2015). Introduction to Evolutionary Computing. Natural Computing Series. Springer, Berlin Heidelberg, Berlin, Heidelberg. · Zbl 1327.68003
[21] Fanjul-Peyro, L.; Ruiz, R., Iterated greedy local search methods for unrelated parallel machine scheduling, European Journal of Operational Research, 207, 55-69 (2010) · Zbl 1205.90121
[22] Fanjul-Peyro, L.; Ruiz, R., Size-reduction heuristics for the unrelated parallel machines scheduling problem, Computers & Operations Research, 38, 301-309 (2011)
[23] Fanjul-Peyro, L.; Ruiz, R., Scheduling unrelated parallel machines with optional machines and jobs selection, Computers & Operations Research, 39, 1745-1753 (2012) · Zbl 1251.90141
[24] Glass, C.; Potts, C.; Shade, P., Unrelated parallel machine scheduling using local search, Mathematical and Computer Modelling, 20, 41-52 (1994) · Zbl 0810.90066
[25] Goldberg, D. E., Genetic Algorithms in Search, Optimization and Machine Learning (1989), Addison-Wesley Longman Publishing Co., Inc.: Addison-Wesley Longman Publishing Co., Inc. Boston, MA, USA · Zbl 0721.68056
[26] Graham, R. L.; Lawler, E. L.; Lenstra, J. K.; Kan, A. H.G. R., Optimization and approximation in deterministic sequencing and scheduling: a survey, Annals of Discrete Mathematics, 5, 287-326 (1979) · Zbl 0411.90044
[27] Haddad, M.N., Coelho, I.M., Souza, M.J.F., Ochi, L.S., Santos, H.G., Martins, A.X., 2012. GARP: a new genetic algorithm for the unrelated parallel machine scheduling problem with setup times. In: 2012 31st International Conference of the Chilean Computer Science Society, IEEE, pp. 152-160.
[28] Hart, E.; Ross, P.; Corne, D., Evolutionary scheduling: a review, Genetic Programming and Evolvable Machines, 6, 191-220 (2005)
[29] Hop, N. V.; Nagarur, N. N., The scheduling problem of pcbs for multiple non-identical parallel machines, European Journal of Operational Research, 158, 577-594 (2004) · Zbl 1056.90075
[30] Kim, C. O.; Shin, H. J., Scheduling jobs on parallel machines: a restricted tabu search approach, The International Journal of Advanced Manufacturing Technology, 22, 278-287 (2003)
[31] Kim, D.-W., Kim, K.-H., Jang, W., Chen, F.F., 2002. Unrelated parallel machine scheduling with setup times using simulated annealing. In: 11th International Conference on Flexible Automation and Intelligent Manufacturing Robotics and Computer-Integrated Manufacturing, vol. 18, pp. 223-231.
[32] Kim, D.-W., Na, D.-G., Chen, F.F., 2003. Unrelated parallel machine scheduling with setup times and a total weighted tardiness objective. In: 12th International Conference on Flexible Automation and Intelligent Manufacturing Robotics and Computer-Integrated Manufacturing, vol. 19, pp. 173-181
[33] Lee, J.-H.; Yu, J.-M.; Lee, D.-H., A tabu search algorithm for unrelated parallel machine scheduling with sequence- and machine-dependent setups: minimizing total tardiness, The International Journal of Advanced Manufacturing Technology, 69, 2081-2089 (2013)
[34] Lenstra, J. K.; Shmoys, D. B.; Tardos, E., Approximation algorithms for scheduling unrelated parallel machines, Mathematical Programming, 46, 259-271 (1990) · Zbl 0715.90063
[35] Leung, J. Y.-T., Handbook of Scheduling: Algorithms, Models, and Performance Analysis (2004), Chapman & Hall/CRC: Chapman & Hall/CRC Boca Raton, FL · Zbl 1103.90002
[36] Lin, C.-W.; Lin, Y.-K.; Hsieh, H.-T., Ant colony optimization for unrelated parallel machine scheduling, The International Journal of Advanced Manufacturing Technology, 67, 35-45 (2013)
[37] Logendran, R.; McDonell, B.; Smucker, B., Scheduling unrelated parallel machines with sequence-dependent setups, Computers & Operations Research, 34, 3420-3438 (2007) · Zbl 1127.90032
[38] Maheswaran, M.; Ali, S.; Siegel, H. J.; Hensgen, D.; Freund, R. F., Dynamic mapping of a class of independent tasks onto heterogeneous computing systems, Journal of Parallel and Distributed Computing, 59, 107-131 (1999)
[39] Mitchell, M., An Introduction to Genetic Algorithms (1998), MIT Press: MIT Press Cambridge, MA, USA · Zbl 0906.68113
[40] Morton, T. E.; Pentico, D. W., Heuristic Scheduling Systems (1993), John Wiley And Sons Inc.
[41] de C.M. Nogueira, J.P., Arroyo, J.E.C., Villadiego, H.M.M., Goncalves, L.B., 2014. Hybrid GRASP heuristics to solve an unrelated parallel machine scheduling problem with earliness and tardiness penalties. Electronic Notes in Theoretical Computer Science, 302, 53-72.
[42] Pinedo, M.L., 2012. Scheduling: Theory, Algorithms, and Systems, fourth ed., vol. 9781461423614. Springer, Boston, MA, US. · Zbl 1239.90002
[43] Raja, K.; Arumugam, C.; Selladurai, V., Non-identical parallel-machine scheduling using genetic algorithm and fuzzy logic approach, International Journal of Services and Operations Management, 4, 72-101 (2008)
[44] Rocha, P. L.; Ravetti, M. G.; Mateus, G. R.; Pardalos, P. M., Exact algorithms for a scheduling problem with unrelated parallel machines and sequence and machine-dependent setup times, Computers & Operations Research, 35, 1250-1264 (2008) · Zbl 1169.90010
[45] Srivastava, B., An effective heuristic for minimising makespan on unrelated parallel machines, Journal of the Operational Research Society, 49, 886-894 (1998) · Zbl 1140.90360
[46] Vallada, E.; Ruiz, R., A genetic algorithm for the unrelated parallel machine scheduling problem with sequence dependent setup times, European Journal of Operational Research, 211, 612-622 (2011)
[47] Wang, I.-L.; Wang, Y.-C.; Chen, C.-W., Scheduling unrelated parallel machines in semiconductor manufacturing by problem reduction and local search heuristics, Flexible Services and Manufacturing Journal, 25, 343-366 (2013)
[48] Wotzlaw, A., Scheduling Unrelated Parallel Machines: Algorithms, Complexity, and Performance, AV Akademikerverlag (2012)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.