SCHEDULING ABOUT A COMMON DUE DATE WITH EARLINESS AND TARDINESS PENALTIES

被引:23
作者
DE, P
GHOSH, JB
WELLS, CE
机构
[1] Department of MIS and Decision Sciences, University of Dayton, 300 College Park, Dayton
关键词
D O I
10.1016/0305-0548(90)90046-A
中图分类号
TP39 [计算机的应用];
学科分类号
081203 ; 0835 ;
摘要
This paper describes solution techniques for scheduling a set of independent jobs on a single machine where the objective is to minimize the mean squared deviation of the completion times about a common due date. A branch and bound algorithm is proposed and implemented using a recursive scheme. The algorithm is tested on job sets drawn from six different distributions of processing times. Computational experiments which compare this approach with the existing methodology indicate that the former is significantly faster and can solve much larger problems. A heuristic based upon the branch and bound algorithm is also presented which provides fast solutions with constant performance guarantees. © 1990.
引用
收藏
页码:231 / 241
页数:11
相关论文
共 19 条
[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]  
BAKER KR, 1988, 226 DARTM COLL A TUC
[6]   A NOTE ON THE MINIMIZATION OF MEAN SQUARED DEVIATION OF COMPLETION TIMES ABOUT A COMMON DUE DATE [J].
DE, P ;
GHOSH, JB ;
WELLS, CE .
MANAGEMENT SCIENCE, 1989, 35 (09) :1143-1147
[7]   MINIMIZING WAITING TIME VARIANCE IN SINGLE MACHINE PROBLEM [J].
EILON, S ;
CHOWDHURY, IG .
MANAGEMENT SCIENCE, 1977, 23 (06) :567-575
[8]   MINIMIZING WEIGHTED ABSOLUTE DEVIATION IN SINGLE-MACHINE SCHEDULING [J].
FRY, TD ;
ARMSTRONG, RD ;
BLACKSTONE, JH .
IIE TRANSACTIONS, 1987, 19 (04) :445-450
[9]   MINIMIZING A QUADRATIC FUNCTION OF JOB LATENESS ON A SINGLE-MACHINE [J].
GUPTA, SK ;
SEN, T .
ENGINEERING COSTS AND PRODUCTION ECONOMICS, 1983, 7 (03) :187-194