Scheduling and deadlock avoidance of a flexible manufacturing system

Addresses the scheduling and deadlock avoidance of a class of manufacturing systems with multiple resources. A set of jobs is to be processed and each job requires a sequence of operations. Each operation may need more than one resource. The processing time of each operation is deterministic. Upon the completion of an operation, resources still in need in the next operation of the same job cannot be released and the remaining resources cannot be released until the start of the next operation. The scheduling problem consists in sequencing the operations on the resources in order to avoid deadlocks and to minimise the makespan. We first model the system using Petri nets, formulate deadlock constraints in terms of a PN model, and establish feasibility conditions of a given schedule. Finally, a heuristic proposed to obtain deadlock-free schedules. The heuristic schedules the jobs one after another. For each job, the scheduling problem consists in minimising its completion time without modifying the schedules of the scheduled jobs. A dynamic programming approach is proposed to solve this one-job scheduling problem and two examples are scheduled.