A note on a fully polynomial-time approximation scheme for parallel-machine scheduling with deteriorating jobs

被引：42
作者：
Kang, Liying [1 ]
Ng, C. T.
机构：
[1] Shanghai Univ, Dept Math, Shanghai 200444, Peoples R China
[2] Hong Kong Polytech Univ, Dept Logist, Hong Kong, Peoples R China
来源：
INTERNATIONAL JOURNAL OF PRODUCTION ECONOMICS | 2007年 / 109卷 / 1-2期
基金：
中国国家自然科学基金;
关键词：
deteriorating jobs; fully polynomial-time approximation scheme; parallel-machine scheduling;
D O I：
10.1016/j.ijpe.2006.11.014
中图分类号：
T [工业技术];
学科分类号：
08 ;
摘要：
In this paper we study the NP-hard problem of scheduling n deteriorating jobs on in identical parallel machines to minimize the makespan. Each job's processing time is a linear nondecreasing function of its start time. We present a fully polynomial-time approximation scheme for the problem, thus establishing that the problem is NP-hard in the ordinary sense only. (c) 2007 Elsevier B.V. All rights reserved.
引用
收藏
页码：180 / 184
页数：5
相关论文
共 17 条
[1]   Scheduling with time dependent processing times: Review and extensions [J].
Alidaee, B ;
Womer, NK .
JOURNAL OF THE OPERATIONAL RESEARCH SOCIETY, 1999, 50 (07) :711-720
[2]   On a scheduling problem of time deteriorating jobs [J].
Cai, JY ;
Cai, P ;
Zhu, YX .
JOURNAL OF COMPLEXITY, 1998, 14 (02) :190-209
[3]  
Chen ZL, 1997, DISCRETE APPL MATH, V75, P103
[4]   Parallel machine scheduling with time dependent processing times [J].
Chen, ZL .
DISCRETE APPLIED MATHEMATICS, 1996, 70 (01) :81-93
[5]   A concise survey of scheduling with time-dependent processing times [J].
Cheng, TCE ;
Ding, Q ;
Lin, BMT .
EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 2004, 152 (01) :1-13
[6]   Scheduling jobs with piecewise linear decreasing processing times [J].
Cheng, TCE ;
Ding, Q ;
Kovalyov, MY ;
Bachman, A ;
Janiak, A .
NAVAL RESEARCH LOGISTICS, 2003, 50 (06) :531-554
[7]  
Graham R. L., 1979, Discrete Optimisation, P287
[8]   SINGLE FACILITY SCHEDULING WITH NONLINEAR PROCESSING TIMES [J].
GUPTA, JND ;
GUPTA, SK .
COMPUTERS & INDUSTRIAL ENGINEERING, 1988, 14 (04) :387-393
[9]   OPTIMAL REPAYMENT POLICIES FOR MULTIPLE LOANS [J].
GUPTA, SK ;
KUNNATHUR, AS ;
DANDAPANI, K .
OMEGA-INTERNATIONAL JOURNAL OF MANAGEMENT SCIENCE, 1987, 15 (04) :323-330
[10]   Scheduling linearly deteriorating jobs on multiple machines [J].
Hsieh, YC ;
Bricker, DL .
COMPUTERS & INDUSTRIAL ENGINEERING, 1997, 32 (04) :727-734
12