Scheduling step-deteriorating jobs on a single machine with multiple critical dates

This paper studies a scheduling problem with step-deteriorating jobs and multiple critical dates in a single machine environment, where each job’s processing time increases stepwise at each critical date as its start time is delayed. Our goal is to minimize the total weighted completion time. First, we prove that the problem is NP-hard when there is one critical date and that even the unweighted case with two critical dates remains NP-hard and has inapproximability. We further establish the strong NP-hardness for the unweighted case with an arbitrary number of critical dates. As solution approaches, we develop a mixed integer linear programming formulation and develop a heuristic based on the weighted shortest processing time rule. Finally, extensive numerical experiments were designed according to the level of difficulty in evaluating the performance of the proposed heuristic.