Lagrangian Relaxation for Parallel Machine Batch Scheduling with Deteriorating Jobs

We investigate the problem of scheduling jobs with batch production on the identical parallel machines with respect to time-deteriorating processing time in which the processing time of a job is a piecewise linear deterioration function of its starting time. The objective is to find a feasible schedule that minimizes the total completion times of jobs. This paper proposes a batch decoupling based Lagrangian relaxation algorithm for this problem. In this algorithm, after capacity constraints are relaxed by Lagrangian multipliers, the relaxed problem can be decomposed into batch-level subproblems. The extensive computational experiments are carried out and the results show that the proposed algorithm can solve the problem effectively in a reasonable amount of the computation time.