{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,28]],"date-time":"2025-10-28T10:53:45Z","timestamp":1761648825431,"version":"build-2065373602"},"reference-count":34,"publisher":"MDPI AG","issue":"11","license":[{"start":{"date-parts":[[2020,10,31]],"date-time":"2020-10-31T00:00:00Z","timestamp":1604102400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"DOI":"10.13039\/501100001659","name":"Deutsche Forschungsgemeinschaft","doi-asserted-by":"publisher","award":["276879186\/GRK2193"],"award-info":[{"award-number":["276879186\/GRK2193"]}],"id":[{"id":"10.13039\/501100001659","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithms"],"abstract":"<jats:p>In modern production systems, scheduling problems have to be solved in consideration of frequently changing demands and varying production parameters. This paper presents a approach combining forecasting and classification techniques to predict uncertainty from demands, and production data with heuristics, metaheuristics, and discrete event simulation for obtaining machine schedules. The problem is a hybrid flow shop with two stages, machine qualifications, skipping stages, and uncertainty in demands. The objective is to minimize the makespan. First, based on the available data of past orders, jobs that are prone to fluctuations just before or during the production phase are identified by clustering algorithms, and production volumes are adjusted accordingly. Furthermore, the distribution of scrap rates is estimated, and the quantiles of the resulting distribution are used to increase corresponding production volumes to prevent costly rescheduling resulting from unfulfilled demands. Second, Shortest Processing Time (SPT), tabu search, and local search algorithms are developed and applied. Third, the best performing schedules are evaluated and selected using a detailed simulation model. The proposed approach is validated on a real-world production case. The results show that the price for a very robust schedule that avoids underproduction with a high probability can significantly increase the makespan.<\/jats:p>","DOI":"10.3390\/a13110277","type":"journal-article","created":{"date-parts":[[2020,10,31]],"date-time":"2020-10-31T21:39:56Z","timestamp":1604180396000},"page":"277","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":6,"title":["Scheduling Algorithms for a Hybrid Flow Shop under Uncertainty"],"prefix":"10.3390","volume":"13","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-9847-0443","authenticated-orcid":false,"given":"Christin","family":"Schumacher","sequence":"first","affiliation":[{"name":"Informatik 4\u2014Modeling and Simulation, Department of Computer Science, TU Dortmund University, D-44221 Dortmund, Germany"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-9966-7686","authenticated-orcid":false,"given":"Peter","family":"Buchholz","sequence":"additional","affiliation":[{"name":"Informatik 4\u2014Modeling and Simulation, Department of Computer Science, TU Dortmund University, D-44221 Dortmund, Germany"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"1968","published-online":{"date-parts":[[2020,10,31]]},"reference":[{"key":"ref_1","doi-asserted-by":"crossref","unstructured":"Borshchev, A., and Grigoryev, I. (2014). The Big Book of Simulation Modeling, AnyLogic.","DOI":"10.1002\/9781118762745.ch12"},{"key":"ref_2","doi-asserted-by":"crossref","first-page":"1151","DOI":"10.1016\/j.cor.2006.07.014","article-title":"Modeling realistic hybrid flexible flowshop scheduling problems","volume":"35","author":"Ruiz","year":"2008","journal-title":"Comput. Oper. Res."},{"key":"ref_3","doi-asserted-by":"crossref","first-page":"87","DOI":"10.1016\/j.endm.2018.03.012","article-title":"A Multi-objective Variable Neighborhood Search algorithm for solving the Hybrid Flow Shop Problem","volume":"66","author":"Souza","year":"2018","journal-title":"Electron. Notes Discret. Math."},{"key":"ref_4","first-page":"287","article-title":"Optimization and approximation in deterministic sequencing and scheduling: A survey","volume":"5","author":"Hammer","year":"1979","journal-title":"Annals of Discrete Mathematics, Proceedings of the Advanced Research Institute on Discrete Optimization and Systems Applications of the Systems Science Panel of NATO and of the Discrete Optimization Symposium Co-Sponsored by IBM Canada and SIAM Banff, Aha, Vancouver, BC, Canada, 1\u201331 August 1977"},{"key":"ref_5","unstructured":"Pinedo, M. (2016). Scheduling: Theory, Algorithms, and Systems, Springer. [5th ed.]."},{"key":"ref_6","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/j.ejor.2009.09.024","article-title":"The hybrid flow shop scheduling problem","volume":"205","author":"Ruiz","year":"2010","journal-title":"Eur. J. Oper. Res."},{"key":"ref_7","doi-asserted-by":"crossref","first-page":"1439","DOI":"10.1016\/j.cor.2009.11.001","article-title":"Review and classification of hybrid flow shop scheduling problems from a production system and a solutions procedure perspective","volume":"37","author":"Ribas","year":"2010","journal-title":"Comput. Oper. Res."},{"key":"ref_8","doi-asserted-by":"crossref","first-page":"2926","DOI":"10.1080\/00207543.2018.1550269","article-title":"Flow shop scheduling problems with assembly operations: A review and new trends","volume":"57","author":"Komaki","year":"2019","journal-title":"Int. J. Prod. Res."},{"key":"ref_9","doi-asserted-by":"crossref","first-page":"949","DOI":"10.1016\/j.cie.2009.03.012","article-title":"Hybrid flexible flowshops with sequence-dependent setup times and machine availability constraints","volume":"57","author":"Jabbarizadeh","year":"2009","journal-title":"Comput. Ind. Eng."},{"key":"ref_10","doi-asserted-by":"crossref","first-page":"371","DOI":"10.1016\/S0925-5273(03)00123-3","article-title":"Comparing scheduling rules for flexible flow lines","volume":"85","author":"Kurz","year":"2003","journal-title":"Int. J. Prod. Econ."},{"key":"ref_11","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."},{"key":"ref_12","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_13","doi-asserted-by":"crossref","first-page":"845","DOI":"10.1016\/j.cor.2006.04.004","article-title":"A two-stage hybrid flowshop scheduling problem with a function constraint and unrelated alternative machines","volume":"35","author":"Low","year":"2008","journal-title":"Comput. Oper. Res."},{"key":"ref_14","doi-asserted-by":"crossref","first-page":"236","DOI":"10.1016\/j.cor.2009.04.017","article-title":"Algorithms for a realistic variant of flowshop scheduling","volume":"37","author":"Naderi","year":"2010","journal-title":"Comput. Oper. Res."},{"key":"ref_15","first-page":"401","article-title":"Evolutionary algorithms for flow shop sequencing with non-unique jobs","volume":"7","author":"Burdett","year":"2000","journal-title":"Int. Trans. Oper. Res."},{"key":"ref_16","doi-asserted-by":"crossref","first-page":"411","DOI":"10.1142\/S1469026803001105","article-title":"Evolutionary Algorithms For Resource Constrained Non-Serial Mixed Flow Shops","volume":"3","author":"Burdett","year":"2003","journal-title":"Int. J. Comput. Intell. Appl."},{"key":"ref_17","doi-asserted-by":"crossref","first-page":"88","DOI":"10.1016\/j.cie.2017.10.034","article-title":"Efficient heuristics for the hybrid flow shop scheduling problem with missing operations","volume":"115","author":"Dios","year":"2018","journal-title":"Comput. Ind. Eng."},{"key":"ref_18","doi-asserted-by":"crossref","first-page":"66","DOI":"10.1016\/j.ijpe.2005.02.006","article-title":"Sequence-dependent group scheduling problems in flexible flow shops","volume":"102","author":"Logendran","year":"2006","journal-title":"Int. J. Prod. Econ."},{"key":"ref_19","doi-asserted-by":"crossref","first-page":"2083","DOI":"10.1080\/002075403010001647604","article-title":"Optimal versus heuristic scheduling of surface mount technology lines","volume":"42","author":"Kaczmarczyk","year":"2004","journal-title":"Int. J. Prod. Res."},{"key":"ref_20","unstructured":"Geiger, M.J. (2008, January 4\u20135). Randomised Variable Neighbourhood Search for Multi Objective Optimisation. Proceedings of the 4th EU\/ME Workshop: Design and Evaluation of Advanced Hybrid Meta-Heuristics, Nottingham, UK."},{"key":"ref_21","doi-asserted-by":"crossref","first-page":"88","DOI":"10.1016\/j.ijpe.2012.09.014","article-title":"A Metaheuristic Optimization Approach for a Real-world Stochastic Flexible Flowshop Problem with Limited Buffer","volume":"145","author":"Almeder","year":"2013","journal-title":"Int. J. Prod. Econ."},{"key":"ref_22","doi-asserted-by":"crossref","first-page":"16","DOI":"10.1016\/j.cie.2015.04.024","article-title":"Techniques to effectively buffer schedules in the face of uncertainties","volume":"87","author":"Burdett","year":"2015","journal-title":"Comput. Ind. Eng."},{"key":"ref_23","doi-asserted-by":"crossref","first-page":"118","DOI":"10.1016\/j.simpat.2014.03.007","article-title":"Hybrid simulation\u2013optimization methods: A taxonomy and discussion","volume":"46","author":"Figueira","year":"2014","journal-title":"Simul. Model. Pract. Theory"},{"key":"ref_24","first-page":"62","article-title":"A review of simheuristics: Extending metaheuristics to deal with stochastic combinatorial optimization problems","volume":"2","author":"Juan","year":"2015","journal-title":"Oper. Res. Perspect."},{"key":"ref_25","unstructured":"Law, A.M. (2015). Simulation Modeling and Analysis, McGraw Hill. [5th ed.]."},{"key":"ref_26","doi-asserted-by":"crossref","first-page":"1834","DOI":"10.1016\/j.ifacol.2015.06.353","article-title":"Forecasting Supply Chain Demand by Clustering Customers","volume":"48","author":"Murray","year":"2015","journal-title":"IFAC-PapersOnLine"},{"key":"ref_27","first-page":"93","article-title":"The bullwhip effect in supply chains","volume":"38","author":"Lee","year":"1997","journal-title":"Sloan Manag. Rev."},{"key":"ref_28","unstructured":"Sayed-Mouchaweh, M., and Wani, M.A. (2013, January 4\u20137). A Genetic Algorithm to Optimize Lazy Learning Parameters for the Prediction of Customer Demands. Proceedings of the 12th International Conference on Machine Learning and Applications (ICMLA), Miami, FL, USA."},{"key":"ref_29","doi-asserted-by":"crossref","first-page":"417","DOI":"10.1016\/j.cirp.2014.03.106","article-title":"Prediction of Customer Demands for Production Planning\u2014Automated Seelction and Configuration of Suitable Prediction Methods","volume":"63","author":"Lappe","year":"2014","journal-title":"CIRP Ann."},{"key":"ref_30","doi-asserted-by":"crossref","unstructured":"Schumacher, C., Buchholz, P., Fiedler, K., and Gorecki, N. (2020, January 13\u201316). Local Search and Tabu Search Algorithms for Machine Scheduling of a Hybrid Flow Shop Under Uncertainty. Proceedings of the 2020 Winter Simulation Conference, Orlando, FL, USA.","DOI":"10.1109\/WSC48552.2020.9383964"},{"key":"ref_31","doi-asserted-by":"crossref","unstructured":"Van Hentenryck, P., and Bent, R. (2006). Online Stochastic Combinatorial Optimization, MIT Press.","DOI":"10.7551\/mitpress\/5140.001.0001"},{"key":"ref_32","doi-asserted-by":"crossref","unstructured":"Juan, A.A., Panadero, J., Reyes-Rubiano, L.S., Faulin, J., de la Torre, R., and Latorre, J.I. (2019, January 8\u201311). Simulation-Based Optimization in Transportation and Logistics: Comparing Sample Average Approximation with Simheuristics. Proceedings of the 2019 Winter Simulation Conference, WSC 2019, National Harbor, MD, USA.","DOI":"10.1109\/WSC40007.2019.9004905"},{"key":"ref_33","unstructured":"Arthur, D., and Vassilvitskii, S. (2007). k-means++: The Advantages of Careful Seeding, Stanford University."},{"key":"ref_34","doi-asserted-by":"crossref","unstructured":"Leskovec, J., Rajaraman, A., and Ullman, J.D. (2014). Mining of Massive Datasets, Cambridge University Press. [2nd ed.].","DOI":"10.1017\/CBO9781139924801"}],"container-title":["Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/1999-4893\/13\/11\/277\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T10:27:24Z","timestamp":1760178444000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/1999-4893\/13\/11\/277"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,10,31]]},"references-count":34,"journal-issue":{"issue":"11","published-online":{"date-parts":[[2020,11]]}},"alternative-id":["a13110277"],"URL":"https:\/\/doi.org\/10.3390\/a13110277","relation":{},"ISSN":["1999-4893"],"issn-type":[{"type":"electronic","value":"1999-4893"}],"subject":[],"published":{"date-parts":[[2020,10,31]]}}}