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

Abstract

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.

Keywords:

• scheduling
• step-improving processing times
• total completion time
• heuristic

after four revisions

The online version of this article is available Open Access

after four revisions

The online version of this article is available Open Access