Scheduling with step-improving processing times

T. C.Edwin Cheng; Yong He; Han Hoogeveen; Min Ji; Gerhard J. Woeginger

doi:10.1016/j.orl.2005.03.002

Scheduling with step-improving processing times

T. C.Edwin Cheng, Yong He, Han Hoogeveen^*, Min Ji, Gerhard J. Woeginger

^*Corresponding author for this work

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

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
Number of pages	4
Journal	Operations Research Letters
Volume	34
Issue number	1
DOIs	https://doi.org/10.1016/j.orl.2005.03.002
Publication status	Published - Jan 2006

Bibliographical note

Funding Information:
T.C. Edwin Cheng was supported in part by The Hong Kong Polytechnic University under a grant from the Area of Strategic Development in China Business Services. Yong He acknowledges support by TRAPOYT, China, and the NSFC of China (10271110, 60021201). Han Hoogeveen and Gerhard Woeginger were partially supported by BSIK Grant 03018 (BRICKS: Basic Research in Informatics for Creating the Knowledge Society). Gerhard Woeginger was partially supported by the Netherlands Organisation for Scientific Research, Grant 639.033.403.

Funding

T.C. Edwin Cheng was supported in part by The Hong Kong Polytechnic University under a grant from the Area of Strategic Development in China Business Services. Yong He acknowledges support by TRAPOYT, China, and the NSFC of China (10271110, 60021201). Han Hoogeveen and Gerhard Woeginger were partially supported by BSIK Grant 03018 (BRICKS: Basic Research in Informatics for Creating the Knowledge Society). Gerhard Woeginger was partially supported by the Netherlands Organisation for Scientific Research, Grant 639.033.403.

Keywords

Approximation scheme
Competitive analysis
Knapsack problem
Scheduling

Access to Document

10.1016/j.orl.2005.03.002

Cite this

@article{399d49803586486da002411e58c45c97,

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

keywords = "Approximation scheme, Competitive analysis, Knapsack problem, Scheduling",

author = "Cheng, {T. C.Edwin} and Yong He and Han Hoogeveen and Min Ji and Woeginger, {Gerhard J.}",

note = "Funding Information: T.C. Edwin Cheng was supported in part by The Hong Kong Polytechnic University under a grant from the Area of Strategic Development in China Business Services. Yong He acknowledges support by TRAPOYT, China, and the NSFC of China (10271110, 60021201). Han Hoogeveen and Gerhard Woeginger were partially supported by BSIK Grant 03018 (BRICKS: Basic Research in Informatics for Creating the Knowledge Society). Gerhard Woeginger was partially supported by the Netherlands Organisation for Scientific Research, Grant 639.033.403.",

year = "2006",

month = jan,

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

language = "English",

volume = "34",

pages = "37--40",

journal = "Operations Research Letters",

publisher = "Elsevier BV",

number = "1",

}

TY - JOUR

T1 - Scheduling with step-improving processing times

AU - Cheng, T. C.Edwin

AU - He, Yong

AU - Hoogeveen, Han

AU - Ji, Min

AU - Woeginger, Gerhard J.

N1 - Funding Information: T.C. Edwin Cheng was supported in part by The Hong Kong Polytechnic University under a grant from the Area of Strategic Development in China Business Services. Yong He acknowledges support by TRAPOYT, China, and the NSFC of China (10271110, 60021201). Han Hoogeveen and Gerhard Woeginger were partially supported by BSIK Grant 03018 (BRICKS: Basic Research in Informatics for Creating the Knowledge Society). Gerhard Woeginger was partially supported by the Netherlands Organisation for Scientific Research, Grant 639.033.403.

PY - 2006/1

Y1 - 2006/1

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.

KW - Approximation scheme

KW - Competitive analysis

KW - Knapsack problem

KW - Scheduling

UR - http://www.scopus.com/inward/record.url?scp=28044460248&partnerID=8YFLogxK

U2 - 10.1016/j.orl.2005.03.002

DO - 10.1016/j.orl.2005.03.002

M3 - Article

VL - 34

SP - 37

EP - 40

JO - Operations Research Letters

JF - Operations Research Letters

IS - 1

ER -

Scheduling with step-improving processing times

Abstract

Bibliographical note

Funding

Keywords

Access to Document

Other files and links

Fingerprint

Cite this