{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,23]],"date-time":"2026-04-23T20:34:57Z","timestamp":1776976497132,"version":"3.51.4"},"reference-count":32,"publisher":"MDPI AG","issue":"4","license":[{"start":{"date-parts":[[2022,3,22]],"date-time":"2022-03-22T00:00:00Z","timestamp":1647907200000},"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>This paper addresses the two-stage hybrid flow shop scheduling problem with a batch processor in the first stage and a discrete processor in the second stage. Incompatible job families and limited buffer size are considered. This hybrid flow shop configuration commonly appears in manufacturing operations and the batch processor is always the bottleneck which breaks the symmetry of processing time. Since making a real-time high-quality schedule is challenging, we focus on the automatic design of efficient heuristics for this two-stage problem based on the genetic programming method. We develop a hyper-heuristic approach to automate the tedious trial-and-error design process of heuristics. The goal is to generate efficient dispatching rules for identifying complete schedules to minimize the total completion time. A genetic programming with cooperative co-evolution approach is proposed to evolve the schedule policy automatically. Numerical results demonstrate that the proposed approach outperforms both the constructive heuristic and meta-heuristic algorithms, and is capable of producing high-quality schedules within seconds.<\/jats:p>","DOI":"10.3390\/sym14040632","type":"journal-article","created":{"date-parts":[[2022,3,22]],"date-time":"2022-03-22T23:30:23Z","timestamp":1647991823000},"page":"632","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":10,"title":["Automatic Design of Efficient Heuristics for Two-Stage Hybrid Flow Shop Scheduling"],"prefix":"10.3390","volume":"14","author":[{"given":"Lingxuan","family":"Liu","sequence":"first","affiliation":[{"name":"Academy for Advanced Interdisciplinary Studies, Peking University, Beijing 100871, China"}]},{"given":"Leyuan","family":"Shi","sequence":"additional","affiliation":[{"name":"Department of Industrial & Systems Engineering, University of Wisconsin-Madison, Madison, WI 53706, USA"}]}],"member":"1968","published-online":{"date-parts":[[2022,3,22]]},"reference":[{"key":"ref_1","doi-asserted-by":"crossref","first-page":"990","DOI":"10.1007\/s00170-005-2585-1","article-title":"A literature review, classification and simple meta-analysis on scheduling of batch processors in semiconductor","volume":"29","author":"Mathirajan","year":"2006","journal-title":"Int. J. Adv. Manuf. Technol."},{"key":"ref_2","doi-asserted-by":"crossref","first-page":"287","DOI":"10.1016\/S0167-5060(08)70356-X","article-title":"Optimization and approximation in deterministic sequencing and scheduling: A survey","volume":"Volume 5","author":"Graham","year":"1979","journal-title":"Annals of Discrete Mathematics"},{"key":"ref_3","doi-asserted-by":"crossref","first-page":"3217","DOI":"10.1080\/00207543.2016.1268730","article-title":"Flow shop scheduling with a batch processor and limited buffer","volume":"55","author":"Zhang","year":"2017","journal-title":"Int. J. Prod. Res."},{"key":"ref_4","doi-asserted-by":"crossref","first-page":"750","DOI":"10.1287\/opre.40.4.750","article-title":"Batching and scheduling jobs on batch and discrete processors","volume":"40","author":"Ahmadi","year":"1992","journal-title":"Oper. Res."},{"key":"ref_5","doi-asserted-by":"crossref","first-page":"110","DOI":"10.1109\/TEVC.2015.2429314","article-title":"Automated design of production scheduling heuristics: A review","volume":"20","author":"Branke","year":"2015","journal-title":"IEEE Trans. Evol. Comput."},{"key":"ref_6","doi-asserted-by":"crossref","first-page":"503","DOI":"10.1142\/S0217595909002328","article-title":"A two-stage flowshop scheduling with limited buffer storage","volume":"26","author":"Su","year":"2009","journal-title":"Asia-Pac. J. Oper. Res."},{"key":"ref_7","doi-asserted-by":"crossref","first-page":"2267","DOI":"10.1080\/00207543.2011.565813","article-title":"Optimisation of flow-shop scheduling with batch processor and limited buffer","volume":"50","author":"Fu","year":"2012","journal-title":"Int. J. Prod. Res."},{"key":"ref_8","unstructured":"Shi, Z., Huang, Z., and Shi, L. (2016, January 21\u201325). Two-stage flow shop with a batch processor and limited buffer. Proceedings of the 2016 IEEE International Conference on Automation Science and Engineering (CASE), Fort Worth, TX, USA."},{"key":"ref_9","doi-asserted-by":"crossref","first-page":"14002","DOI":"10.1051\/matecconf\/201819714002","article-title":"Three-stage flow-shop scheduling model with batch processing machine and discrete processing machine","volume":"Volume 197","author":"Mauluddin","year":"2018","journal-title":"MATEC Web of Conferences"},{"key":"ref_10","unstructured":"Ross, H.L.F.P., and Corne, D. (1994, January 8\u201312). A promising hybrid GA\/heuristic approach for open-shop scheduling problems. Proceedings of the 11th European Conference on Artificial Intelligence, Amsterdam, The Netherlands."},{"key":"ref_11","unstructured":"Rodr\u00edguez, J.V., Petrovic, S., and Salhi, A. (2007, January 28\u201331). A combined meta-heuristic with hyper-heuristic approach to the scheduling of the hybrid flow shop with sequence dependent setup times and uniform machines. Proceedings of the 3rd Multidisciplinary International Conference on Scheduling: Theory and Applications, MISTA, Paris, France."},{"key":"ref_12","doi-asserted-by":"crossref","first-page":"177","DOI":"10.1016\/j.ejor.2005.08.012","article-title":"A graph-based hyper-heuristic for educational timetabling problems","volume":"176","author":"Burke","year":"2007","journal-title":"Eur. J. Oper. Res."},{"key":"ref_13","doi-asserted-by":"crossref","unstructured":"Sim, K., Hart, E., and Paechter, B. (2012, January 1\u20135). A hyper-heuristic classifier for one dimensional bin packing problems: Improving classification accuracy by attribute evolution. Proceedings of the International Conference on Parallel Problem Solving from Nature, Taormina, Italy.","DOI":"10.1007\/978-3-642-32964-7_35"},{"key":"ref_14","doi-asserted-by":"crossref","unstructured":"Runka, A. (2009, January 8\u201312). Evolving an edge selection formula for ant colony optimization. Proceedings of the 11th Annual Conference on Genetic and Evolutionary Computation, Montreal, QC, USA.","DOI":"10.1145\/1569901.1570046"},{"key":"ref_15","doi-asserted-by":"crossref","first-page":"205","DOI":"10.1007\/s12293-009-0022-y","article-title":"Evolving timetabling heuristics using a grammar-based genetic programming hyper-heuristic framework","volume":"1","author":"Poli","year":"2009","journal-title":"Memetic Comput."},{"key":"ref_16","unstructured":"Koza, J.R. (1994). Genetic Programming II: Automatic Discovery of Reusable Subprograms, MIT Press."},{"key":"ref_17","unstructured":"Miyashita, K. (2000, January 10\u201312). Job-shop scheduling with genetic programming. Proceedings of the 2nd Annual Conference on Genetic and Evolutionary Computation, Las Vegas, NV, USA."},{"key":"ref_18","doi-asserted-by":"crossref","first-page":"489","DOI":"10.1016\/S0965-9978(00)00109-5","article-title":"Investigating the use of genetic programming for a classic one-machine scheduling problem","volume":"32","author":"Dimopoulos","year":"2001","journal-title":"Adv. Eng. Softw."},{"key":"ref_19","doi-asserted-by":"crossref","first-page":"7","DOI":"10.1007\/s10951-006-5591-8","article-title":"Rapid modeling and discovery of priority dispatching rules: An autonomous learning approach","volume":"9","author":"Geiger","year":"2006","journal-title":"J. Sched."},{"key":"ref_20","doi-asserted-by":"crossref","first-page":"1431","DOI":"10.1080\/00207540600993360","article-title":"Learning effective dispatching rules for batch processor scheduling","volume":"46","author":"Geiger","year":"2008","journal-title":"Int. J. Prod. Res."},{"key":"ref_21","doi-asserted-by":"crossref","unstructured":"Hildebrandt, T., Goswami, D., and Freitag, M. (2014, January 7\u201310). Large-scale simulation-based optimization of semiconductor dispatching rules. Proceedings of the Winter Simulation Conference 2014, Savannah, GA, USA.","DOI":"10.1109\/WSC.2014.7020102"},{"key":"ref_22","doi-asserted-by":"crossref","unstructured":"Shi, Z., Gao, S., Du, J., Ma, H., and Shi, L. (2019, January 14\u201316). Automatic design of dispatching rules for real-time optimization of complex production systems. Proceedings of the 2019 IEEE\/SICE International Symposium on System Integration (SII), Paris, France.","DOI":"10.1109\/SII.2019.8700391"},{"key":"ref_23","doi-asserted-by":"crossref","unstructured":"Nguyen, S., Zhang, M., Johnston, M., and Tan, K.C. (2019). Genetic programming for job shop scheduling. Evolutionary and Swarm Intelligence Algorithms, Springer.","DOI":"10.26686\/wgtn.13158287.v1"},{"key":"ref_24","doi-asserted-by":"crossref","unstructured":"Park, J., Nguyen, S., Zhang, M., and Johnston, M. (2013, January 20\u201323). Genetic programming for order acceptance and scheduling. Proceedings of the 2013 IEEE Congress on Evolutionary Computation, Canc\u00fan, Mexico.","DOI":"10.1109\/CEC.2013.6557677"},{"key":"ref_25","doi-asserted-by":"crossref","first-page":"193","DOI":"10.1109\/TEVC.2013.2248159","article-title":"Automatic design of scheduling policies for dynamic multi-objective job shop scheduling via cooperative coevolution genetic programming","volume":"18","author":"Nguyen","year":"2013","journal-title":"IEEE Trans. Evol. Comput."},{"key":"ref_26","doi-asserted-by":"crossref","unstructured":"Yska, D., Mei, Y., and Zhang, M. (2018, January 4\u20136). Genetic programming hyper-heuristic with cooperative coevolution for dynamic flexible job shop scheduling. Proceedings of the European Conference on Genetic Programming, Parma, Italy.","DOI":"10.1145\/3205651.3205741"},{"key":"ref_27","doi-asserted-by":"crossref","first-page":"2685","DOI":"10.1080\/00207549508904839","article-title":"Scheduling batch processing machines with incompatible job families","volume":"33","author":"Uzsoy","year":"1995","journal-title":"Int. J. Prod. Res."},{"key":"ref_28","doi-asserted-by":"crossref","unstructured":"Burke, E.K., Hyde, M.R., Kendall, G., Ochoa, G., Ozcan, E., and Woodward, J.R. (2009). Exploring hyper-heuristic methodologies with genetic programming. Computational Intelligence, Springer.","DOI":"10.1007\/978-3-642-01799-5_6"},{"key":"ref_29","unstructured":"Luke, S. (2021, October 01). Essentials of Metaheuristics. Available online: http:\/\/cs.gmu.edu\/sean\/book\/metaheuristics\/."},{"key":"ref_30","unstructured":"Wieg, R.P., Liles, W.C., and De Jong, K.A. (2001, January 7\u201311). An empirical analysis of collaboration methods in cooperative coevolutionary algorithms. Proceedings of the Genetic and Evolutionary Computation Conference (GECCO), San Francisco, CA, USA."},{"key":"ref_31","doi-asserted-by":"crossref","unstructured":"Hunt, R., Johnston, M., and Zhang, M. (2014, January 12\u201316). Evolving \u201cless-myopic\u201d scheduling rules for dynamic job shop scheduling with genetic programming. Proceedings of the 2014 Annual Conference on Genetic and Evolutionary Computation, Vancouver, BC, Canada.","DOI":"10.1145\/2576768.2598224"},{"key":"ref_32","doi-asserted-by":"crossref","first-page":"631","DOI":"10.1080\/15458830.1996.11770708","article-title":"Ranking dispatching rules by data envelopment analysis in a job shop environment","volume":"28","author":"Chang","year":"1996","journal-title":"IIE Trans."}],"container-title":["Symmetry"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/2073-8994\/14\/4\/632\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,10]],"date-time":"2025-10-10T22:40:46Z","timestamp":1760136046000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/2073-8994\/14\/4\/632"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,3,22]]},"references-count":32,"journal-issue":{"issue":"4","published-online":{"date-parts":[[2022,4]]}},"alternative-id":["sym14040632"],"URL":"https:\/\/doi.org\/10.3390\/sym14040632","relation":{},"ISSN":["2073-8994"],"issn-type":[{"value":"2073-8994","type":"electronic"}],"subject":[],"published":{"date-parts":[[2022,3,22]]}}}