Scheduling step-deteriorating jobs to minimize the total completion time. (June 2020)

• Record Type: Journal Article
• Authors: Cheng, T.C.E.; Kravchenko, Svetlana A.; Lin, Bertrand M.T.
• Is Part Of: Computers & industrial engineering. Volume 144(2020)
• Publication Date: 2020-06
• Subjects: Single-machine scheduling -- Step deterioration -- Total completion time -- Ordinary NP-hardness -- Dynamic programming; Engineering -- Data processing -- Periodicals; Industrial engineering -- Periodicals; 620.00285
• DOI: 10.1016/j.cie.2020.106329
• Languages: English
• ISSNs: 0360-8352

Abstract

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.