A hybrid heuristic search algorithm for scheduling flexible manufacturing systems

摘要

This paper presents a hybrid search algorithm for scheduling flexible manufacturing systems (FMS). The algorithm combines heuristic best-first strategy with controlled backtracking strategy. Timed (place) Petri nets are used for problem representation. Their use allows to explicitly formulate concurrent activities, multiple resources sharing, precedence constraints and dynamic routing in FMS operation. The hybrid heuristic search algorithm is combined with the execution of the timed Petri nets to search for an optimal or near-optimal and deadlock-free schedule. The backtracking strategy is controllable. One can only employ the pure best-first search to obtain an optimal schedule thanks to a proposed admissible heuristic function. The presented method is illustrated through an FMS scheduling problem.