Scheduling jobs with simple precedence constraints on parallel machines

Abstract

A methodology is presented for scheduling jobs on identical, parallel machines. Each job comprises 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 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 reincorporate new jobs and other dynamic changes. This scheduling methodology has been implemented in a knowledge-based scheduling system. Typical sizes of problems involve 35 to 40 machines and 100 to 200 jobs, each with 3 to 5 operations.