{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,25]],"date-time":"2026-07-25T15:01:48Z","timestamp":1784991708956,"version":"3.55.0"},"reference-count":38,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[2026,7,25]],"date-time":"2026-07-25T00:00:00Z","timestamp":1784937600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2026,7,25]],"date-time":"2026-07-25T00:00:00Z","timestamp":1784937600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100001636","name":"University College Cork","doi-asserted-by":"crossref","id":[{"id":"10.13039\/501100001636","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Oper Res Int J"],"published-print":{"date-parts":[[2026,12]]},"abstract":"<jats:title>Abstract<\/jats:title>\n                  <jats:p>On-time delivery is becoming increasingly crucial for industrial companies, due to their customers\u2019 need for deliveries by specific dates. This paper investigates parallel machine scheduling problems with sequence-dependent setup times, a combinatorial challenge that has gained significant attention due to its practicality and relevance in real-world applications. Aiming to reduce total weighted tardiness, we introduce a mixed integer linear programming model and an effective iterated greedy approach with a strategic reconstruction operator. We evaluate the performance of our methods by comparing it with six well-established and related approaches. Our experiments, using a benchmark set of 900 instances, validate that the introduced iterated greedy algorithm consistently produces high-quality solutions.<\/jats:p>","DOI":"10.1007\/s12351-026-01092-7","type":"journal-article","created":{"date-parts":[[2026,7,25]],"date-time":"2026-07-25T14:17:29Z","timestamp":1784989049000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Iterated greedy with strategic reconstruction for parallel machine problem with weighted tardiness and setup times"],"prefix":"10.1007","volume":"26","author":[{"given":"Ahmed","family":"Missaoui","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Barry","family":"O\u2019Sullivan","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2026,7,25]]},"reference":[{"key":"1092_CR1","doi-asserted-by":"publisher","first-page":"115916","DOI":"10.1016\/j.eswa.2021.115916","volume":"187","author":"OA Ar\u0131k","year":"2022","unstructured":"Ar\u0131k OA, Schutten M, Topan E (2022) Weighted earliness\/tardiness parallel machine scheduling problem with a common due date. Expert Syst Appl 187:115916","journal-title":"Expert Syst Appl"},{"issue":"1","key":"1092_CR2","doi-asserted-by":"publisher","first-page":"134","DOI":"10.1016\/j.ijpe.2008.04.011","volume":"115","author":"D Biskup","year":"2008","unstructured":"Biskup D, Herrmann J, Gupta JN (2008) Scheduling identical parallel machines to minimize total tardiness. Int J Prod Econ 115(1):134\u2013142","journal-title":"Int J Prod Econ"},{"issue":"5","key":"1092_CR3","doi-asserted-by":"publisher","first-page":"581","DOI":"10.1007\/s00170-008-1617-z","volume":"42","author":"IA Chaudhry","year":"2009","unstructured":"Chaudhry IA, Drake PR (2009) Minimizing total tardiness for the machine scheduling and worker assignment problems in identical parallel machines using genetic algorithms. Int J Adv Manuf Technol 42(5):581\u2013594","journal-title":"Int J Adv Manuf Technol"},{"issue":"3","key":"1092_CR4","doi-asserted-by":"publisher","first-page":"271","DOI":"10.1016\/0377-2217(90)90215-W","volume":"47","author":"TCE Cheng","year":"1990","unstructured":"Cheng TCE, Sin CCS (1990) A state-of-the-art review of parallel-machine scheduling research. Eur J Oper Res 47(3):271\u2013292","journal-title":"Eur J Oper Res"},{"issue":"3","key":"1092_CR5","doi-asserted-by":"publisher","first-page":"333","DOI":"10.1287\/ijoc.1070.0246","volume":"20","author":"M Dell\u2019Amico","year":"2008","unstructured":"Dell\u2019Amico M, Iori M, Martello S, Monaci M (2008) Heuristic and exact algorithms for the identical parallel machine scheduling problem. INFORMS J Comput 20(3):333\u2013344","journal-title":"INFORMS J Comput"},{"issue":"02","key":"1092_CR6","doi-asserted-by":"publisher","first-page":"369","DOI":"10.1142\/S0219686721500177","volume":"20","author":"MB Fakhrzad","year":"2021","unstructured":"Fakhrzad MB, Shamsadini S, Jafari-Nodoushan A (2021) The parallel machine scheduling with considering the due date assignment, earliness, weighted number of tardy jobs and batch delivery. J Adv Manuf Syst 20(02):369\u2013388","journal-title":"J Adv Manuf Syst"},{"issue":"7","key":"1092_CR7","doi-asserted-by":"publisher","first-page":"1745","DOI":"10.1016\/j.cor.2011.10.012","volume":"39","author":"L Fanjul-Peyro","year":"2012","unstructured":"Fanjul-Peyro L, Ruiz R (2012) Scheduling unrelated parallel machines with optional machines and jobs selection. Comput Op Res 39(7):1745\u20131753","journal-title":"Comput Op Res"},{"issue":"3","key":"1092_CR8","first-page":"353","volume":"7","author":"Y German","year":"2016","unstructured":"German Y, Badi I, Bakir A, Shetwan A (2016) Scheduling to minimize makespan on identical parallel machines. Int J Sci Eng Res 7(3):353\u2013359","journal-title":"Int J Sci Eng Res"},{"issue":"1","key":"1092_CR9","doi-asserted-by":"publisher","first-page":"221","DOI":"10.1016\/j.jpdc.2018.05.008","volume":"133","author":"L Ghalami","year":"2019","unstructured":"Ghalami L, Grosu D (2019) Scheduling parallel identical machines to minimize makespan: a parallel approximation algorithm. J Parallel Distrib Computng 133(1):221\u2013231","journal-title":"J Parallel Distrib Computng"},{"key":"1092_CR10","doi-asserted-by":"publisher","first-page":"287","DOI":"10.1016\/S0167-5060(08)70356-X","volume":"5","author":"RL Graham","year":"1979","unstructured":"Graham RL, Lawler EL, Lenstra JK, Kan AHG (1979) Optimization and approximation in deterministic sequencing and scheduling: a survey. Ann Discrete Math 5:287\u2013326","journal-title":"Ann Discrete Math"},{"issue":"12","key":"1092_CR11","doi-asserted-by":"publisher","first-page":"2970","DOI":"10.1016\/j.cor.2013.06.011","volume":"40","author":"M Ji","year":"2013","unstructured":"Ji M, Wang J-Y, Lee W-C (2013) Minimizing resource consumption on uniform parallel machines with a bound on makespan. Comput Op Res 40(12):2970\u20132974","journal-title":"Comput Op Res"},{"issue":"6","key":"1092_CR12","doi-asserted-by":"publisher","first-page":"1628","DOI":"10.1080\/00207543.2019.1672900","volume":"58","author":"J-G Kim","year":"2020","unstructured":"Kim J-G, Song S, Jeong BJ (2020) Minimising total tardiness for the identical parallel machine scheduling problem with splitting jobs and sequence-dependent setup times. Int J Prod Res 58(6):1628\u20131643","journal-title":"Int J Prod Res"},{"issue":"1","key":"1092_CR13","doi-asserted-by":"publisher","first-page":"15791","DOI":"10.1109\/ACCESS.2017.2735538","volume":"5","author":"S-W Lin","year":"2017","unstructured":"Lin S-W, Ying K-C (2017) Uniform parallel-machine scheduling for minimizing total resource consumption with a bounded makespan. IEEE Access 5(1):15791\u201315799","journal-title":"IEEE Access"},{"issue":"1","key":"1092_CR14","doi-asserted-by":"publisher","first-page":"99","DOI":"10.1016\/j.ejor.2022.02.019","volume":"303","author":"A Missaoui","year":"2022","unstructured":"Missaoui A, Ruiz R (2022) A parameter-less iterated greedy method for the hybrid flowshop scheduling problem with setup times and due date windows. Eur J Oper Res 303(1):99\u2013113","journal-title":"Eur J Oper Res"},{"key":"1092_CR15","doi-asserted-by":"crossref","unstructured":"Missaoui A, Ozturk C, O\u2019Sullivan B (2023) Iterated greedy algorithms for combinatorial optimization: a systematic literature review. In: The IEEE international conference on computer systems and applications. pp 1\u20137","DOI":"10.1109\/AICCSA59173.2023.10479246"},{"issue":"2","key":"1092_CR16","first-page":"193","volume":"18","author":"E Mokotoff","year":"2001","unstructured":"Mokotoff E (2001) Parallel machine scheduling problems: a survey. Asia-Pacific J Oper Res 18(2):193","journal-title":"Asia-Pacific J Oper Res"},{"issue":"6","key":"1092_CR17","doi-asserted-by":"publisher","first-page":"9625","DOI":"10.1016\/j.eswa.2008.09.063","volume":"36","author":"B Naderi","year":"2009","unstructured":"Naderi B, Zandieh M, Balagh AKG, Roshanaei V (2009) An improved simulated annealing for hybrid flowshops with sequence-dependent setup and transportation times to minimize total completion time and total tardiness. Expert Syst Appl 36(6):9625\u20139633","journal-title":"Expert Syst Appl"},{"issue":"11\u201312","key":"1092_CR18","doi-asserted-by":"publisher","first-page":"1186","DOI":"10.1007\/s00170-008-1569-3","volume":"41","author":"B Naderi","year":"2009","unstructured":"Naderi B, Zandieh M, Roshanaei V (2009) Scheduling hybrid flowshops with sequence dependent setup times to minimize makespan and maximum tardiness. Int J Adv Manuf Technol 41(11\u201312):1186\u20131198","journal-title":"Int J Adv Manuf Technol"},{"issue":"1","key":"1092_CR19","doi-asserted-by":"publisher","first-page":"91","DOI":"10.1016\/0305-0483(83)90088-9","volume":"11","author":"M Nawaz","year":"1983","unstructured":"Nawaz M, Enscore EE Jr, Ham I (1983) A heuristic algorithm for the m-machine, n-job flow-shop sequencing problem. Omega 11(1):91\u201395","journal-title":"Omega"},{"issue":"7","key":"1092_CR20","doi-asserted-by":"publisher","first-page":"869","DOI":"10.1016\/S0305-0548(00)00090-3","volume":"29","author":"JC-H Pan","year":"2002","unstructured":"Pan JC-H, Chen J-S, Chao C-M (2002) Minimizing tardiness in a two-machine flow-shop. Comput Op Res 29(7):869\u2013885","journal-title":"Comput Op Res"},{"key":"1092_CR21","first-page":"89","volume":"303","author":"Q-K Pan","year":"2017","unstructured":"Pan Q-K, Gao L, Li X-Y, Gao K-Z (2017) Effective metaheuristics for scheduling a hybrid flowshop with sequence-dependent setup times. Appl Math Comput 303:89\u2013112","journal-title":"Appl Math Comput"},{"issue":"2","key":"1092_CR22","doi-asserted-by":"publisher","first-page":"391","DOI":"10.1287\/opre.30.2.391","volume":"30","author":"SS Panwalkar","year":"1982","unstructured":"Panwalkar SS, Smith ML, Seidmann A (1982) Common due date assignment to minimize total penalty for the one machine scheduling problem. Oper Res 30(2):391\u2013399","journal-title":"Oper Res"},{"issue":"7","key":"1092_CR23","doi-asserted-by":"publisher","first-page":"1829","DOI":"10.1016\/j.cor.2013.01.018","volume":"40","author":"FJ Rodriguez","year":"2013","unstructured":"Rodriguez FJ, Lozano M, Blum C, Garcia-Martinez C (2013) An iterated greedy algorithm for the large-scale unrelated parallel machines scheduling problem. Comput Op Res 40(7):1829\u20131841","journal-title":"Comput Op Res"},{"issue":"3","key":"1092_CR24","doi-asserted-by":"publisher","first-page":"2033","DOI":"10.1016\/j.ejor.2005.12.009","volume":"177","author":"R Ruiz","year":"2007","unstructured":"Ruiz R, St\u00fctzle T (2007) A simple and effective iterated greedy algorithm for the permutation flowshop scheduling problem. Eur J Oper Res 177(3):2033\u20132049","journal-title":"Eur J Oper Res"},{"issue":"1","key":"1092_CR25","doi-asserted-by":"publisher","first-page":"213","DOI":"10.1016\/j.omega.2018.03.004","volume":"83","author":"R Ruiz","year":"2019","unstructured":"Ruiz R, Pan Q-K, Naderi B (2019) Iterated greedy methods for the distributed permutation flowshop scheduling problem. Omega 83(1):213\u2013222","journal-title":"Omega"},{"key":"1092_CR26","doi-asserted-by":"publisher","first-page":"105527","DOI":"10.1016\/j.knosys.2020.105527","volume":"194","author":"W Shao","year":"2020","unstructured":"Shao W, Shao Z, Pi D (2020) Modeling and multi-neighborhood iterated greedy algorithm for distributed hybrid flow shop scheduling problem. Knowl-Based Syst 194:105527","journal-title":"Knowl-Based Syst"},{"issue":"1","key":"1092_CR27","first-page":"47","volume":"34","author":"Thamarai Selvi Somasundaram and Kannan Govindarajan","year":"2014","unstructured":"Thamarai Selvi Somasundaram and Kannan Govindarajan (2014) Cloudrb: a framework for scheduling and managing high-performance computing (HPC) applications in science cloud. Futur Gener Comput Syst 34(1):47\u201365","journal-title":"Futur Gener Comput Syst"},{"issue":"1","key":"1092_CR28","doi-asserted-by":"publisher","first-page":"47","DOI":"10.1093\/comjnl\/bxx032","volume":"61","author":"J-B Wang","year":"2018","unstructured":"Wang J-B, Li L (2018) Machine scheduling with deteriorating jobs and modifying maintenance activities. Comput J 61(1):47\u201353","journal-title":"Comput J"},{"issue":"1","key":"1092_CR29","doi-asserted-by":"publisher","first-page":"104918","DOI":"10.1016\/j.cor.2020.104918","volume":"118","author":"S Wang","year":"2020","unstructured":"Wang S, Ruochen W, Chu F, Jianbo Yu (2020) Identical parallel machine scheduling with assurance of maximum waiting time for an emergency job. Comput Op Res 118(1):104918","journal-title":"Comput Op Res"},{"issue":"3","key":"1092_CR30","doi-asserted-by":"publisher","first-page":"471","DOI":"10.1080\/0305215X.2021.1876041","volume":"54","author":"J-B Wang","year":"2022","unstructured":"Wang J-B, Jing-Xiao X, Guo F, Liu M (2022) Single-machine scheduling problems with job rejection, deterioration effects and past-sequence-dependent setup times. Eng Optim 54(3):471\u2013486","journal-title":"Eng Optim"},{"key":"1092_CR31","doi-asserted-by":"publisher","first-page":"89964","DOI":"10.1109\/ACCESS.2020.2993857","volume":"8","author":"Q Wei","year":"2020","unstructured":"Wei Q, Yong W (2020) Dynamic programming algorithms for two-machine hybrid flow-shop scheduling with a given job sequence and deadline. IEEE Access 8:89964\u201389975","journal-title":"IEEE Access"},{"issue":"2","key":"1092_CR32","doi-asserted-by":"publisher","first-page":"478","DOI":"10.1007\/s11424-015-3330-y","volume":"29","author":"Q Wei","year":"2016","unstructured":"Wei Q, Kang L, Shan E (2016) Batching scheduling in a two-level supply chain with earliness and tardiness penalties. J Syst Sci Complexity 29(2):478\u2013498","journal-title":"J Syst Sci Complexity"},{"issue":"2","key":"1092_CR33","doi-asserted-by":"publisher","first-page":"183","DOI":"10.1080\/07408170304382","volume":"35","author":"F Yalaoui","year":"2003","unstructured":"Yalaoui F, Chu C (2003) An efficient heuristic approach for parallel machine scheduling with job splitting and sequence-dependent setup times. IIE Trans 35(2):183\u2013190","journal-title":"IIE Trans"},{"issue":"1","key":"1092_CR34","doi-asserted-by":"publisher","first-page":"1795","DOI":"10.1007\/s10845-010-0483-3","volume":"23","author":"K-C Ying","year":"2012","unstructured":"Ying K-C, Lee Z-J, Lin S-W (2012) Makespan minimization for scheduling unrelated parallel machines with setup times. J Intell Manuf 23(1):1795\u20131803","journal-title":"J Intell Manuf"},{"issue":"3","key":"1092_CR35","doi-asserted-by":"publisher","first-page":"261","DOI":"10.1080\/05695557908974469","volume":"11","author":"T Yoshida","year":"1979","unstructured":"Yoshida T, Hitomi K (1979) Optimal two-stage production scheduling with setup times separated. AIIE Trans 11(3):261\u2013263","journal-title":"AIIE Trans"},{"issue":"6","key":"1092_CR36","doi-asserted-by":"publisher","first-page":"967","DOI":"10.1080\/01605682.2019.1595190","volume":"71","author":"A Zandi","year":"2020","unstructured":"Zandi A, Ramezanian R, Monplaisir L (2020) Green parallel machines scheduling problem: a bi-objective model and a heuristic algorithm to obtain pareto frontier. J Op Res Soc 71(6):967\u2013978","journal-title":"J Op Res Soc"},{"key":"1092_CR37","doi-asserted-by":"crossref","unstructured":"Zhang Q, Tian Z, Wang S, Liu S (2020) Iterated greedy algorithm for solving a hybrid flow shop scheduling problem with reentrant jobs. In: Chinese Control And Decision Conference. pp 5636\u20135641","DOI":"10.1109\/CCDC49329.2020.9164464"},{"issue":"4","key":"1092_CR38","doi-asserted-by":"publisher","first-page":"146","DOI":"10.1007\/s40314-022-01851-0","volume":"41","author":"S Zhao","year":"2022","unstructured":"Zhao S (2022) Scheduling jobs with general truncated learning effects including proportional setup times. Comput Appl Math 41(4):146","journal-title":"Comput Appl Math"}],"container-title":["Operational Research"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s12351-026-01092-7.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s12351-026-01092-7","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s12351-026-01092-7.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,7,25]],"date-time":"2026-07-25T14:17:31Z","timestamp":1784989051000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s12351-026-01092-7"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026,7,25]]},"references-count":38,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2026,12]]}},"alternative-id":["1092"],"URL":"https:\/\/doi.org\/10.1007\/s12351-026-01092-7","relation":{},"ISSN":["1109-2858","1866-1505"],"issn-type":[{"value":"1109-2858","type":"print"},{"value":"1866-1505","type":"electronic"}],"subject":[],"published":{"date-parts":[[2026,7,25]]},"assertion":[{"value":"28 August 2024","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"10 March 2026","order":2,"name":"revised","label":"Revised","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"3 July 2026","order":3,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"25 July 2026","order":4,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"No conflict of interest.","order":1,"name":"Ethics","label":"Conflict of interest","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"No humans and\/or animals were used in this research.","order":2,"name":"Ethics","label":"Human and animal rights","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"This publication has emanated from research conducted with the financial support of Research Ireland under grants 12\/RC\/2289\\_P2 and 23\/RC\/13506. For the purpose of open access, the author has applied a CC BY public copyright licence to any Author Accepted Manuscript version arising from this submission.","order":3,"name":"Ethics","label":"Acknowledgement","group":{"name":"EthicsHeading","label":"Declarations"}}],"article-number":"104"}}