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 条
123