Scheduling And Resource Allocation With Genetic Algorithms

The efficient management of the distribution of goods and services is important throughout the minerals industry. From the scheduling of processing plant operations, to the routing of work crews in mines, to the planning of product development, vast amounts of time, energy, and money are wasted due to poor planning and scheduling. Thus, the U.S. Bureau of Mines is investigating computational algorithms that can be used to minimize the economic losses related to scheduling and allocating resources. Although there is commercial software available for tackling many scheduling problems, there has been little relief provided for solving the difficult traveling salesman with time windows problem (TSTW). The TSTW problem is a "derivative" of the classic traveling salesman problem, and can be used to minimize the distance traveled by vehicles or personnel to visit all points on a tour, with the additional constraint that each point on the tour must be visited within a specified time window. This paper is a survey of published work in which genetic algorithms have been used to efficiently solve the traveling salesman problem and its more difficult derivative, the TSTW problem. A genetic algorithm is a search algorithm based on the mechanics of natural genetics, and has been used to solve a broad spectrum of engineering optimization problems. Results indicate that the versatility, searching power, and simplicity of genetic algorithms can be used to provide substantial improvement in the area of scheduling and resource allocation.