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 -