Scheduling with step-improving processing times

Edwin Tai Chiu Cheng; Yong He; Han Hoogeveen; Min Ji; Gerhard J. Woeginger

doi:10.1016/j.orl.2005.03.002

Scheduling with step-improving processing times

Edwin Tai Chiu Cheng, Yong He, Han Hoogeveen, Min Ji, Gerhard J. Woeginger

Research output: Journal article publication › Journal article › Academic research › peer-review

7 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
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 - 1 Jan 2006

Keywords

Approximation scheme
Competitive analysis
Knapsack problem
Scheduling

ASJC Scopus subject areas

Management Science and Operations Research
Statistics, Probability and Uncertainty
Discrete Mathematics and Combinatorics
Modelling and Simulation

More information

10.1016/j.orl.2005.03.002

http://hdl.handle.net/10397/1228

Cite this

@article{26d78fb823274a1f87eb53c9397d9aee,

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, {Edwin Tai Chiu} and Yong He and Han Hoogeveen and Min Ji and Woeginger, {Gerhard J.}",

year = "2006",

month = jan,

day = "1",

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

language = "English",

volume = "34",

pages = "37--40",

journal = "Operations Research Letters",

issn = "0167-6377",

publisher = "Elsevier",

number = "1",

}

TY - JOUR

T1 - Scheduling with step-improving processing times

AU - Cheng, Edwin Tai Chiu

AU - He, Yong

AU - Hoogeveen, Han

AU - Ji, Min

AU - Woeginger, Gerhard J.

PY - 2006/1/1

Y1 - 2006/1/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 - Journal 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

Keywords

ASJC Scopus subject areas

More information

Other files and links

Fingerprint

Cite this