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

作者：Kim Eun Seok; Oron Daniel^*

来源：Journal of the Operational Research Society, 2015, 66(9): 1481-1490.

DOI：10.1057/jors.2014.91

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

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.

• 出版日期2015-9