A genetic algorithm approach to the simultaneous scheduling of machines and automated guided vehicles

This article addresses the problem of simultaneous scheduling of machines and a number of identical automated guided vehicles (AGVs) in a flexible manufacturing system (FMS) so as to minimize the makespan. For solving this problem, a genetic algorithm (GA) is proposed. Here, chromosomes represent both operation sequencing and AGV assignment dimensions of the search space. A third dimension, time, is implicitly given by the ordering of operations of the chromosomes. A special uniform crossover operator is developed which produces one offspring from two parent chromosomes. It transfers any patterns of operation sequences and/or AGV assignments that are present in both parents to the child. Two mutation operators are introduced: a bitwise mutation for AGV assignments and a swap mutation for operations. Any precedence infeasibility resulting from the operation swap mutation is removed by a repair function. The schedule associated with a given chromosome is determined by a simple schedule builder. After a number of problems are solved to evaluate various search strategies and to tune the parameters of the proposed GA, 180 test problems are solved. An easily computable lower bound is introduced and compared with the results of GA. In 60% of the problems GA reaches the lower bound indicating optimality. The average deviation from the lower bound over all problems is found to be 2.53%. Additional comparison is made with the time window approach suggested for this same problem using 82 rest problems from the literature. In 59% of the problems GA outperforms the time window approach where the reverse is true only in 6% of the problems. (C) 1997 Elsevier Science Ltd.