V-SHAPED POLICIES FOR SCHEDULING DETERIORATING JOBS

被引：150
作者：
MOSHEIOV, G
机构：
[1] CUNY BERNARD M BARUCH COLL,DEPT STAT & COMP INFORMAT SYST,NEW YORK,NY 10010
[2] HEBREW UNIV JERUSALEM,DEPT STAT,JERUSALEM,ISRAEL
来源：
OPERATIONS RESEARCH | 1991年 / 39卷 / 06期
关键词：
PRODUCTION SCHEDULING; DETERMINISTIC SEQUENCING; SINGLE MACHINE;
D O I：
10.1287/opre.39.6.979
中图分类号：
C93 [管理学];
学科分类号：
12 ; 1201 ; 1202 ; 120202 ;
摘要：
A set of N jobs has to be processed on a single machine. Jobs have the same basic processing time, but the actual processing time of each job grows linearly with its starting time. A (possibly) different rate of growth is associated with each job. We show that the optimal sequence to minimize flow time is V-shaped: Jobs are arranged in descending order of growth rate if they are placed before the minimal growth rate job, and in ascending order if placed after it. Efficient (0(N log N)) asymptotically optimal heuristics are developed. Their average performance is shown to be extremely good: The average relative error over a set of 20-job problems is on the order of 10(-5).
引用
收藏
页码：979 / 991
页数：13
相关论文
共 17 条
[1]  
BAGCHI U, 1987, NAV RES LOG, V34, P739, DOI 10.1002/1520-6750(198710)34:5<739::AID-NAV3220340513>3.0.CO
[2]  
2-3
[3]   MINIMIZING MEAN ABSOLUTE DEVIATION OF COMPLETION TIMES ABOUT A COMMON DUE DATE [J].
BAGCHI, U ;
SULLIVAN, RS ;
CHANG, YL .
NAVAL RESEARCH LOGISTICS, 1986, 33 (02) :227-240
[4]   MINIMIZING MEAN SQUARED DEVIATION OF COMPLETION TIMES ABOUT A COMMON DUE DATE [J].
BAGCHI, U ;
SULLIVAN, RS ;
CHANG, YL .
MANAGEMENT SCIENCE, 1987, 33 (07) :894-906
[5]   SEQUENCING WITH EARLINESS AND TARDINESS PENALTIES - A REVIEW [J].
BAKER, KR ;
SCUDDER, GD .
OPERATIONS RESEARCH, 1990, 38 (01) :22-36
[6]   SCHEDULING DETERIORATING JOBS ON A SINGLE PROCESSOR [J].
BROWNE, S ;
YECHIALI, U .
OPERATIONS RESEARCH, 1990, 38 (03) :495-498
[7]   MINIMIZING WAITING TIME VARIANCE IN SINGLE MACHINE PROBLEM [J].
EILON, S ;
CHOWDHURY, IG .
MANAGEMENT SCIENCE, 1977, 23 (06) :567-575
[8]  
EMMONS H, 1987, NAV RES LOG, V34, P803, DOI 10.1002/1520-6750(198712)34:6<803::AID-NAV3220340605>3.0.CO
[9]  
2-2
[10]   EARLINESS-TARDINESS SCHEDULING PROBLEMS .1. WEIGHTED DEVIATION OF COMPLETION TIMES ABOUT A COMMON DUE DATE [J].
HALL, NG ;
POSNER, ME .
OPERATIONS RESEARCH, 1991, 39 (05) :836-846
12