{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,6]],"date-time":"2026-05-06T02:08:40Z","timestamp":1778033320552,"version":"3.51.4"},"reference-count":37,"publisher":"Springer Science and Business Media LLC","issue":"7","license":[{"start":{"date-parts":[[2022,6,1]],"date-time":"2022-06-01T00:00:00Z","timestamp":1654041600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2022,6,1]],"date-time":"2022-06-01T00:00:00Z","timestamp":1654041600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["J Intell Manuf"],"published-print":{"date-parts":[[2022,10]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>This paper addresses the unrelated parallel machine scheduling problem with sequence and machine dependent setup times and machine eligibility constraints. The objective is to minimize the maximum completion time (makespan). Instances of more than 500 jobs and 50 machines are not uncommon in industry. Such large instances become increasingly challenging to provide high-quality solutions within limited amount of computational time, but so far, have not been adequately addressed in recent literature. A hybrid genetic algorithm is developed, which is lean in the sense that is equipped with a minimal number of parameters and operators, and which is enhanced with an effective local search operator, specifically targeted to solve large instances. For evaluation purposes a new set of larger problems is generated, consisting of up to 800 jobs and 60 machines. An extensive comparative study shows that the proposed method performs significantly better compared to other state-of-the-art algorithms, especially for the new larger instances. Also, it is demonstrated that calibration is crucial and in practice it should be targeted at a narrower set of representative instances.<\/jats:p>","DOI":"10.1007\/s10845-022-01959-4","type":"journal-article","created":{"date-parts":[[2022,6,1]],"date-time":"2022-06-01T13:04:00Z","timestamp":1654088640000},"page":"2059-2073","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":20,"title":["A hybrid genetic algorithm for parallel machine scheduling with setup times"],"prefix":"10.1007","volume":"33","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-6431-5146","authenticated-orcid":false,"given":"J.","family":"Adan","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2022,6,1]]},"reference":[{"issue":"14","key":"1959_CR1","doi-asserted-by":"publisher","first-page":"9545","DOI":"10.1007\/s00500-021-05889-w","volume":"25","author":"MA Al-qaness","year":"2021","unstructured":"Al-qaness, M. A., Ewees, A. A., & Abd Elaziz, M. (2021). Modified whale optimization algorithm for solving unrelated parallel machine scheduling problems. Soft Computing, 25(14), 9545\u20139557.","journal-title":"Soft Computing"},{"issue":"2","key":"1959_CR2","doi-asserted-by":"publisher","first-page":"345","DOI":"10.1016\/j.ejor.2015.04.004","volume":"246","author":"A Allahverdi","year":"2015","unstructured":"Allahverdi, A. (2015). The third comprehensive survey on scheduling problems with setup times\/costs. European Journal of Operational Research, 246(2), 345\u2013378.","journal-title":"European Journal of Operational Research"},{"issue":"3","key":"1959_CR3","doi-asserted-by":"publisher","first-page":"985","DOI":"10.1016\/j.ejor.2006.06.060","volume":"187","author":"A Allahverdi","year":"2008","unstructured":"Allahverdi, A., Ng, C. T., Cheng, T. E., & Kovalyov, M. Y. (2008). A survey of scheduling problems with setup times or costs. European journal of operational research, 187(3), 985\u20131032.","journal-title":"European journal of operational research"},{"issue":"1","key":"1959_CR4","doi-asserted-by":"publisher","first-page":"273","DOI":"10.1007\/s10479-019-03138-w","volume":"285","author":"JP Arnaout","year":"2020","unstructured":"Arnaout, J. P. (2020). A worm optimization algorithm to minimize the makespan on unrelated parallel machines with sequence-dependent setup times. Annals of Operations Research, 285(1), 273\u2013293.","journal-title":"Annals of Operations Research"},{"issue":"6","key":"1959_CR5","doi-asserted-by":"publisher","first-page":"693","DOI":"10.1007\/s10845-009-0246-1","volume":"21","author":"JP Arnaout","year":"2010","unstructured":"Arnaout, J. P., Rabadi, G., & Musa, R. (2010). A two-stage ant colony optimization algorithm to minimize the makespan on unrelated parallel machines with sequence-dependent setup times. Journal of Intelligent Manufacturing, 21(6), 693\u2013701.","journal-title":"Journal of Intelligent Manufacturing"},{"issue":"1","key":"1959_CR6","doi-asserted-by":"publisher","first-page":"43","DOI":"10.1007\/s10845-012-0672-3","volume":"25","author":"JP Arnaout","year":"2014","unstructured":"Arnaout, J. P., Musa, R., & Rabadi, G. (2014). A two-stage ant colony optimization algorithm to minimize the makespan on unrelated parallel machines-part ii: enhancements and experimentations. Journal of Intelligent Manufacturing, 25(1), 43\u201353.","journal-title":"Journal of Intelligent Manufacturing"},{"issue":"9","key":"1959_CR7","doi-asserted-by":"publisher","first-page":"1705","DOI":"10.1007\/s00170-014-6390-6","volume":"76","author":"O Avalos-Rosales","year":"2015","unstructured":"Avalos-Rosales, O., Angel-Bello, F., & Alvarez, A. (2015). Efficient metaheuristic algorithm and re-formulations for the unrelated parallel machine scheduling problem with sequence and machine-dependent setup times. The International Journal of Advanced Manufacturing Technology, 76(9), 1705\u20131718.","journal-title":"The International Journal of Advanced Manufacturing Technology"},{"issue":"2","key":"1959_CR8","first-page":"137","volume":"2","author":"S Binitha","year":"2012","unstructured":"Binitha, S., Sathya, S. S., et al. (2012). A survey of bio inspired optimization algorithms. International journal of soft computing and engineering, 2(2), 137\u2013151.","journal-title":"International journal of soft computing and engineering"},{"issue":"6","key":"1959_CR9","doi-asserted-by":"publisher","first-page":"4135","DOI":"10.1016\/j.asoc.2011.02.032","volume":"11","author":"C Blum","year":"2011","unstructured":"Blum, C., Puchinger, J., Raidl, G. R., & Roli, A. (2011). Hybrid metaheuristics in combinatorial optimization: A survey. Applied Soft Computing, 11(6), 4135\u20134151.","journal-title":"Applied Soft Computing"},{"key":"1959_CR10","doi-asserted-by":"publisher","DOI":"10.1093\/oso\/9780195162929.001.0001","volume-title":"Perspectives on Adaptation in Natural and Artificial Systems","author":"L Booker","year":"2005","unstructured":"Booker, L., Forrest, S., Mitchell, M., & Riolo, R. (2005). Perspectives on Adaptation in Natural and Artificial Systems (Vol. 8). Oxford: Oxford University Press."},{"issue":"1","key":"1959_CR11","doi-asserted-by":"publisher","first-page":"1263","DOI":"10.1016\/j.asoc.2010.03.003","volume":"11","author":"PC Chang","year":"2011","unstructured":"Chang, P. C., & Chen, S. H. (2011). Integrating dominance properties with genetic algorithms for parallel machine scheduling problems with setup times. Applied Soft Computing, 11(1), 1263\u20131274.","journal-title":"Applied Soft Computing"},{"issue":"1","key":"1959_CR12","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/S0377-2217(02)00909-8","volume":"152","author":"TE Cheng","year":"2004","unstructured":"Cheng, T. E., Ding, Q., & Lin, B. M. (2004). A concise survey of scheduling with time-dependent processing times. European Journal of Operational Research, 152(1), 1\u201313.","journal-title":"European Journal of Operational Research"},{"key":"1959_CR13","volume-title":"New Ideas in Optimization","author":"D Corne","year":"1999","unstructured":"Corne, D., Dorigo, M., Glover, F., Dasgupta, D., Moscato, P., Poli, R., & Price, K. V. (1999). New Ideas in Optimization. London, UK: McGraw-Hill Ltd."},{"key":"1959_CR14","doi-asserted-by":"crossref","unstructured":"Cota, L. P., Guimar\u00e3es, F. G., de\u00a0Oliveira, F. B., & Souza, M. J. F. (2017). An adaptive large neighborhood search with learning automata for the unrelated parallel machine scheduling problem. In: 2017 IEEE Congress on Evolutionary Computation (CEC), IEEE, pp 185\u2013192.","DOI":"10.1109\/CEC.2017.7969312"},{"issue":"3","key":"1959_CR15","doi-asserted-by":"publisher","first-page":"809","DOI":"10.1108\/JM2-12-2018-0209","volume":"15","author":"LR de Abreu","year":"2020","unstructured":"de Abreu, L. R., & de Athayde, P. B. (2020). A genetic algorithm with neighborhood search procedures for unrelated parallel machine scheduling problem with sequence-dependent setup times. Journal of Modelling in Management, 15(3), 809\u2013828.","journal-title":"Journal of Modelling in Management"},{"issue":"1","key":"1959_CR16","doi-asserted-by":"publisher","first-page":"19","DOI":"10.1016\/j.swevo.2011.02.001","volume":"1","author":"AE Eiben","year":"2011","unstructured":"Eiben, A. E., & Smit, S. K. (2011). Parameter tuning for configuring and analyzing evolutionary algorithms. Swarm and Evolutionary Computation, 1(1), 19\u201331.","journal-title":"Swarm and Evolutionary Computation"},{"key":"1959_CR17","doi-asserted-by":"publisher","first-page":"285","DOI":"10.1016\/j.apm.2021.01.017","volume":"94","author":"AA Ewees","year":"2021","unstructured":"Ewees, A. A., Al-qaness, M. A., & Abd Elaziz, M. (2021). Enhanced salp swarm algorithm based on firefly algorithm for unrelated parallel machine scheduling with setup times. Applied Mathematical Modelling, 94, 285\u2013305.","journal-title":"Applied Mathematical Modelling"},{"key":"1959_CR18","doi-asserted-by":"publisher","first-page":"54459","DOI":"10.1109\/ACCESS.2018.2872110","volume":"6","author":"AE Ezugwu","year":"2018","unstructured":"Ezugwu, A. E., & Akutsah, F. (2018). An improved firefly algorithm for the unrelated parallel machines scheduling problem with sequence-dependent setup times. IEEE Access, 6, 54459\u201354478.","journal-title":"IEEE Access"},{"issue":"7","key":"1959_CR19","doi-asserted-by":"publisher","first-page":"e0200030","DOI":"10.1371\/journal.pone.0200030","volume":"13","author":"AE Ezugwu","year":"2018","unstructured":"Ezugwu, A. E., Adeleke, O. J., & Viriri, S. (2018). Symbiotic organisms search algorithm for the unrelated parallel machines scheduling with sequence-dependent setup times. PLoS ONE, 13(7), e0200030.","journal-title":"PLoS ONE"},{"key":"1959_CR20","doi-asserted-by":"publisher","first-page":"173","DOI":"10.1016\/j.cor.2018.07.007","volume":"101","author":"L Fanjul-Peyro","year":"2019","unstructured":"Fanjul-Peyro, L., Ruiz, R., & Perea, F. (2019). Reformulations and an exact algorithm for unrelated parallel machine scheduling problems with setup times. Computers & Operations Research, 101, 173\u2013182.","journal-title":"Computers & Operations Research"},{"key":"1959_CR21","volume-title":"Statistical Tables for Biological, Agricultural and Medical Research","author":"RA Fisher","year":"1953","unstructured":"Fisher, R. A., & Yates, F. (1953). Statistical Tables for Biological, Agricultural and Medical Research. New York: Hafner Publishing Company."},{"key":"1959_CR22","volume-title":"Genetic Algorithms in Search, Optimization and Machine Learning","author":"DE Goldberg","year":"1989","unstructured":"Goldberg, D. E. (1989). Genetic Algorithms in Search, Optimization and Machine Learning. Boston: Addison-Wesley Longman Publishing Co., Inc."},{"key":"1959_CR23","doi-asserted-by":"publisher","first-page":"287","DOI":"10.1016\/S0167-5060(08)70356-X","volume":"5","author":"RL Graham","year":"1979","unstructured":"Graham, R. L., Lawler, E. L., Lenstra, J. K., & Kan, A. R. (1979). Optimization and approximation in deterministic sequencing and scheduling: A survey. Annals of Discrete Mathematics, 5, 287\u2013326.","journal-title":"Annals of Discrete Mathematics"},{"key":"1959_CR24","doi-asserted-by":"publisher","DOI":"10.7551\/mitpress\/1090.001.0001","volume-title":"Adaptation in Natural and Artificial Systems: An Introductory Analysis with Applications to Biology, Control, and Artificial Intelligence","author":"JH Holland","year":"1992","unstructured":"Holland, J. H. (1992). Adaptation in Natural and Artificial Systems: An Introductory Analysis with Applications to Biology, Control, and Artificial Intelligence. Cambridge: MIT Press."},{"key":"1959_CR25","doi-asserted-by":"crossref","unstructured":"Jovanovic, R., & Vo\u00df, S. (2021). Fixed set search application for minimizing the makespan on unrelated parallel machines with sequence-dependent setup times. Applied Soft Computing, 110, 107521.","DOI":"10.1016\/j.asoc.2021.107521"},{"issue":"3\u20134","key":"1959_CR26","doi-asserted-by":"publisher","first-page":"223","DOI":"10.1016\/S0736-5845(02)00013-3","volume":"18","author":"DW Kim","year":"2002","unstructured":"Kim, D. W., Kim, K. H., Jang, W., & Chen, F. F. (2002). Unrelated parallel machine scheduling with setup times using simulated annealing. Robotics and Computer-Integrated Manufacturing, 18(3\u20134), 223\u2013231.","journal-title":"Robotics and Computer-Integrated Manufacturing"},{"key":"1959_CR27","doi-asserted-by":"publisher","first-page":"343","DOI":"10.1016\/S0167-5060(08)70743-X","volume":"1","author":"JK Lenstra","year":"1977","unstructured":"Lenstra, J. K., Kan, A. R., & Brucker, P. (1977). Complexity of machine scheduling problems. Annals of Discrete Mathematics, 1, 343\u2013362.","journal-title":"Annals of Discrete Mathematics"},{"key":"1959_CR28","doi-asserted-by":"publisher","first-page":"172","DOI":"10.1016\/j.cor.2014.05.013","volume":"51","author":"SW Lin","year":"2014","unstructured":"Lin, S. W., & Ying, K. C. (2014). Abc-based manufacturing scheduling for unrelated parallel machines with machine-dependent and job sequence-dependent setup times. Computers & Operations Research, 51, 172\u2013181.","journal-title":"Computers & Operations Research"},{"key":"1959_CR29","volume-title":"Engineering Statistics","author":"DC Montgomery","year":"2009","unstructured":"Montgomery, D. C., Runger, G. C., & Hubele, N. F. (2009). Engineering Statistics. Hoboken: Wiley."},{"issue":"1","key":"1959_CR30","doi-asserted-by":"publisher","first-page":"85","DOI":"10.1007\/s10845-005-5514-0","volume":"17","author":"G Rabadi","year":"2006","unstructured":"Rabadi, G., Moraga, R. J., & Al-Salem, A. (2006). Heuristics for the unrelated parallel machine scheduling problem with setup times. Journal of Intelligent Manufacturing, 17(1), 85\u201397.","journal-title":"Journal of Intelligent Manufacturing"},{"issue":"2","key":"1959_CR31","doi-asserted-by":"publisher","first-page":"707","DOI":"10.1111\/itor.12316","volume":"26","author":"HG Santos","year":"2019","unstructured":"Santos, H. G., Toffolo, T. A., Silva, C. L., & Vanden Berghe, G. (2019). Analysis of stochastic local search methods for the unrelated parallel machine scheduling problem. International Transactions in Operational Research, 26(2), 707\u2013724.","journal-title":"International Transactions in Operational Research"},{"issue":"3","key":"1959_CR32","doi-asserted-by":"publisher","first-page":"612","DOI":"10.1016\/j.ejor.2011.01.011","volume":"211","author":"E Vallada","year":"2011","unstructured":"Vallada, E., & Ruiz, R. (2011). A genetic algorithm for the unrelated parallel machine scheduling problem with sequence dependent setup times. European Journal of Operational Research, 211(3), 612\u2013622.","journal-title":"European Journal of Operational Research"},{"key":"1959_CR33","doi-asserted-by":"crossref","unstructured":"Wesley Barnes, J., & Laguna, M. (1993). Solving the multiple-machine weighted flow time problem using tabu search. IIE Transactions, 25(2), 121\u2013128.","DOI":"10.1080\/07408179308964284"},{"key":"1959_CR34","volume-title":"Nature-Inspired Optimization Algorithms","author":"XS Yang","year":"2020","unstructured":"Yang, X. S. (2020). Nature-Inspired Optimization Algorithms. Cambridge: Academic Press."},{"issue":"12","key":"1959_CR35","doi-asserted-by":"publisher","first-page":"2154","DOI":"10.1080\/00405000.2017.1316177","volume":"108","author":"D Yilmaz Eroglu","year":"2017","unstructured":"Yilmaz Eroglu, D., & Ozmutlu, H. (2017). Solution method for a large-scale loom scheduling problem with machine eligibility and splitting property. The Journal of The Textile Institute, 108(12), 2154\u20132165.","journal-title":"The Journal of The Textile Institute"},{"issue":"5","key":"1959_CR36","doi-asserted-by":"publisher","first-page":"1795","DOI":"10.1007\/s10845-010-0483-3","volume":"23","author":"KC Ying","year":"2012","unstructured":"Ying, K. C., Lee, Z. J., & Lin, S. W. (2012). Makespan minimization for scheduling unrelated parallel machines with setup times. Journal of Intelligent Manufacturing, 23(5), 1795\u20131803.","journal-title":"Journal of Intelligent Manufacturing"},{"issue":"11","key":"1959_CR37","doi-asserted-by":"publisher","first-page":"987","DOI":"10.1080\/07408170600559706","volume":"38","author":"X Zhu","year":"2006","unstructured":"Zhu, X., & Wilhelm, W. E. (2006). Scheduling and lot sizing with sequence-dependent setup: A literature review. IIE Transactions, 38(11), 987\u20131007.","journal-title":"IIE Transactions"}],"container-title":["Journal of Intelligent Manufacturing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10845-022-01959-4.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10845-022-01959-4\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10845-022-01959-4.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,8,30]],"date-time":"2022-08-30T13:10:56Z","timestamp":1661865056000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10845-022-01959-4"}},"subtitle":["A comparative study of metaheuristics on large problem instances"],"short-title":[],"issued":{"date-parts":[[2022,6,1]]},"references-count":37,"journal-issue":{"issue":"7","published-print":{"date-parts":[[2022,10]]}},"alternative-id":["1959"],"URL":"https:\/\/doi.org\/10.1007\/s10845-022-01959-4","relation":{},"ISSN":["0956-5515","1572-8145"],"issn-type":[{"value":"0956-5515","type":"print"},{"value":"1572-8145","type":"electronic"}],"subject":[],"published":{"date-parts":[[2022,6,1]]},"assertion":[{"value":"19 March 2021","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"30 April 2022","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"1 June 2022","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}