{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,11]],"date-time":"2025-11-11T13:41:51Z","timestamp":1762868511097,"version":"build-2065373602"},"reference-count":34,"publisher":"MDPI AG","issue":"5","license":[{"start":{"date-parts":[[2021,4,30]],"date-time":"2021-04-30T00:00:00Z","timestamp":1619740800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithms"],"abstract":"<jats:p>When no-wait constraint holds in job shops, a job has to be processed with no waiting time from the first to the last operation, and the start time of a job is greatly restricted. Using key elements of the iterated greedy algorithm, this paper proposes a population-based iterated greedy (PBIG) algorithm for finding high-quality schedules in no-wait job shops. Firstly, the Nawaz\u2013Enscore\u2013Ham (NEH) heuristic used for flow shop is extended in no-wait job shops, and an initialization scheme based on the NEH heuristic is developed to generate start solutions with a certain quality and diversity. Secondly, the iterated greedy procedure is introduced based on the destruction and construction perturbator and the insert-based local search. Furthermore, a population-based co-evolutionary scheme is presented by imposing the iterated greedy procedure in parallel and hybridizing both the left timetabling and inverse left timetabling methods. Computational results based on well-known benchmark instances show that the proposed algorithm outperforms two existing metaheuristics by a significant margin.<\/jats:p>","DOI":"10.3390\/a14050145","type":"journal-article","created":{"date-parts":[[2021,4,30]],"date-time":"2021-04-30T10:53:29Z","timestamp":1619780009000},"page":"145","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":7,"title":["No-Wait Job Shop Scheduling Using a Population-Based Iterated Greedy Algorithm"],"prefix":"10.3390","volume":"14","author":[{"given":"Mingming","family":"Xu","sequence":"first","affiliation":[{"name":"Key Laboratory of Cyber-Physical System and Intelligent Control in Universities of Shandong, School of Information and Electrical Engineering, Ludong University, Yantai 264025, China"}]},{"given":"Shuning","family":"Zhang","sequence":"additional","affiliation":[{"name":"Key Laboratory of Cyber-Physical System and Intelligent Control in Universities of Shandong, School of Information and Electrical Engineering, Ludong University, Yantai 264025, China"}]},{"given":"Guanlong","family":"Deng","sequence":"additional","affiliation":[{"name":"Key Laboratory of Cyber-Physical System and Intelligent Control in Universities of Shandong, School of Information and Electrical Engineering, Ludong University, Yantai 264025, China"}]}],"member":"1968","published-online":{"date-parts":[[2021,4,30]]},"reference":[{"key":"ref_1","unstructured":"Pinedo, M. (2016). Scheduling: Theory, Algorithms, and Systems, Springer. [5th ed.]."},{"key":"ref_2","doi-asserted-by":"crossref","first-page":"423","DOI":"10.1016\/S0377-2217(99)00041-7","article-title":"A mathematical programming model for scheduling steelmaking-continuous casting production","volume":"120","author":"Tang","year":"2000","journal-title":"Eur. J. Oper. Res."},{"key":"ref_3","doi-asserted-by":"crossref","first-page":"535","DOI":"10.1016\/S0377-2217(99)00224-6","article-title":"Sequencing of jobs in some production system","volume":"125","author":"Grabowski","year":"2000","journal-title":"Eur. J. Oper. Res."},{"key":"ref_4","first-page":"472","article-title":"A no-wait flow shop scheduling heuristic to minimize makespan","volume":"45","author":"Rajendran","year":"1994","journal-title":"Eur. J. Oper. Res."},{"key":"ref_5","doi-asserted-by":"crossref","first-page":"510","DOI":"10.1287\/opre.44.3.510","article-title":"A survey of machine scheduling problems with blocking and no-wait in process","volume":"44","author":"Hall","year":"1996","journal-title":"Oper. Res."},{"key":"ref_6","doi-asserted-by":"crossref","first-page":"343","DOI":"10.1016\/S0167-5060(08)70743-X","article-title":"Complexity of machine scheduling problems","volume":"1","author":"Lenstra","year":"1997","journal-title":"Ann. Discret. Math."},{"key":"ref_7","doi-asserted-by":"crossref","first-page":"448","DOI":"10.1287\/moor.4.4.448","article-title":"Complexity of scheduling shops with no-wait in process","volume":"4","author":"Sahni","year":"1979","journal-title":"Math. Oper. Res."},{"key":"ref_8","doi-asserted-by":"crossref","first-page":"498","DOI":"10.1016\/S0377-2217(01)00338-1","article-title":"Job-shop scheduling with blocking and no-wait constraints","volume":"143","author":"Mascis","year":"2002","journal-title":"Eur. J. Oper. Res."},{"key":"ref_9","unstructured":"Van den Broek, J. (2009). MIP-Based Approaches for Complex Planning Problems. [Ph.D. Thesis, Technische Universiteit Eindhoven]."},{"key":"ref_10","doi-asserted-by":"crossref","first-page":"345","DOI":"10.1007\/s10878-012-9466-y","article-title":"Optimal job insertion in the no-wait job shop","volume":"26","year":"2013","journal-title":"J. Comb. Optim."},{"key":"ref_11","doi-asserted-by":"crossref","first-page":"2585","DOI":"10.1080\/002075499190671","article-title":"Modelling and optimization of industrial manufacturing processes subject to no-wait constraints","volume":"37","author":"Macchiaroli","year":"1999","journal-title":"Int. J. Prod. Res."},{"key":"ref_12","doi-asserted-by":"crossref","first-page":"308","DOI":"10.1016\/S0167-6377(03)00005-1","article-title":"Approximate procedures for no-wait job shop scheduling","volume":"31","author":"Schuster","year":"2003","journal-title":"Oper. Res. Lett."},{"key":"ref_13","doi-asserted-by":"crossref","first-page":"473","DOI":"10.1007\/s00186-005-0056-y","article-title":"No-wait job shop scheduling: Tabu search and complexity of subproblems","volume":"63","author":"Schuster","year":"2006","journal-title":"Math. Methods Oper. Res."},{"key":"ref_14","doi-asserted-by":"crossref","first-page":"1200","DOI":"10.1016\/j.cor.2004.09.009","article-title":"An enhanced timetabling procedure for the no-wait job shop problem: A complete local search approach","volume":"331","author":"Framinan","year":"2006","journal-title":"Comput. Oper. Res."},{"key":"ref_15","doi-asserted-by":"crossref","first-page":"378","DOI":"10.1016\/j.ejor.2008.09.015","article-title":"Complete local search with limited memory algorithm for no-wait job shops to minimize makespan","volume":"198","author":"Zhu","year":"2009","journal-title":"Eur. J. Oper. Res."},{"key":"ref_16","first-page":"189","article-title":"An effective meta-heuristic for no-wait job shops to minimize makespan","volume":"9","author":"Zhu","year":"2012","journal-title":"IEEE Trans. Autom. Sci. Eng."},{"key":"ref_17","doi-asserted-by":"crossref","first-page":"1595","DOI":"10.1007\/s00170-014-6086-y","article-title":"A two-stage no-wait job shop scheduling problem by using a neuro-evolutionary variable neighborhood search","volume":"74","author":"Mokhtari","year":"2014","journal-title":"Int. J. Adv. Manuf. Technol."},{"key":"ref_18","doi-asserted-by":"crossref","first-page":"679","DOI":"10.1007\/s10845-014-0906-7","article-title":"Branch-and-bound and PSO algorithms for no-wait job shop scheduling","volume":"27","author":"Aitzai","year":"2016","journal-title":"J. Intell. Manuf."},{"key":"ref_19","doi-asserted-by":"crossref","first-page":"1401","DOI":"10.1007\/s00170-013-4866-4","article-title":"A memory-based complete local search method with variable neighborhood structures for no-wait job shops","volume":"87","author":"Li","year":"2016","journal-title":"Int. J. Adv. Manuf. Technol."},{"key":"ref_20","doi-asserted-by":"crossref","first-page":"1193","DOI":"10.1007\/s00500-015-1852-9","article-title":"A hybrid artificial bee colony algorithm for the job-shop scheduling problem with no-wait constraint","volume":"21","author":"Sundar","year":"2017","journal-title":"Soft Comput."},{"key":"ref_21","doi-asserted-by":"crossref","first-page":"2033","DOI":"10.1016\/j.ejor.2005.12.009","article-title":"A simple and effective iterated greedy algorithm for the permutation flowshop scheduling problem","volume":"177","author":"Ruiz","year":"2007","journal-title":"Eur. J. Oper. Res."},{"key":"ref_22","doi-asserted-by":"crossref","first-page":"2292","DOI":"10.1080\/00207543.2017.1374571","article-title":"A dispatching rule and a random iterated greedy metaheuristic for identical parallel machine scheduling to minimize total tardiness","volume":"56","author":"Lee","year":"2018","journal-title":"Int. J. Prod. Res."},{"key":"ref_23","doi-asserted-by":"crossref","first-page":"213","DOI":"10.1016\/j.omega.2018.03.004","article-title":"Iterated greedy methods for the distributed permutation fowshop scheduling problem","volume":"83","author":"Ruiz","year":"2019","journal-title":"OMEGA"},{"key":"ref_24","doi-asserted-by":"crossref","first-page":"347","DOI":"10.1016\/j.eswa.2018.12.039","article-title":"An iterated greedy algorithm for solving the total tardiness parallel blocking flow shop scheduling problem","volume":"121","author":"Ribas","year":"2019","journal-title":"Expert Syst. Appl."},{"key":"ref_25","doi-asserted-by":"crossref","first-page":"4942","DOI":"10.1080\/00207543.2013.784410","article-title":"Studying the effect of different combinations of timetabling with sequencing algorithms to solve the no-wait job shop scheduling problem","volume":"51","author":"Samarghandi","year":"2013","journal-title":"Int. J. Prod. Res."},{"key":"ref_26","doi-asserted-by":"crossref","first-page":"103369","DOI":"10.1016\/j.engappai.2019.103369","article-title":"A population-based iterated greedy algorithm for no-wait job shop scheduling with total flow time criterion","volume":"88","author":"Deng","year":"2020","journal-title":"Eng. Appl. Artif. Intell."},{"key":"ref_27","doi-asserted-by":"crossref","first-page":"91","DOI":"10.1016\/0305-0483(83)90088-9","article-title":"A heuristic algorithm for the m-machine, n-job flow-shop sequencing problem","volume":"11","author":"Nawaz","year":"1983","journal-title":"Omega"},{"key":"ref_28","unstructured":"Fisher, H., and Thompson, G.L. (1963). Probabilistic Learning Combinations of Local Job-Shop Scheduling Rules. Industrial Scheduling, Prentice-Hall."},{"key":"ref_29","doi-asserted-by":"crossref","first-page":"149","DOI":"10.1287\/ijoc.3.2.149","article-title":"A computational study of the job-shop problem","volume":"3","author":"Applegate","year":"1991","journal-title":"ORSA J. Comput."},{"key":"ref_30","doi-asserted-by":"crossref","first-page":"391","DOI":"10.1287\/mnsc.34.3.391","article-title":"The shifting bottleneck procedure for job shop scheduling","volume":"34","author":"Adams","year":"1988","journal-title":"Manag. Sci."},{"key":"ref_31","unstructured":"Lawrence, S. (1984). Resource Constrained Project Scheduling: An Experimental Investigation of Heuristic Scheduling Techniques, Carnegie-Mellon University. Technical Report."},{"key":"ref_32","doi-asserted-by":"crossref","first-page":"1495","DOI":"10.1287\/mnsc.38.10.1495","article-title":"New search spaces for sequencing instances with application to job shop scheduling","volume":"38","author":"Storer","year":"1992","journal-title":"Manag. Sci."},{"key":"ref_33","doi-asserted-by":"crossref","first-page":"105480","DOI":"10.1016\/j.asoc.2019.05.007","article-title":"Total flow time minimization in no-wait job shop using a hybrid discrete group search optimizer","volume":"81","author":"Deng","year":"2019","journal-title":"Appl. Soft Comput."},{"key":"ref_34","unstructured":"Montgomery, D.C. (2012). Design and Analysis of Experiments, Wiley. [8th ed.]."}],"container-title":["Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/1999-4893\/14\/5\/145\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T05:56:08Z","timestamp":1760162168000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/1999-4893\/14\/5\/145"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,4,30]]},"references-count":34,"journal-issue":{"issue":"5","published-online":{"date-parts":[[2021,5]]}},"alternative-id":["a14050145"],"URL":"https:\/\/doi.org\/10.3390\/a14050145","relation":{},"ISSN":["1999-4893"],"issn-type":[{"type":"electronic","value":"1999-4893"}],"subject":[],"published":{"date-parts":[[2021,4,30]]}}}