SCHEDULING JOBS UNDER SIMPLE LINEAR DETERIORATION

被引:261
作者
MOSHEIOV, G [1 ]
机构
[1] HEBREW UNIV JERUSALEM,DEPT STAT,IL-91905 JERUSALEM,ISRAEL
关键词
D O I
10.1016/0305-0548(94)90080-9
中图分类号
TP39 [计算机的应用];
学科分类号
081203 ; 0835 ;
摘要
We consider simple linear deterioration of processing times, i.e. P(i) - alpha(i)t, where alpha(i) is a job dependent deterioration rate and t >0 is the job's starting time. In this environment, we study most classical n -job, non-preemptive, single machine scheduling models, i.e. most commonly used performance measures are considered: makespan, flow-time, total tardiness, number of tardy jobs, etc We show that all these models remain polynomially solvable.
引用
收藏
页码:653 / 659
页数:7
相关论文
共 7 条
[1]  
BAKER KR, 1975, INTRO SEQUENCING SCH
[2]   SCHEDULING DETERIORATING JOBS ON A SINGLE PROCESSOR [J].
BROWNE, S ;
YECHIALI, U .
OPERATIONS RESEARCH, 1990, 38 (03) :495-498
[3]  
JACKSON J, 1955, UCLA43 MAG SCI RES P
[4]   N JOB, ONE MACHINE SEQUENCING ALGORITHM FOR MINIMIZING THE NUMBER OF LATE JOBS [J].
MOORE, JM .
MANAGEMENT SCIENCE, 1968, 15 (01) :102-109
[5]   V-SHAPED POLICIES FOR SCHEDULING DETERIORATING JOBS [J].
MOSHEIOV, G .
OPERATIONS RESEARCH, 1991, 39 (06) :979-991
[6]  
MOSHEIOV G, 1990, THESIS COLUMBIA U NY
[7]   SIMPLE OPTIMALITY PROOF OF MOORES SEQUENCING ALGORITHM [J].
STURM, LBJM .
MANAGEMENT SCIENCE SERIES A-THEORY, 1970, 17 (01) :116-118