More MILP models for hybrid flow shop scheduling problem and its extended problems |
| |
| Authors: | Leilei Meng Xinyu Shao Biao Zhang Yaping Ren Wenwen Lin |
| |
| Affiliation: | 1. State Key Lab of Digital Manufacturing Equipment and Technology, Huazhong University of Science and Technology, Wuhan, People’s Republic of China;2. Current address: School of Computer Science, Liaocheng University, Liaocheng, People's Republic of China;3. State Key Lab of Digital Manufacturing Equipment and Technology, Huazhong University of Science and Technology, Wuhan, People’s Republic of China;4. Current address: School of Intelligent Systems Science and Engineering, Jinan University (Zhuhai Campus), Zhuhai, People's Republic of China;5. Faculty of Mechanical Engineering &6. Mechanics, Ningbo University, Ningbo, People’s Republic of China |
| |
| Abstract: | With the rapid development of computer technology and related softwares for mathematical models, mathematical modelling of scheduling problems is receiving growing attention from researchers. In this work, the hybrid flow shop scheduling problem with unrelated parallel machines (HFSP-UPM) with the objective aimed to minimise the makespan is studied. According to the characteristics of the HFSP-UPM, eight mixed integer linear programming (MILP) models are formulated in order to obtain optimal solutions based on different modelling ideas. Then, these models are extended to solve HFSP-UPM with sequence-dependent setup times (HFSP-UPM-SDST), no-wait HFSP-UPM (HFSP-UPM-NW) and HFSP-UPM with blocking (HFSP-UPM-B). All the proposed models and the existing model are detailedly compared and evaluated under three aspects namely modelling process, size complexity and computational complexity. Numerical experiments show that MILP models dependent on diverse modelling ideas perform very differently. The model developed based on stage precedence is the best one and should be given preference in future applications. In addition, the proposed models of HFSP-UPM-NW and HFSP-UPM-B improve several best known solutions for the test instances in the existing literature. |
| |
| Keywords: | hybrid flow shop scheduling sequence-dependent setup times no-wait blocking mixed integer linear programming |
|
|
