EARLINESS-TARDINESS SCHEDULING PROBLEMS .2. DEVIATION OF COMPLETION TIMES ABOUT A RESTRICTIVE COMMON DUE DATE

被引:196
作者
HALL, NG
KUBIAK, W
SETHI, SP
机构
[1] MEM UNIV NEWFOUNDLAND,FAC BUSINESS ADM,ST JOHNS A1C 5S7,NEWFOUNDLAND,CANADA
[2] UNIV TORONTO,FAC MANAGEMENT,TORONTO M5S 1A1,ONTARIO,CANADA
[3] MFG RES CORP,TORONTO,ONTARIO,CANADA
关键词
PRODUCTION SCHEDULING - DETERMINISTIC; SINGLE MACHINE SEQUENCING;
D O I
10.1287/opre.39.5.847
中图分类号
C93 [管理学];
学科分类号
12 ; 1201 ; 1202 ; 120202 ;
摘要
A companion paper (Part I) considers the problem of minimizing the weighted earliness and tardiness of jobs scheduled on a single machine around a common due date, d, which is unrestrictively late. This paper (Part II) considers the problem of minimizing the unweighted earliness and tardiness of jobs, allowing the possibility that d is early enough to constrain the scheduling decision. We describe several optimality conditions. The recognition version of the problem is shown to be NP-complete in the ordinary sense, confirming a well known conjecture. Moreover, this complexity definition is precise, since we describe a dynamic programming algorithm which runs in pseudopolynomial time. This algorithm is also extremely efficient computationally, providing an improvement over earlier procedures, of almost two orders of magnitude in the size of instance that can be solved. Finally, we describe a special case of the problem which is polynomially solvable.
引用
收藏
页码:847 / 856
页数:10
相关论文
共 13 条
[1]   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
[2]   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
[3]   SEQUENCING WITH EARLINESS AND TARDINESS PENALTIES - A REVIEW [J].
BAKER, KR ;
SCUDDER, GD .
OPERATIONS RESEARCH, 1990, 38 (01) :22-36
[4]   MINIMIZING WAITING TIME VARIANCE IN SINGLE MACHINE PROBLEM [J].
EILON, S ;
CHOWDHURY, IG .
MANAGEMENT SCIENCE, 1977, 23 (06) :567-575
[5]   ONE-PROCESSOR SCHEDULING WITH SYMMETRIC EARLINESS AND TARDINESS PENALTIES [J].
GAREY, MR ;
TARJAN, RE ;
WILFONG, GT .
MATHEMATICS OF OPERATIONS RESEARCH, 1988, 13 (02) :330-348
[6]   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
[8]  
HOOGEVEEN JA, 1989, SCHEDULING SMALL COM
[10]   COMMON DUE DATE ASSIGNMENT TO MINIMIZE TOTAL PENALTY FOR THE ONE MACHINE SCHEDULING PROBLEM [J].
PANWALKAR, SS ;
SMITH, ML ;
SEIDMANN, A .
OPERATIONS RESEARCH, 1982, 30 (02) :391-399