Scheduling step-deteriorating jobs to minimize the total completion time. (June 2020) - Cheng, T.C.E.; Kravchenko, Svetlana A.; Lin, Bertrand M.T.
Highlights: Single-machine scheduling with step-deteriorating jobs to minimize the total completion time is considered. A binary NP-hardness proof is given. A pseudo-polynomial algorithm is developed. Abstract: We consider single-machine scheduling to minimize the total completion time, where the processing time of a job is a step function of its start time. In this paper we establish the complexity status of the problem by proving its NP-hardness and developing a dynamic programming algorithm that solves the problem in pseudo-polynomial time.