A GENETIC ALGORITHM APPROACH TO THE SIMULTANEOUS SCHEDULING OF MACHINES AND AUTOMATED GUIDED VEHICLES

This article addresses the problem of simultaneous scheduling of machi nes and a number of identical automated guided vehicles (AGVs) in a fl exible manufacturing system (FMS) so as to minimize the makespan. For solving this problem, a genetic algorithm (GA) is proposed. Here, chro mosomes represent both operation sequencing and AGV assignment dimensi ons of the search space. A third dimension, time, is implicitly given by the ordering of operations of the chromosomes. A special uniform cr ossover operator is developed which produces one offspring from two pa rent 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 assignm ents and a swap mutation for operations. Any precedence infeasibility resulting from the operation swap mutation is removed by a repair func tion. The schedule associated with a given chromosome is determined by a simple schedule builder. After a number of problems are solved to e valuate various search strategies and to tune the parameters of the pr oposed GA, 180 test problems are solved. An easily computable lower bo und is introduced and compared with the results of GA. In 60% of the p roblems 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.