Scheduling step-deteriorating jobs to minimize the total completion time

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

doi:10.1016/j.cie.2020.106329

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 publication › Journal article › Academic research › peer-review

19 Citations (Scopus)

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 language	English
Article number	106329
Journal	Computers and Industrial Engineering
Volume	144
DOIs	https://doi.org/10.1016/j.cie.2020.106329
Publication status	Published - Jun 2020

Keywords

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

ASJC Scopus subject areas

General Computer Science
General Engineering

More information

10.1016/j.cie.2020.106329

Cite this

@article{137b8a93b1874011811a1c50c92fd5b4,

title = "Scheduling step-deteriorating jobs to minimize the total completion time",

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.",

keywords = "Dynamic programming, Ordinary NP-hardness, Single-machine scheduling, Step deterioration, Total completion time",

author = "Cheng, \{T. C.E.\} and Kravchenko, \{Svetlana A.\} and Lin, \{Bertrand M.T.\}",

year = "2020",

month = jun,

doi = "10.1016/j.cie.2020.106329",

language = "English",

volume = "144",

journal = "Computers and Industrial Engineering",

issn = "0360-8352",

publisher = "Elsevier Ltd",

}

TY - JOUR

T1 - Scheduling step-deteriorating jobs to minimize the total completion time

AU - Cheng, T. C.E.

AU - Kravchenko, Svetlana A.

AU - Lin, Bertrand M.T.

PY - 2020/6

Y1 - 2020/6

N2 - 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.

AB - 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.

KW - Dynamic programming

KW - Ordinary NP-hardness

KW - Single-machine scheduling

KW - Step deterioration

KW - Total completion time

UR - https://www.scopus.com/pages/publications/85083590408

U2 - 10.1016/j.cie.2020.106329

DO - 10.1016/j.cie.2020.106329

M3 - Journal article

AN - SCOPUS:85083590408

SN - 0360-8352

VL - 144

JO - Computers and Industrial Engineering

JF - Computers and Industrial Engineering

M1 - 106329

ER -

Scheduling step-deteriorating jobs to minimize the total completion time

Abstract

Keywords

ASJC Scopus subject areas

More information

Other files and links

Fingerprint

Cite this