The Application of a Genetic Algorithm to a Scheduling Problem

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 proble