{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,19]],"date-time":"2026-02-19T23:19:11Z","timestamp":1771543151189,"version":"3.50.1"},"reference-count":47,"publisher":"MDPI AG","issue":"5","license":[{"start":{"date-parts":[[2022,4,29]],"date-time":"2022-04-29T00:00:00Z","timestamp":1651190400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Symmetry"],"abstract":"<jats:p>The No-wait Flowshop Scheduling Problem (NWFSP) has always been a research hotspot because of its importance in various industries. This paper uses a matheuristic approach that combines exact and heuristic algorithms to solve it with the objective to minimize the makespan. Firstly, according to the symmetry characteristics in NWFSP, a local search method is designed, where the first job and the last job in the symmetrical position remain unchanged, and then, a three-level neighborhood division method and the corresponding rapid evaluation method at each level are given. The two proposed heuristic algorithms are built on them, which can effectively avoid al-ready searched areas, so as to quickly obtain the local optimal solutions, and even directly obtain the optimal solutions for small-scale instances. Secondly, using the equivalence of this problem and the Asymmetric Traveling Salesman Problem (ATSP), an exact method for solving NWFSP is constructed. Importing the results of the heuristics into the model, the efficiency of the Mil-ler-Tucker-Zemlin (MTZ) model for solving small-scale NWFSP can be improved. Thirdly, the matheuristic algorithm is used to test 141 instances of the Tailard and Reeves benchmarks, and each optimal solution can be obtained within 134 s, which verifies the stability and effectiveness of the algorithm.<\/jats:p>","DOI":"10.3390\/sym14050913","type":"journal-article","created":{"date-parts":[[2022,5,4]],"date-time":"2022-05-04T08:21:25Z","timestamp":1651652485000},"page":"913","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":7,"title":["A Matheuristic Approach for the No-Wait Flowshop Scheduling Problem with Makespan Criterion"],"prefix":"10.3390","volume":"14","author":[{"given":"Yu","family":"Gao","sequence":"first","affiliation":[{"name":"School of Mechanical Science and Engineering, Huazhong University of Science and Technology, Wuhan 430074, China"},{"name":"School of Physics and Electronic Science, Hubei Normal University, Huangshi 435002, China"}]},{"given":"Ziyue","family":"Wang","sequence":"additional","affiliation":[{"name":"School of Mechanical Science and Engineering, Huazhong University of Science and Technology, Wuhan 430074, China"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-1485-0722","authenticated-orcid":false,"given":"Liang","family":"Gao","sequence":"additional","affiliation":[{"name":"School of Mechanical Science and Engineering, Huazhong University of Science and Technology, Wuhan 430074, China"}]},{"given":"Xinyu","family":"Li","sequence":"additional","affiliation":[{"name":"School of Mechanical Science and Engineering, Huazhong University of Science and Technology, Wuhan 430074, China"}]}],"member":"1968","published-online":{"date-parts":[[2022,4,29]]},"reference":[{"key":"ref_1","doi-asserted-by":"crossref","first-page":"92","DOI":"10.35378\/gujs.682388","article-title":"Genetic algorithm application for permutation flow shop scheduling problems","volume":"35","author":"Arik","year":"2022","journal-title":"Gazi Univ. J. Sci."},{"key":"ref_2","first-page":"15","article-title":"An effective new heuristic algorithm for solving permutation flow shop scheduling problem","volume":"11","author":"Red","year":"2022","journal-title":"Trans. Comb."},{"key":"ref_3","doi-asserted-by":"crossref","first-page":"12","DOI":"10.1186\/s10033-022-00683-7","article-title":"Integrated production and transportation scheduling method in hybrid flow shop","volume":"35","author":"Li","year":"2022","journal-title":"Chin. J. Mech. Eng."},{"key":"ref_4","doi-asserted-by":"crossref","first-page":"5","DOI":"10.2507\/IJSIMM21-1-577","article-title":"Two-stage hybrid flowshop scheduling problem with independent setup times","volume":"21","author":"Jemmali","year":"2022","journal-title":"Int. J. Simul. Model."},{"key":"ref_5","doi-asserted-by":"crossref","first-page":"1809","DOI":"10.1007\/s10845-017-1350-2","article-title":"Review of job shop scheduling research and its new perspectives under industry 4.0","volume":"30","author":"Zhang","year":"2019","journal-title":"J. Intell. Manuf."},{"key":"ref_6","doi-asserted-by":"crossref","unstructured":"Sun, Y., Pan, J.S., Hu, P., and Chu, S.C. (2022). Enhanced equilibrium optimizer algorithm applied in job shop scheduling problem. J. Intell. Manuf., Available online: https:\/\/www.webofscience.com\/wos\/alldb\/full-record\/WOS:000739739300001.","DOI":"10.1007\/s10845-021-01899-5"},{"key":"ref_7","doi-asserted-by":"crossref","first-page":"107077","DOI":"10.1016\/j.cie.2020.107077","article-title":"Open-shop production scheduling with reverse flows","volume":"153","author":"Aghighi","year":"2021","journal-title":"Comput. Ind. Eng."},{"key":"ref_8","doi-asserted-by":"crossref","first-page":"291","DOI":"10.1007\/s10100-019-00630-3","article-title":"Dynamic programming approach for solving the open shop problem","volume":"29","author":"Ozolins","year":"2021","journal-title":"Cent. Europ. J. Oper. Res."},{"key":"ref_9","unstructured":"Callahan, J.R. (1971). The Nothing Hot Delay Problems in the Production of Steel. [Ph.D. Dissertation, Department of Mechanical & Industrial Engineering, Toronto University]."},{"key":"ref_10","doi-asserted-by":"crossref","first-page":"979","DOI":"10.1080\/0951192X.2010.506655","article-title":"Discrete particle swarm optimisation combined with no-wait algorithm in stages for scheduling mill roller annealing process","volume":"23","author":"Tang","year":"2010","journal-title":"Int. J. Comput. Integr. Manuf."},{"key":"ref_11","doi-asserted-by":"crossref","first-page":"295","DOI":"10.1007\/s10951-011-0241-1","article-title":"On Eulerian extensions and their application to no-wait flowshop scheduling","volume":"15","author":"Jacobs","year":"2012","journal-title":"J. Sched."},{"key":"ref_12","doi-asserted-by":"crossref","first-page":"498282","DOI":"10.1155\/2013\/498282","article-title":"Optimal research and numerical simulation for scheduling No-Wait Flow Shop in steel production","volume":"2013","author":"Yuan","year":"2013","journal-title":"J. Appl. Math."},{"key":"ref_13","first-page":"119","article-title":"Review of scheduling of process operations","volume":"78","author":"Reklaitis","year":"1982","journal-title":"AIChE Symp. Ser."},{"key":"ref_14","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_15","doi-asserted-by":"crossref","unstructured":"Babor, M., Senge, J., Rosell, C.M., Rodrigo, D., and Hitzmann, B. (2021). Optimization of No-Wait Flowshop Scheduling Problem in Bakery Production with Modified PSO, NEH and SA. Processes, 9.","DOI":"10.3390\/pr9112044"},{"key":"ref_16","doi-asserted-by":"crossref","first-page":"218","DOI":"10.1002\/nav.10060","article-title":"Scheduling patients in an ambulatory surgical center","volume":"50","author":"Hsu","year":"2003","journal-title":"Nav. Res. Logist."},{"key":"ref_17","doi-asserted-by":"crossref","first-page":"1026","DOI":"10.1287\/opre.1080.0642","article-title":"Optimal real-time traffic control in metro stations","volume":"57","author":"Mannino","year":"2009","journal-title":"Oper. Res."},{"key":"ref_18","doi-asserted-by":"crossref","first-page":"113556","DOI":"10.1016\/j.eswa.2020.113556","article-title":"A comprehensive review of Branch-and-Bound algorithms: Guidelines and directions for further research on the flowshop scheduling problem","volume":"158","author":"Tomazella","year":"2020","journal-title":"Expert Syst. Appl."},{"key":"ref_19","first-page":"287","article-title":"Optimization and approximation in deterministic sequencing and scheduling: A survey","volume":"5","author":"Graham","year":"1979","journal-title":"Ann. Math."},{"key":"ref_20","unstructured":"Garey, M.R., and Johnson, D.S. (1979). Computers and Intractability: A guide to the Theory of NP-Completeness, W.H. Freeman and Company."},{"key":"ref_21","doi-asserted-by":"crossref","first-page":"533","DOI":"10.1145\/322203.322213","article-title":"Flowshop scheduling with limited temporary storage","volume":"27","author":"Papadimitriou","year":"1980","journal-title":"J. ACM"},{"key":"ref_22","doi-asserted-by":"crossref","first-page":"869","DOI":"10.1057\/jors.1976.176","article-title":"Solutions to the constrained flowshop sequencing problem","volume":"27","author":"Bonney","year":"1976","journal-title":"J. Oper. Res. Soc."},{"key":"ref_23","doi-asserted-by":"crossref","first-page":"343","DOI":"10.1080\/00207548008919673","article-title":"Heuristics for flowshop scheduling","volume":"18","author":"King","year":"1980","journal-title":"Int. J. Prod. Res."},{"key":"ref_24","doi-asserted-by":"crossref","first-page":"285","DOI":"10.1016\/0925-5273(93)90042-J","article-title":"Heuristic algorithms for scheduling in the no-wait flowshop","volume":"32","author":"Gangadharan","year":"1993","journal-title":"Int. J. Prod. Econ."},{"key":"ref_25","doi-asserted-by":"crossref","first-page":"97","DOI":"10.1007\/s00170-008-1454-0","article-title":"A constructive heuristic for minimizing makespan in no-wait flow shop scheduling","volume":"41","author":"Laha","year":"2009","journal-title":"Int. J. Adv. Manuf. Technol."},{"key":"ref_26","doi-asserted-by":"crossref","first-page":"30702","DOI":"10.1109\/ACCESS.2018.2834954","article-title":"Improved exact methods for solving no-wait flowshop scheduling problems with due date constraints","volume":"6","author":"Ying","year":"2018","journal-title":"IEEE Access"},{"key":"ref_27","doi-asserted-by":"crossref","first-page":"497","DOI":"10.2307\/1910129","article-title":"An automatic method of solving discrete programming problems","volume":"28","author":"Land","year":"1960","journal-title":"Econometrica"},{"key":"ref_28","doi-asserted-by":"crossref","first-page":"487","DOI":"10.1080\/00207543.2019.1597291","article-title":"A column generation-based approach for proportionate flexible two-stage no-wait job shop scheduling","volume":"58","author":"Pei","year":"2020","journal-title":"Int. J. Prod. Res."},{"key":"ref_29","doi-asserted-by":"crossref","first-page":"665","DOI":"10.1016\/j.ejor.2016.05.036","article-title":"A survey of scheduling problems with no-wait in process","volume":"255","author":"Allahverdi","year":"2016","journal-title":"Eur. J. Oper. Res."},{"key":"ref_30","doi-asserted-by":"crossref","first-page":"337","DOI":"10.1007\/s00170-007-1099-4","article-title":"A hybrid discrete particle swarm optimization algorithm for the no-wait flow shop scheduling problem with makespan criterion","volume":"38","author":"Pan","year":"2008","journal-title":"Int. J. Adv. Manuf. Technol."},{"key":"ref_31","doi-asserted-by":"crossref","first-page":"166","DOI":"10.1016\/j.asoc.2018.08.002","article-title":"A new hybrid ant colony optimization algorithm for solving the no-wait flow shop scheduling problems","volume":"72","author":"Engin","year":"2018","journal-title":"Appl. Soft. Comput."},{"key":"ref_32","doi-asserted-by":"crossref","first-page":"347","DOI":"10.1016\/j.eswa.2017.09.028","article-title":"A discrete water wave optimization algorithm for no-wait flow shop scheduling problem","volume":"91","author":"Zhao","year":"2018","journal-title":"Expert Syst. Appl."},{"key":"ref_33","doi-asserted-by":"crossref","first-page":"41","DOI":"10.1016\/j.eswa.2019.01.084","article-title":"A factorial based particle swarm optimization with a population adaptation mechanism for the no-wait flow shop scheduling problem with the makespan objective","volume":"126","author":"Zhao","year":"2019","journal-title":"Expert Syst. Appl."},{"key":"ref_34","doi-asserted-by":"crossref","first-page":"1727","DOI":"10.1080\/0305215X.2018.1542693","article-title":"An improved water wave optimization algorithm with the single wave mechanism for the no-wait flow-shop scheduling problem","volume":"51","author":"Zhao","year":"2019","journal-title":"Eng. Optimiz."},{"key":"ref_35","doi-asserted-by":"crossref","first-page":"321","DOI":"10.1016\/j.eswa.2019.02.023","article-title":"A hybrid biogeography-based optimization with variable neighborhood search mechanism for no-wait flow shop scheduling problem","volume":"126","author":"Zhao","year":"2019","journal-title":"Expert Syst. Appl."},{"key":"ref_36","doi-asserted-by":"crossref","first-page":"791","DOI":"10.1007\/s10489-018-1285-0","article-title":"Quantum-inspired cuckoo co-search algorithm for no-wait flow shop scheduling","volume":"49","author":"Zhu","year":"2019","journal-title":"Appl. Intell."},{"key":"ref_37","doi-asserted-by":"crossref","first-page":"99380","DOI":"10.1109\/ACCESS.2020.2997379","article-title":"An improved discrete migrating birds optimization algorithm for the no-wait flow shop scheduling problem","volume":"8","author":"Zhang","year":"2020","journal-title":"IEEE Access"},{"key":"ref_38","first-page":"4731012","article-title":"Solving no-wait flow shop scheduling problem based on discrete wolf pack algorithm","volume":"2021","author":"Lai","year":"2021","journal-title":"Sci. Program."},{"key":"ref_39","doi-asserted-by":"crossref","first-page":"451","DOI":"10.1023\/B:HEUR.0000012446.94732.b6","article-title":"A tabu-search hyperheuristic for timetabling and rostering","volume":"9","author":"Burke","year":"2003","journal-title":"J. Heuristics"},{"key":"ref_40","doi-asserted-by":"crossref","first-page":"185","DOI":"10.1007\/s10479-012-1235-x","article-title":"A variable neighborhood search based matheuristic for nurse rostering problems","volume":"218","author":"Salassa","year":"2014","journal-title":"Ann. Oper. Res."},{"key":"ref_41","doi-asserted-by":"crossref","first-page":"523","DOI":"10.1016\/j.ejor.2014.12.009","article-title":"A matheuristic approach for the Pollution-Routing Problem","volume":"243","author":"Kramer","year":"2015","journal-title":"Eur. J. Oper. Res."},{"key":"ref_42","doi-asserted-by":"crossref","first-page":"623","DOI":"10.1080\/00207543.2021.1975839","article-title":"An iterated greedy matheuristic for scheduling in steelmaking-continuous casting process","volume":"60","author":"Hong","year":"2021","journal-title":"Int. J. Prod. Res."},{"key":"ref_43","doi-asserted-by":"crossref","first-page":"115","DOI":"10.1016\/j.omega.2015.12.002","article-title":"Optimization of makespan for no-wait flowshop scheduling problems using efficient matheuristics","volume":"64","author":"Lin","year":"2016","journal-title":"Omega-Int. J. Manag. Sci."},{"key":"ref_44","doi-asserted-by":"crossref","first-page":"816","DOI":"10.1016\/j.ejor.2004.06.040","article-title":"A review of TSP based approaches for flowshop scheduling","volume":"169","author":"Bagchi","year":"2006","journal-title":"Eur. J. Oper. Res."},{"key":"ref_45","doi-asserted-by":"crossref","first-page":"106","DOI":"10.1016\/S0377-2217(99)00284-2","article-title":"An effective implementation of the Lin-Kernighan traveling salesman heuristic","volume":"126","author":"Helsgaun","year":"2000","journal-title":"Eur. J. Oper. Res."},{"key":"ref_46","doi-asserted-by":"crossref","first-page":"134","DOI":"10.1016\/S0377-2217(97)00358-5","article-title":"The asymmetric travelling salesman problem and a reformulation of the Miller-Tucker-Zemlin constraints","volume":"112","author":"Gouveia","year":"1999","journal-title":"Eur. J. Oper. Res."},{"key":"ref_47","doi-asserted-by":"crossref","first-page":"113229","DOI":"10.1016\/j.eswa.2020.113229","article-title":"Accelerating the Miller-Tucker-Zemlin model for the asymmetric traveling salesman problem","volume":"148","author":"Campuzano","year":"2020","journal-title":"Expert Syst. Appl."}],"container-title":["Symmetry"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/2073-8994\/14\/5\/913\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,10]],"date-time":"2025-10-10T23:04:29Z","timestamp":1760137469000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/2073-8994\/14\/5\/913"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,4,29]]},"references-count":47,"journal-issue":{"issue":"5","published-online":{"date-parts":[[2022,5]]}},"alternative-id":["sym14050913"],"URL":"https:\/\/doi.org\/10.3390\/sym14050913","relation":{},"ISSN":["2073-8994"],"issn-type":[{"value":"2073-8994","type":"electronic"}],"subject":[],"published":{"date-parts":[[2022,4,29]]}}}