Scheduling dynamic hybrid flowshop with serial batching machines

Abstract

This paper considers a multi-stage dynamic hybrid flowshop in which some stage contains several identical batching machines and the other stages contain several identical discrete machines. Each discrete machine can process no more than one operation at a time, and each batching machine can process several jobs continuously in a batch. This problem has a strong practical background in the process industry. Since the problem is NP-hard, improved Lagrangian relaxation (LR) is developed where batch decomposition strategy is applied and mixed backward and forward dynamic programming is designed to solve batch-level subproblems with the case that each operation may have multiple predecessors and successors. Results of numerical experiments with up to 60 jobs show that the proposed algorithm can obtain better solutions in a reasonable computation time than traditional LR.

Keywords:

• dynamic HFS scheduling
• serial batching machines
• improved Lagrangian relaxation
• batch decomposition
• MBFDP

Acknowledgements

This research is supported by National Natural Science Foundation of China (Grant no. 71001090 and Grant no. 71001091). The authors would like to thank the anonymous referees for their valuable comments.