Single-machine group-scheduling problems with deteriorating setup times and job-processing times

There is a growing interest in the research of deteriorating job-scheduling problems in recent years. However, the group technology is relatively unexplored in this field. In addition, the group setup times are assumed to be known and fixed. In reality, process setup or preparation often requires more time as food quality deteriorates or a patient's condition worsens. Therefore, this paper considers a situation where both setup times and job-processing times are lengthened as jobs wait to be processed. Specifically, two single-machine group-scheduling problems are investigated where the group setup times and the job-processing times are both increasing functions of their starting times. We first prove that the makespan minimization problem remains polynomially solvable when the deterioration is present. We then show that the sum of completion times problem is polynomially solvable when the numbers of jobs in each group are equal. For the case of unequal job sizes, a heuristic algorithm is proposed, and the computational experiments show that the performance of the heuristic is fairly accurately when the deterioration rate is small. (c) 2008 Elsevier B.V. All rights reserved.