Mathematical modelling and optimisation of energy-conscious hybrid flow shop scheduling problem with unrelated parallel machines

Abstract

This paper investigates an energy-conscious hybrid flow shop scheduling problem with unrelated parallel machines (HFSP-UPM) with the energy-saving strategy of turning off and on. We first analyse the energy consumption of HFSP-UPM and formulate five mixed integer linear programming (MILP) models based on two different modelling ideas namely idle time and idle energy. All the models are compared both in size and computational complexities. The results show that MILP models based on different modelling ideas vary dramatically in both size and computational complexities. HFSP-UPM is NP-Hard, thus, an improved genetic algorithm (IGA) is proposed. Specifically, a new energy-conscious decoding method is designed in IGA. To evaluate the proposed IGA, comparative experiments of different-sized instances are conducted. The results demonstrate that the IGA is more effective than the genetic algorithm (GA), simulating annealing algorithm (SA) and migrating birds optimisation algorithm (MBO). Compared with the best MILP model, the IGA can get the solution that is close to an optimal solution with the gap of no more than 2.17% for small-scale instances. For large-scale instances, the IGA can get a better solution than the best MILP model within no more than 10% of the running time of the best MILP model.

Keywords:

• hybrid flow shop scheduling
• unrelated parallel machine
• mixed integer linear programming
• energy-conscious
• genetic algorithm

Disclosure statement

No potential conflict of interest was reported by the authors.

Additional information

Funding

This research is supported by the International Cooperation and Exchange of the National Natural Science Foundation of China [grant number 51561125002], the National Natural Science Foundation of China [grant number 51575211], the Fundamental Research Funds for the Central Universities [grant number HUST: 2014TS038], the National Natural Science Foundation of Jilin province of China [grant number 20180101058JC], and the 111 Project of China [grant number B16019].