Scheduling step-deteriorating jobs to minimize the total completion time

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

Research output: Journal article publicationJournal articleAcademic researchpeer-review

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
Publication statusPublished - Jun 2020

Keywords

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

ASJC Scopus subject areas

  • Computer Science(all)
  • Engineering(all)

Cite this