Minimizing total completion time on a single machine with step improving jobs

Production systems often experience a shock or a technological change, resulting in performance improvement. In such settings, job processing times become shorter if jobs start processing at, or after, a common critical date. This paper considers a single machine scheduling problem with step‐improving processing times, where the effects are job‐dependent. The objective is to minimize the total completion time. We show that the problem is NP‐hard in general and discuss several special cases which can be solved in polynomial time. We formulate a Mixed Integer Programming model and develop an LP‐based heuristic for the general problem. Finally, computational experiments show that the proposed heuristic yields very effective and efficient solutions.