More MILP models for hybrid flow shop scheduling problem and its extended problems

摘要

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.