Deadlock-Free Scheduling And Control For Automated Manufacturing Systems

Automated manufacturing systems (AMS) are modern production facilities, which have easy adaptability to variable production plans and goals. This peculiarity of flexibility allows AMS to effectively respond to the changing market demands, so more and more manufacturers move to use AMS as a way to keep their competitive power. However, AMS usually exhibit a high degree of resource sharing, so when various jobs advancing through the system compete for limited resources, deadlock would occur if proper scheduling and control methods were absent. The deadlock involving a set of jobs may propagate to other jobs, eventually crippling the whole system, so deadlock could bring us a catastrophic failure. Therefore, it is highly important to develop efficient algorithm to avoid the deadlock situations. The investigations on deadlock resolution in automated manufacturing systems have received significant attention in the last decade both in academy and industry.In this dissertation, the deadlock problem is investigated from the perspective of scheduling and control. Petri net and digraph tools have been employed to model the AMS with different structures, and then based on the formal models, efficient deadlock scheduling algorithms and deadlock avoidance methods have been proposed:1. Timed Petri nets is used to model single-unit resource allocation systems and conjunctive resouce allocation systems without buffers in a Bottom-Up way, and then a new deadlock-free scheduling method based on genetic algorithm and Timed Petri nets model is proposed. The scheduling problem consists in finding a feasible transition firing sequence to avoid the deadlock situation and to minimize the total completion time of all jobs. In the proposed genetic algorithm with deadlock-free constraint, Petri net transition sequence is coded and a deadlock detection method based on siphon technology is addressed to reschedule the sequence of transitions. The enabled transitions are fired as early as possible and thus the quality of solutions can be improved. In the fitness computation procedure, a penalty item for the infeasible solution is involved to prevent the search process from converging to the infeasible solutions. The method proposed in this paper can provide a feasible scheduling strategy as well as enable the system to achieve good performance.2. An efficient algorithm based on genetic algorithm and graph theory for finding optimal deadlock-free schedules in manufacturing systems with central buffers and material handling systems with special vehicle buffers is presented. Deadlock avoidance policy is imbedded into the decoding procedure of genetic algorithm in order to satisfy the deadlock free constraint of chromosomes. Because of the peculiarity of scheduling problem, after adaptation of gene sequences, the feasibility of solutions can always be guaranteed. With the deadlock free scheduling algorithm, the optimal deadlock free schedules can be got under the restriction of different buffer numbers. 3. Two improved banker's algorithm for deadlock avoidance have been proposed. Based on digraph model, a distributed banker's algorithm for deadlock avoidance in automated manufacturing systems (AMS) is proposed. The digraph model is decomposed into sub digraphs and the distributed banker's algorithm is applied to each sub digraph locally and orderly according to a related sequence. The proposed algorithm is very suitable for these large AMS and it needs less on line computation cost than the classical centralized banker's algorithm, while maintaining the same system flexibility. For the AMS with flexible routing and multiple resource requests, two methods are employed to reduce the computation cost of traditional banker's algorithm. First, the terminal place of a processing path is introduced. Since each process is terminable when reaching to a terminal place, then the further checking of the process for the resource needs can be ignored. Second, in the banker's algorithm, we search for a terminable process in the subset of the processes, named the shortest distance process set, instead of the whole process set during each iteration, which could decrease the computation.4. According to the structure of digraph model, a distributed deadlock avoidance policy for flexible manufacturing systems is proposed. The whole digraph model is decomposed into subsystems, which could be controlled locally and independently by a suitable deadlock avoidance policy. For the potential restricted deadlock situation, we proposed a method to control the number of jobs in the whole subsystem in order to avoid such restricted deadlocks. The flexibility of the deadlock avoidance policy is demonstrated and the complexity analysis is given. It can be proofed that our method can accommodate more jobs in the system than the traditional method while guaranteeing that the system is deadlock-free.5. For the Petri net model with uncontrollable and unobservable transitions, a supervisor synthesis method based on inhibitor Petri net model and theory of regions has been proposed to resolve the potential deadlock situations. Based on the reachability graph, maximally admissible live state space and the set of state transitions the controller has to disable can be calculated. In order to inhibit the system to enter the unsafe states, control places and connected inhibitor arcs are added to supervise the operation of Petri net model. Necessary and sufficient conditions for the existence of controller to realize the maximally permissive controller have been proposed.