A hybrid GA/heuristic approach to the simultaneous scheduling of machines and automated guided vehicles

TLDR

Simultaneous scheduling of machines and identical AGVs in flexible manufacturing systems is an NP‑complete problem composed of two interrelated NP‑complete subproblems. The study seeks to minimize makespan in this simultaneous scheduling problem by developing a hybrid GA/heuristic coding scheme. The hybrid coding scheme combines genetic‑algorithm operators from scheduling literature with a heuristic component to solve the problem. Applied to 82 benchmark problems, the hybrid approach outperforms existing methods, showing superior performance.

Abstract

In this paper, the problem of simultaneous scheduling of machines and identical automated guided vehicles (AGVs) in flexible manufacturing systems is addressed with the objective of minimizing the makespan. This problem is composed of two interrelated decision problems: the scheduling of machines, and the scheduling of AGVs. Both problems are known to be NP-complete, resulting in a more complicated NP-complete problem when they are considered simultaneously. A new hybrid Genetic-algorithm/heuristic coding scheme is developed for the studied problem. The developed coding scheme is combined with a set of genetic algorithm (GA) operators selected from the literature of the applications of GAs to the scheduling problems. The algorithm is applied to a set of 82 test problems, which was constructed by other researchers, and the comparison of the results indicates the superior performance of the developed coding.