Real-time scheduling with deadlock avoidance in flexible manufacturing systems

The dynamic nature of manufacturing makes rescheduling essential in today's complex production environment, particularly in flexible and re-configurable systems. Research on optimising schedules, which includes deadlock avoidance, is rather limited. Furthermore, the deadlock problem is mostly ignored in research on rescheduling. A rescheduling algorithm, that uses time petri-nets and the minimal siphons concept, was developed to deal with sources of disturbance such as machine breakdowns in real-time. The algorithm guarantees a deadlock-free new schedule. The existence of alternative routes, availability of material handling facilities and the limitation of buffer capacities were taken into consideration. The developed algorithm modifies only the affected portion of the original schedule, rather than rescheduling all jobs, in order to limit changes to the original schedule and reduce the impact on the response time.The effect of flexible routing, machine breakdowns, machine downtime, routing criterion and the use of the dispatching rule on the performance of manufacturing systems was studied. The systems performance was measured by the average flow time, the makespan and the average machine utilisation. The results indicate that utilising the system routing flexibility in real-time rescheduling, while avoiding deadlocks, improves system performance. Moreover, routing the interrupted operation to an alternative machine, based on the minimum expected completion time rather than the least utilised machine criterion, resulted in better performance.