Lagrangian relaxation algorithms for real-time hybrid flowshop scheduling with finite intermediate buffers

Abstract

We investigate the problem of scheduling N jobs on parallel identical machines in J successive stages with finite buffer capacities between consecutive stages in a real-time environment. The objective is to find a schedule that minimizes the sum of weighted completion time of jobs. This problem has proven strongly NP-hard. In this paper, the scheduling problem is formulated as an integer programming model considering buffers as machines with zero processing time. Lagrangian relaxation algorithms are developed combined with a speed-up dynamic programming approach. The complication and time consumption of solving all the subproblems at each iteration in subgradient optimization motivate the development of the surrogate subgradient method, where only one subproblem is minimized at each iteration and an adaptive multiplier update scheme of Lagrangian multipliers is designed. Computational experiments with up to 100 jobs show that the designed surrogate subgradient algorithm provides a better performance as compared to the subgradient algorithm.

Keywords:

• real-time hybrid flowshop scheduling
• finite immediate buffer
• Lagrangian relaxation
• speed-up dynamic programming
• surrogate subgradient method
• subgradient method

Acknowledgements

This research is partly supported by the National Natural Science Foundation for Distinguished Young Scholars of China (Grant no. 70425003), National Natural Science Foundation of China (Grant no. 60274049) and (Grant no. 70171030), Fok Ying Tung Education Foundation and the Excellent Young Faculty Program of the Ministry of Education, China. We thank the Production Manufacturing Centre in Baosteel for providing a lot of production information and data. We also thank the two anonymous referees for their valuable suggestions. We are also grateful to Chen HX and Zhao X of the University of Connecticut for insightful discussions in algorithm development.