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.
