Scheduling Jobs with Simple Precedence Constraints on Parallel Machines

被引:21
作者
Hoitomt, Debra J. [1 ]
Luh, Peter B. [2 ]
Max, Eric [1 ]
Pattipati, Krishna R. [2 ]
机构
[1] Pratt & Whitney, E Hartford, CT 06108 USA
[2] Univ Connecticut, Dept Elect & Syst Engn, Storrs, CT 06269 USA
来源
IEEE CONTROL SYSTEMS MAGAZINE | 1990年 / 10卷 / 02期
基金
美国国家科学基金会;
关键词
D O I
10.1109/37.45792
中图分类号
TP [自动化技术、计算机技术];
学科分类号
0812 ;
摘要
This article presents a methodology for scheduling jobs on identical, parallel machines. Each job is comprised of a small number of operations that must be processed in a specified order. The objective is to minimize the total weighted quadratic tardiness of the schedule, subject to capacity and precedence constraints. The procedure presented here is an efficient near-optimal method based on the Lagrangian relaxation technique and the list-scheduling concept. In addition, the resulting job-interaction information can be used to provide quick answers to "what-if" questions and to reconfigure the schedule to incorporate new jobs and other dynamic changes. This scheduling methodology has been implemented for a work center at Pratt & Whitney as part of its knowledge-based scheduling system. Typical sizes of problems involve 35 to 40 machines and 100 to 200 jobs, each with 3 to 5 operations.
引用
收藏
页码:34 / 40
页数:7
相关论文
共 27 条
[11]   AN OPTIMAL SOLUTION METHOD FOR LARGE-SCALE MULTIPLE TRAVELING SALESMEN PROBLEMS [J].
GAVISH, B ;
SRIKANTH, K .
OPERATIONS RESEARCH, 1986, 34 (05) :698-717
[12]  
Geoffrion A.M., 1974, MATH PROGRAMMING STU, P82, DOI DOI 10.1007/BFB0120686
[13]  
Goldratt E. M., 1986, GOAL PROCESS ONGOING
[14]   BOUNDS ON MULTIPROCESSING TIMING ANOMALIES [J].
GRAHAM, RL .
SIAM JOURNAL ON APPLIED MATHEMATICS, 1969, 17 (02) :416-&
[15]  
GRAVES SC, 1981, OPER RES, V18, P841
[16]  
Held M., 1971, MATH PROGRAMMING STU, P6
[17]  
Horowitz E., 1978, FUNDAMENTALS COMPUTE, P575
[18]   OPTIMIZATION BY SIMULATED ANNEALING [J].
KIRKPATRICK, S ;
GELATT, CD ;
VECCHI, MP .
SCIENCE, 1983, 220 (4598) :671-680
[19]  
LAWLER EL, 1982, DETERMINISTIC STOCHA
[20]   COMPLEXITY OF SCHEDULING UNDER PRECEDENCE CONSTRAINTS [J].
LENSTRA, JK ;
RINNOOYKAN, AHG .
OPERATIONS RESEARCH, 1978, 26 (01) :22-35