{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,10]],"date-time":"2026-03-10T12:19:02Z","timestamp":1773145142306,"version":"3.50.1"},"reference-count":45,"publisher":"MDPI AG","issue":"11","license":[{"start":{"date-parts":[[2021,11,3]],"date-time":"2021-11-03T00:00:00Z","timestamp":1635897600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"DOI":"10.13039\/501100002507","name":"Kangwon National University","doi-asserted-by":"publisher","award":["2021"],"award-info":[{"award-number":["2021"]}],"id":[{"id":"10.13039\/501100002507","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100003725","name":"National Research Foundation of Korea","doi-asserted-by":"publisher","award":["NRF-2020R1G1A1006268"],"award-info":[{"award-number":["NRF-2020R1G1A1006268"]}],"id":[{"id":"10.13039\/501100003725","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100003725","name":"National Research Foundation of Korea","doi-asserted-by":"publisher","award":["2020R1G1A1099829"],"award-info":[{"award-number":["2020R1G1A1099829"]}],"id":[{"id":"10.13039\/501100003725","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithms"],"abstract":"<jats:p>This study considers a scheduling problem for a flow shop with urgent jobs and limited waiting times. The urgent jobs and limited waiting times are major considerations for scheduling in semiconductor manufacturing systems. The objective function is to minimize a weighted sum of total tardiness of urgent jobs and the makespan of normal jobs. This problem is formulated in mixed integer programming (MIP). By using a commercial optimization solver, the MIP can be used to find an optimal solution. However, because this problem is proved to be NP-hard, solving to optimality requires a significantly long computation time for a practical size problem. Therefore, this study adopts metaheuristic algorithms to obtain a good solution quickly. To complete this, two metaheuristic algorithms (an iterated greedy algorithm and a simulated annealing algorithm) are proposed, and a series of computational experiments were performed to examine the effectiveness and efficiency of the proposed algorithms.<\/jats:p>","DOI":"10.3390\/a14110323","type":"journal-article","created":{"date-parts":[[2021,11,3]],"date-time":"2021-11-03T17:59:38Z","timestamp":1635962378000},"page":"323","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":18,"title":["Metaheuristics for a Flow Shop Scheduling Problem with Urgent Jobs and Limited Waiting Times"],"prefix":"10.3390","volume":"14","author":[{"given":"BongJoo","family":"Jeong","sequence":"first","affiliation":[{"name":"Department of Business Administration, Kongju National University, Kongju-si 32588, Korea"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-3292-5705","authenticated-orcid":false,"given":"Jun-Hee","family":"Han","sequence":"additional","affiliation":[{"name":"Department of Industrial and Management Engineering, Dong-A University, Busan 49315, Korea"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-4515-1454","authenticated-orcid":false,"given":"Ju-Yong","family":"Lee","sequence":"additional","affiliation":[{"name":"Division of Business Administration & Accounting, Kangwon National University, Chuncheon-si 24341, Korea"}]}],"member":"1968","published-online":{"date-parts":[[2021,11,3]]},"reference":[{"key":"ref_1","doi-asserted-by":"crossref","first-page":"5","DOI":"10.1299\/jamdsm.2017jamdsm0062","article-title":"Heuristic algorithms for two-machine re-entrant flowshop scheduling problem with jobs of two classes","volume":"11","author":"Jeong","year":"2017","journal-title":"J. Adv. Mech. Des. Syst. Manuf."},{"key":"ref_2","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/j.cie.2018.04.021","article-title":"Permutation flowshop scheduling with time lag constraints and makespan criterion","volume":"120","author":"Wang","year":"2018","journal-title":"Comput. Ind. Eng."},{"key":"ref_3","doi-asserted-by":"crossref","first-page":"127","DOI":"10.1016\/j.cor.2016.01.017","article-title":"Minimizing makespan in a two-machine flowshop with a limited waiting time constraint and sequence-dependent setup times","volume":"71","author":"An","year":"2016","journal-title":"Comput. Oper. Res."},{"key":"ref_4","doi-asserted-by":"crossref","first-page":"1025","DOI":"10.1287\/opre.42.6.1025","article-title":"The Total Tardiness Problem: Review and Extensions","volume":"42","author":"Koulamas","year":"1994","journal-title":"Oper. Res."},{"key":"ref_5","doi-asserted-by":"crossref","first-page":"8","DOI":"10.1016\/0360-8352(94)00026-J","article-title":"A two-machine flowshop sequencing problem with limited waiting time constraints","volume":"28","author":"Yang","year":"1995","journal-title":"Comput. Ind. Eng."},{"key":"ref_6","doi-asserted-by":"crossref","first-page":"407","DOI":"10.1007\/s12293-019-00290-5","article-title":"Multi-objective flow shop scheduling with limited buffers using hybrid self-adaptive differential evolution","volume":"11","author":"Liang","year":"2019","journal-title":"Memetic. Comput."},{"key":"ref_7","doi-asserted-by":"crossref","first-page":"49","DOI":"10.1007\/s10951-019-00610-0","article-title":"Metaheuristics for solving a multi-objective flow shop scheduling problem with sequence-dependent setup times","volume":"23","author":"Anjana","year":"2020","journal-title":"J. Sched."},{"key":"ref_8","doi-asserted-by":"crossref","first-page":"115339","DOI":"10.1016\/j.eswa.2021.115339","article-title":"Multi-objective distributed reentrant permutation flow shop scheduling with sequence-dependent setup time","volume":"183","author":"Rifai","year":"2021","journal-title":"Expert Syst. Appl."},{"key":"ref_9","doi-asserted-by":"crossref","first-page":"325","DOI":"10.1016\/j.cie.2019.07.036","article-title":"A multiobjective evolutionary algorithm based on decomposition for hybrid flowshop green scheduling problem","volume":"136","author":"Zhang","year":"2019","journal-title":"Comput. Ind. Eng."},{"key":"ref_10","doi-asserted-by":"crossref","first-page":"106343","DOI":"10.1016\/j.asoc.2020.106343","article-title":"Discrete evolutionary multi-objective optimization for energy-efficient blocking flow shop scheduling with setup time","volume":"93","author":"Han","year":"2020","journal-title":"Appl. Soft. Comput."},{"key":"ref_11","doi-asserted-by":"crossref","first-page":"6687","DOI":"10.1109\/TII.2020.3043734","article-title":"Energy-efficient scheduling of distributed flow shop with heterogeneous factories: A real-world case from automobile industry in China","volume":"17","author":"Lu","year":"2021","journal-title":"IEEE Trans. Ind. Inform."},{"key":"ref_12","doi-asserted-by":"crossref","first-page":"229","DOI":"10.1287\/opre.1030.0092","article-title":"Scheduling problems with two competing agents","volume":"52","author":"Agnetis","year":"2004","journal-title":"Oper. Res."},{"key":"ref_13","doi-asserted-by":"crossref","first-page":"7","DOI":"10.1023\/A:1022231419049","article-title":"A multiple-criterion model for machine scheduling","volume":"6","author":"Baker","year":"2003","journal-title":"J. Sched."},{"key":"ref_14","doi-asserted-by":"crossref","first-page":"387","DOI":"10.1007\/s10878-006-9001-0","article-title":"A note on the complexity of the problem of two-agent scheduling on a single machine","volume":"12","author":"Ng","year":"2006","journal-title":"J. Comb. Optim."},{"key":"ref_15","doi-asserted-by":"crossref","first-page":"458","DOI":"10.1287\/opre.1090.0744","article-title":"Competitive two-agent scheduling and its applications","volume":"58","author":"Leung","year":"2010","journal-title":"Oper. Res."},{"key":"ref_16","doi-asserted-by":"crossref","first-page":"273","DOI":"10.1016\/j.tcs.2006.07.011","article-title":"Multi-agent scheduling on a single machine to minimize total weighted number of tardy jobs","volume":"362","author":"Cheng","year":"2006","journal-title":"Theor. Comput. Sci."},{"key":"ref_17","doi-asserted-by":"crossref","first-page":"603","DOI":"10.1016\/j.ejor.2007.04.040","article-title":"Multi-agent scheduling on a single machine with max-form criteria","volume":"188","author":"Cheng","year":"2008","journal-title":"Eur. J. Oper. Res."},{"key":"ref_18","unstructured":"Liu, P., and Tang, L. (2008). Two-Agent Scheduling with Linear Deteriorating Jobs on a Single Machine, Springer."},{"key":"ref_19","first-page":"10831","article-title":"A single-machine bi-criterion scheduling problem with two agents","volume":"219","author":"Lee","year":"2013","journal-title":"Appl. Math. Comput."},{"key":"ref_20","first-page":"912","article-title":"Pareto optimization scheduling with two competing agents to minimize the number of tardy jobs and the maximum cost","volume":"273","author":"Wan","year":"2016","journal-title":"Appl. Math. Comput."},{"key":"ref_21","doi-asserted-by":"crossref","first-page":"6594","DOI":"10.1016\/j.eswa.2010.02.125","article-title":"Branch-and-bound and simulated annealing algorithms for a two-agent scheduling problem","volume":"37","author":"Lee","year":"2010","journal-title":"Expert Syst. Appl."},{"key":"ref_22","doi-asserted-by":"crossref","first-page":"98","DOI":"10.1016\/j.cor.2010.04.002","article-title":"A two-machine flowshop problem with two agents","volume":"38","author":"Lee","year":"2011","journal-title":"Comput. Oper. Res."},{"key":"ref_23","doi-asserted-by":"crossref","first-page":"151","DOI":"10.1057\/jors.2013.9","article-title":"Polynomial time solutions for scheduling problems on a proportionate flowshop with two competing agents","volume":"65","author":"Mor","year":"2014","journal-title":"J. Oper. Res. Soc."},{"key":"ref_24","doi-asserted-by":"crossref","first-page":"376","DOI":"10.1016\/j.ejor.2016.01.009","article-title":"Two-agent scheduling in a flowshop","volume":"252","author":"Fan","year":"2016","journal-title":"Eur. J. Oper. Res."},{"key":"ref_25","doi-asserted-by":"crossref","first-page":"3123","DOI":"10.1111\/itor.12530","article-title":"Algorithms for a two-machine flowshop problem with jobs of two classes","volume":"27","author":"Jeong","year":"2020","journal-title":"Int. Trans. Oper. Res."},{"key":"ref_26","doi-asserted-by":"crossref","unstructured":"Azerine, A., Boudhar, M., and Rebaine, D. (2021). A two-machine no-wait flow shop problem with two competing agents. J. Comb. Optim., in press.","DOI":"10.1007\/s10878-021-00755-9"},{"key":"ref_27","doi-asserted-by":"crossref","first-page":"15","DOI":"10.1007\/s10288-005-0069-7","article-title":"Two-machine flow shop scheduling problems with minimal and maximal delays","volume":"4","author":"Bouquard","year":"2006","journal-title":"4OR"},{"key":"ref_28","doi-asserted-by":"crossref","first-page":"572","DOI":"10.1057\/palgrave.jors.2602598","article-title":"A branch-and-bound algorithm for a two-machine flowshop scheduling problem with limited waiting time constraints","volume":"60","author":"Joo","year":"2009","journal-title":"J. Oper. Res. Soc."},{"key":"ref_29","first-page":"95","article-title":"Minimizing total tardiness in the permutation flowshop scheduling problem with minimal and maximal time lags","volume":"15","author":"Hamdi","year":"2015","journal-title":"Oper. Res. Ger."},{"key":"ref_30","doi-asserted-by":"crossref","first-page":"213","DOI":"10.1111\/j.1475-3995.2012.00876.x","article-title":"Lexicographic optimization of a permutation flow shop scheduling problem with time lag constraints","volume":"20","author":"Dhouib","year":"2013","journal-title":"Int. Trans. Oper. Res."},{"key":"ref_31","doi-asserted-by":"crossref","first-page":"93","DOI":"10.1016\/j.cor.2018.06.009","article-title":"Three-machine flow shop scheduling with overlapping waiting time constraints","volume":"101","author":"Kim","year":"2019","journal-title":"Comput. Oper. Res."},{"key":"ref_32","doi-asserted-by":"crossref","first-page":"8833645","DOI":"10.1155\/2020\/8833645","article-title":"A genetic algorithm for a two-machine flowshop with a limited waiting time constraint and sequence-dependent setup times","volume":"2020","author":"Lee","year":"2020","journal-title":"Math. Probl. Eng."},{"key":"ref_33","doi-asserted-by":"crossref","first-page":"155","DOI":"10.1109\/TSM.2017.2662231","article-title":"Minimization of waiting time variation in a generalized two-machine flowshop with waiting time constraints and skipping jobs","volume":"30","author":"Yu","year":"2017","journal-title":"IEEE T Semicond. Manuf."},{"key":"ref_34","doi-asserted-by":"crossref","first-page":"484","DOI":"10.1080\/0305215X.2019.1593974","article-title":"A two-stage flow-shop scheduling problem with incompatible job families and limited waiting time","volume":"52","author":"Li","year":"2020","journal-title":"Eng. Optim."},{"key":"ref_35","doi-asserted-by":"crossref","first-page":"223","DOI":"10.1007\/s40092-019-00331-1","article-title":"MILP models and valid inequalities for the two-machine permutation flowshop scheduling problem with minimal time lags","volume":"15","author":"Hamdi","year":"2019","journal-title":"J. Ind. Eng. Int."},{"key":"ref_36","doi-asserted-by":"crossref","first-page":"3","DOI":"10.1016\/j.compind.2019.04.014","article-title":"Sampling-based release control of multiple lots in time constraint tunnels","volume":"110","author":"Lima","year":"2019","journal-title":"Comput. Ind."},{"key":"ref_37","doi-asserted-by":"crossref","first-page":"860","DOI":"10.1080\/00207543.2020.1711984","article-title":"A sampling-based approach for managing lot release in time constraint tunnels in semiconductor manufacturing","volume":"59","author":"Lima","year":"2021","journal-title":"Int. J. Prod. Res."},{"key":"ref_38","doi-asserted-by":"crossref","first-page":"104965","DOI":"10.1016\/j.cor.2020.104965","article-title":"Relationship between common objective functions, idle time and waiting time in permutation flow shop scheduling","volume":"121","author":"Maassena","year":"2020","journal-title":"Comput. Oper. Res."},{"key":"ref_39","doi-asserted-by":"crossref","first-page":"614","DOI":"10.1016\/j.cie.2019.07.048","article-title":"Minimizing the makespan in a flow shop environment under minimum and maximum time-lag constraints","volume":"136","author":"Samarghandi","year":"2019","journal-title":"Comput. Ind. Eng."},{"key":"ref_40","doi-asserted-by":"crossref","first-page":"160","DOI":"10.1016\/j.cie.2017.08.024","article-title":"Efficient heuristic for solving non-permutation flow-shop scheduling problems with maximal and minimal time lags","volume":"113","author":"Ye","year":"2017","journal-title":"Comput. Ind. Eng."},{"key":"ref_41","doi-asserted-by":"crossref","unstructured":"Zhou, N., Wu, M., and Zhou, J. (2018, January 6\u20139). Research on power battery formation production scheduling problem with limited waiting time constraints. Proceedings of the 2018 10th International Conference on Communication Software and Networks, Chengdu, China.","DOI":"10.1109\/ICCSN.2018.8488247"},{"key":"ref_42","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_43","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_44","doi-asserted-by":"crossref","first-page":"551","DOI":"10.1016\/0305-0483(89)90059-5","article-title":"Simulated annealing for permutation flow-shop scheduling","volume":"17","author":"Osman","year":"1989","journal-title":"Omega"},{"key":"ref_45","doi-asserted-by":"crossref","first-page":"61","DOI":"10.1002\/nav.3800010110","article-title":"Optimal two- and three-stage production schedules with setup times included","volume":"1","author":"Johnson","year":"1954","journal-title":"Nav. Res. Logist. Q."}],"container-title":["Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/1999-4893\/14\/11\/323\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T07:25:26Z","timestamp":1760167526000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/1999-4893\/14\/11\/323"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,11,3]]},"references-count":45,"journal-issue":{"issue":"11","published-online":{"date-parts":[[2021,11]]}},"alternative-id":["a14110323"],"URL":"https:\/\/doi.org\/10.3390\/a14110323","relation":{},"ISSN":["1999-4893"],"issn-type":[{"value":"1999-4893","type":"electronic"}],"subject":[],"published":{"date-parts":[[2021,11,3]]}}}