A Genetic Algorithm for Resource-Constrained Scheduling

A Genetic Algorithm for Resource-Constrained Scheduling by Matthew Bartschi Wall B.S. Mechanical Engineering Massachusetts Institute of Technology, 1989 M.S. Mechanical Engineering Massachusetts Institute of Technology, 1991 M.S. Management Sloan School of Management, 1991 Submitted to the Department of Mechanical Engineering in partial fulfillment of the requirements for the degree of Doctor of Philosophy in Mechanical Engineering at the Massachusetts Institute of Technology June 1996 ©1996 Massachusetts Institute of Technology. All rights reserved. Signature of Author: ___________________________________________________________________ Department of Mechanical Engineering 14 May 1996 Certified by: __________________________________________________________________________ Mark Jakiela Associate Professor of Mechanical Engineering Thesis Supervisor Certified by: __________________________________________________________________________ Woodie C. Flowers Pappalardo Professor of Mechanical Engineering Thesis Supervisor Accepted by:__________________________________________________________________________ Ain A. Sonin Chairman, Department Committee on Graduate Students 2

3 A Genetic Algorithm for Resource-Constrained Scheduling by Matthew Bartschi Wall Submitted to the Department of Mechanical Engineering on 14 May 1996 in partial fulfillment of the requirements for the degree of Doctor of Philosophy in Mechanical Engineering Abstract This work describes a genetic algorithm approach to resource-constrained scheduling using a direct, time-based representation. Whereas traditional solution methods are typically sequence- based, this representation encodes schedule information as a dual array of relative delay times and integer execution modes. The representation supports multiple execution modes, preemption, non-uniform resource availability/usage, a variety of resource types, probabilistic resource performance models, overlapping precedence relationships, and temporal constraints on both tasks and resources. In addition, the representation includes time-varying resource availabilities and requirements. Many objective measures can be defined such as minimization of makespan, maximization of net present value, or minimization of average tardiness. Multiple, possibly conflicting objectives are supported. The genetic algorithm adapts to dynamic factors such as changes to the project plan or disturbances in the schedule execution. In addition to the scheduling representation, this thesis presents a structured method for defining and evaluating multiple constraints and objectives. The genetic algorithm was applied to over 1000 small job shop and project scheduling problems (10-300 activities, 3-10 resource types). Although computationally expensive, the algorithm performed fairly well on a wide variety of problems. With little attention given to its parameters, the algorithm found solutions within 2% of published best in 60% of the project scheduling problems. Performance on the jobshop problems was less encouraging; in a set of 82 jobshop problems with makespan as the single performance measure, the algorithm found solutions with makespan 2 to 3 times the published best. On project scheduling problems with multiple execution modes, the genetic algorithm performed better than deterministic, bounded enumerative search methods for 10% of the 538 problems tested. The test runs were performed with minimal attention to tuning of the genetic algorithm parameters. In most cases, better performance is possible simply by running the algorithm longer or by varying the selection method, population size or mutation rate. However, the results show the flexibility and robustness of a direct representation and hint at the possibilities of integrating the genetic algorithm approach with other methods. Thesis Committee: Mark Jakiela , Associate Professor of Mechanical Engineering, MIT Woodie Flowers, Pappalardo Professor of Mechanical Engineering, MIT Stephen Graves, Professor of Management Science, Sloan School of Management Karl Ulrich,...

Website: lancet.mit.edu | Filesize: -
No of Page(s): 62
Download A Genetic Algorithm for Resource-Constrained Scheduling - MIT.pdf