1. Improved Beam Search for Optimizing No-Wait Flowshops With Release Times
- Author
-
Chen-Yang Cheng, Shih-Wei Lin, Pei-Yu Lin, Pourya Pourhejazy, and Kuo-Ching Ying
- Subjects
0209 industrial biotechnology ,Mathematical optimization ,Optimization problem ,General Computer Science ,Linear programming ,no-wait ,Heuristic (computer science) ,Computer science ,Scheduling (production processes) ,02 engineering and technology ,Flowshop scheduling ,020901 industrial engineering & automation ,Production manager ,0202 electrical engineering, electronic engineering, information engineering ,General Materials Science ,Local search (optimization) ,beam search ,Job shop scheduling ,business.industry ,General Engineering ,Beam search ,020201 artificial intelligence & image processing ,release time ,lcsh:Electrical engineering. Electronics. Nuclear engineering ,business ,lcsh:TK1-9971 - Abstract
Production management of perishable goods is highly complex and requires well-informed decisions in corresponding stages. In such production environments, scheduling problems with time constraints are of high relevance to ensure the timely flow of the work-in-process material and goods. This study introduces the no-wait flowshop scheduling problem with release times (NWFSP-RT) to help advance decision support systems in the food production industry. For this purpose, an original mixed-integer linear programming (MILP) formulation is proposed for minimizing makespan. A BS algorithm, and an improved variant, the local search-based Beam Search (BSLS) algorithms are developed to solve the NWFSP-RT problem. Extensive numerical analysis is conducted to analyze the performance of the algorithms in solving this highly intractable extension of the scheduling problems. We showed that BSLS effectively avoids early convergence and local optimality while dismissing non-promising search directions within a partial enumeration solution approach. The statistical analysis confirmed that the improved BS algorithm performs better in terms of solution quality. Applications of the developed heuristic are worthwhile research topics to pursue in solving other complex optimization problems.
- Published
- 2020