Scheduling and supervisory control of flexible manufacturing systems using Petri nets and heuristic search

The new scheduling method presented in this thesis formulates a scheduling problem with a timed place Petri net model. Once a complete model of the system is constructed, the scheduling algorithm uses this Petri net model to search a partial reachability graph. Depending on the heuristic functions used, the scheduling algorithm finds a globally optimal or near optimal feasible schedule in terms of the firing sequence of the transitions of the Petri net model. The formulation explicitly and easily handles the important characteristics of flexible manufacturing systems, such as routing flexibility, shared resources, concurrency, lot sizes and setup times. By setting the initial and the final markings appropriately, partial scheduling can be dealt with without any modification of the model. Rescheduling can be done with addition and subtraction of Petri net submodels and changes in the markings. By using appropriate functions or combinations of functions in the scheduling algorithm, other performance criteria or multiple performance criteria can be adapted. With simple changes in the Petri net model, the scheduling method can also handle periodic scheduling. The scheduling algorithm can be directly applied to the modified Petri net model. Hence the scheduling method that uses Petri net formulation and heuristic search can handle scheduling of both non-periodic and periodic flexible manufacturing systems. Scheduling models that integrate the part processing facilities such as machines and robots, and automated guided vehicle systems (AGVSs) for material handling, into a single coherent formulation are presented. This single formulation can be used to collectively schedule and control (supervisory) the entire FMS as opposed to the traditional separate scheduling of the part processing facilities and the material handling system. Experimental studies of the efficiency of some heuristic functions for the search are presented. A good heuristic function for the search can be quickly estimated from the Petri net model. From the above discussions, therefore, the new scheduling method presented in this thesis provides general and viable generative scheduling, and has excellent application potential. A limited comparative study provides some evidence that the scheduling method presented in this thesis compares favorably with heuristic dispatch rules found in the literature. Since a complete Petri net model of a system is obtained during the problem formulation, the generated schedule in terms of the firing sequence of the transitions can be used directly by employing Petri net controllers in the supervisory control of the modeled system. This contributes to the integration of scheduling and supervisory control of flexible manufacturing systems. Once a schedule to reach a desired final state is generated, potential deadlocks can be avoided by following the schedule. Hence the analytical overhead to guarantee the liveness of the model and the system is eliminated.