Scheduling with step-improving processing times

T.C.E. Cheng; Yong He; J.A. Hoogeveen; Min Ji; G.J. Woeginger

doi:10.1016/j.orl.2005.03.002

Scheduling with step-improving processing times

T.C.E. Cheng
, Yong He
, J.A. Hoogeveen
, Min Ji
, G.J. Woeginger

Combinatorial Optimization

Research output: Contribution to journal › Article › Academic › peer-review

9 Citations (Scopus)

Abstract

We consider the scheduling problem of minimizing the makespan on a single machine with step-improving job processing times around a common critical date. For this problem we give an NP-hardness proof, a fast pseudo-polynomial time algorithm, an FPTAS, and an on-line algorithm with best possible competitive ratio.

Original language	English
Pages (from-to)	37-40
Journal	Operations Research Letters
Volume	34
Issue number	1
DOIs	https://doi.org/10.1016/j.orl.2005.03.002
Publication status	Published - 2006

Access to Document

10.1016/j.orl.2005.03.002

Cite this

@article{391f33375b7341e6ad30036e62f594f4,

title = "Scheduling with step-improving processing times",

abstract = "We consider the scheduling problem of minimizing the makespan on a single machine with step-improving job processing times around a common critical date. For this problem we give an NP-hardness proof, a fast pseudo-polynomial time algorithm, an FPTAS, and an on-line algorithm with best possible competitive ratio.",

author = "T.C.E. Cheng and Yong He and J.A. Hoogeveen and Min Ji and G.J. Woeginger",

year = "2006",

doi = "10.1016/j.orl.2005.03.002",

language = "English",

volume = "34",

pages = "37--40",

journal = "Operations Research Letters",

issn = "0167-6377",

publisher = "Elsevier B.V.",

number = "1",

}

TY - JOUR

T1 - Scheduling with step-improving processing times

AU - Cheng, T.C.E.

AU - He, Yong

AU - Hoogeveen, J.A.

AU - Ji, Min

AU - Woeginger, G.J.

PY - 2006

Y1 - 2006

N2 - We consider the scheduling problem of minimizing the makespan on a single machine with step-improving job processing times around a common critical date. For this problem we give an NP-hardness proof, a fast pseudo-polynomial time algorithm, an FPTAS, and an on-line algorithm with best possible competitive ratio.

AB - We consider the scheduling problem of minimizing the makespan on a single machine with step-improving job processing times around a common critical date. For this problem we give an NP-hardness proof, a fast pseudo-polynomial time algorithm, an FPTAS, and an on-line algorithm with best possible competitive ratio.

U2 - 10.1016/j.orl.2005.03.002

DO - 10.1016/j.orl.2005.03.002

M3 - Article

SN - 0167-6377

VL - 34

SP - 37

EP - 40

JO - Operations Research Letters

JF - Operations Research Letters

IS - 1

ER -

Scheduling with step-improving processing times

Abstract

Access to Document

Fingerprint

Cite this