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 条

[1]

[Anonymous], 2016, LINEAR NONLINEAR PRO

[2]

Bertsekas D. P., 1982, P 1982 IEEE INT LARG, P141

[3] FLEXIBLE MIXED-INTEGER PROGRAMMING FORMULATIONS FOR PRODUCTION SCHEDULING PROBLEMS [J].