Scheduling step-deteriorating jobs to minimize the total completion time

T. C.E. Cheng, Svetlana A. Kravchenko, Bertrand M.T. Lin*

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

16 Scopus citations

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.

Original languageEnglish
Article number106329
JournalComputers and Industrial Engineering
Volume144
DOIs
StatePublished - Jun 2020

Keywords

  • Dynamic programming
  • Ordinary NP-hardness
  • Single-machine scheduling
  • Step deterioration
  • Total completion time

Fingerprint

Dive into the research topics of 'Scheduling step-deteriorating jobs to minimize the total completion time'. Together they form a unique fingerprint.

Cite this