Scheduling jobs with simple precedence constraints on parallel machines
- 1 February 1990
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Control Systems Magazine
- Vol. 10 (2) , 34-40
- https://doi.org/10.1109/37.45792
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.Keywords
This publication has 21 references indexed in Scilit:
- A system for routing and capacity assignment in computer communication networksIEEE Transactions on Communications, 1989
- An evolutionary approach to the traveling salesman problemBiological Cybernetics, 1988
- Ordering scheduling problem in manufacturing systemsInternational Journal of Production Research, 1988
- Two level heuristic for the resource constrained scheduling problemInternational Journal of Production Research, 1986
- Flexible Mixed-Integer Programming Formulations for Production Scheduling ProblemsIIE Transactions, 1985
- Optimization by Simulated AnnealingScience, 1983
- Recent Developments in Deterministic Sequencing and Scheduling: A SurveyPublished by Springer Nature ,1982
- Lagrangean relaxation for integer programmingPublished by Springer Nature ,1974
- Bounds on Multiprocessing Timing AnomaliesSIAM Journal on Applied Mathematics, 1969
- Minimization of unsmooth functionalsUSSR Computational Mathematics and Mathematical Physics, 1969