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 (MIP) 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.

Published online 10 December 2014