Single-machine scheduling with deteriorating jobs under a series-parallel graph constraint

被引：67

作者：

Wang, Ji-Bo ^{[1
,2
]}

Ng, C. T. ^{[2
]}

Cheng, T. C. E. ^{[2
]}

机构：

[1] Shenyang Inst Aeronaut Engn, Dept Sci, Shenyang 110136, Peoples R China

[2] Hong Kong Polytech Univ, Dept Logist, Kowloon, Hong Kong, Peoples R China

来源：

COMPUTERS & OPERATIONS RESEARCH | 2008年 / 35卷 / 08期

关键词：

scheduling; single machine; deteriorating jobs; series-parallel graph; makespan; total weighted completion time;

D O I：

10.1016/j.cor.2006.12.026

中图分类号：

TP39 [计算机的应用];

学科分类号：

081203 ; 0835 ;

摘要：

This paper considers single-machine scheduling problems with deteriorating jobs, i.e., jobs whose processing times are an increasing function of their starting times. In addition, the jobs are related by a series-parallel graph. It is shown that for the general linear problem to minimize the makespan, polynomial algorithms exist. It is also shown that for the proportional linear problem of minimization of the total weighted completion time, polynomial algorithms exist, too. (C) 2007 Elsevier Ltd. All rights reserved.

引用

页码：2684 / 2693

页数：10

共 22 条

[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] Minimizing maximum lateness under linear deterioration [J].

Bachman, A ;

Janiak, A .

EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 2000, 126 (03) :557-566

[3] Minimizing the total weighted completion time of deteriorating jobs [J].

Bachman, A ;

Janiak, A ;

Kovalyov, MY .

INFORMATION PROCESSING LETTERS, 2002, 81 (02) :81-84

[4] SCHEDULING DETERIORATING JOBS ON A SINGLE PROCESSOR [J].

BROWNE, S ;

YECHIALI, U .

OPERATIONS RESEARCH, 1990, 38 (03) :495-498

[5]

BRUCKER P, 1998, SCHEDULING ALGORITHM

[6] Parallel machine scheduling with time dependent processing times [J].

Chen, ZL .

DISCRETE APPLIED MATHEMATICS, 1996, 70 (01) :81-93

[7] 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

[8] The complexity of scheduling starting time dependent tasks with release times [J].

Cheng, TCE ;

Ding, Q .

INFORMATION PROCESSING LETTERS, 1998, 65 (02) :75-79

[9]

Graham R. L., 1979, Discrete Optimisation, P287

[10] Minimization of maximum lateness under linear deterioration [J].

Hsu, YS ;

Lin, BMT .

OMEGA-INTERNATIONAL JOURNAL OF MANAGEMENT SCIENCE, 2003, 31 (06) :459-469

← 1 2 3 →