A Scatter Search Algorithm for a Multistage Production Scheduling Problem With Blocking and Semi-Continuous Batching Machine

摘要

This paper studies a multistage production scheduling problem with blocking and semi-continuous batching machine, which is abstracted from the integrated hot rolling production in iron and steel industry. One major characteristic of the problem is that the first machine is a semi-continuous batching machine that can simultaneously process multiple jobs and the jobs do not enter and leave it in a batch mode, but one by one and continuously. Furthermore, this problem considers multiple production stages of hot rolling line while previous problems in the literature focused on only the single hot rolling stage or the two stages of reheating and hot rolling. This problem can be treated as a generalized permutation flowshop scheduling problem with blocking to minimize the makespan (i.e., the maximum completion time of all jobs), which is a NP-hard problem. We formulate this problem as a mixed integer linear programming model and propose a scatter search (SS) algorithm to solve it. To further improve the performance of the SS, the reference set is divided into three parts to balance the solution quality and diversity, and a modified stochastic variable neighborhood search is developed as the local search, where two kinds of speedup strategies based on the problem's characteristics are incorporated. Computational results on practical production data and randomly generated instances of our problem show that the SS algorithm outperforms the commercial software named CPLEX and some other meta-heuristics. In addition, further tests using benchmark instances of the traditional permutation flowshop scheduling problem with blocking also demonstrate that our SS algorithm is superior to previous meta-heuristics in the literature.