The Application of a Genetic Algorithm to a Scheduling Problem
Date
1995-08
Authors
Journal Title
Journal ISSN
Volume Title
Publisher
ORCID
Type
Degree Level
Masters
Abstract
Over the past three decades a significant amount of time and effort has been
expended in an attempt to optimize complex scheduling problems as a way to
reduce costs. These scheduling problems are often difficult to solve because of
their combinatorial nature.
Many Civil Engineering problems deal with the logistics of coordinating the
movement of goods or people between various modes of transportation.
Problems of this type, which can be classified as Doubly Constrained
Traveling Salesman Problems (DCTSP), are particularly difficult because the
deliveries must be made within pre specified windows of opportunity.
The Genetic Algorithm (GA) has been identified as a method to solve
combinatorial problems. Its capability to solve complex scheduling problems
has been explored herein by applying the GA technique to a complex real
world scheduling problem which can be modeled as a DCTSP. The problem
selected was the design of the National Hockey League's (NHL) 1992-1993
playing schedule. The NHL playing schedule was selected because: it is easily
modeled as a DCTSP, the data necessary to formulate the problem was readily
available, and the existing solution could act as a benchmark to measure the
GA's performance.
To illustrate the robustness of the GA it was applied to a variety of classical
Operations Research (OR) problems. Solving the OR problems provided an
excellent opportunity to compare the performance of various GA modeling
techniques. When applying the GA to the NHL scheduling problem, the
problem size and complexity was increased incrementally. Initially the GA
was used to optimize the schedule only on distance. Next, optimization was
based on meeting a subset of the NHL's constraints as well as minimizing
distance traveled. Finally, the GA was used to optimize the schedule by
meeting the complete set of constraints and minimizing the distance
traveled.
The GA illustrated its flexibility by solving the OR test suite with minimal
modifications. As the problems became more difficult new chromosome
structures and reproduction schemes were introduced to improve the GA's
performance. In the NHL scheduling application the GA was able to create
scheduling solutions but it was unable to improve upon the schedule recently
developed using the Decision Support System now in use by the NHL.
The GA's failure was attributed to one, or a combination of, three factors:
limited computer resources, chromosomes were not adequate representations
for the problem, and the problem space was either too large or deceptive for
the GA to find a local optima.
The GA is a robust tool. It can solve a variety of linear and non-linear
problems. This in turn suggested, and was shown to be true, that it can solve
problems with hybrid characteristics such as the doubly constrained traveling
salesman problem
Description
Keywords
Citation
Degree
Master of Science (M.Sc.)
Department
Civil Engineering
Program
Civil Engineering