SEARCH-BASED MAXIMALLY PERMISSIVE DEADLOCK AVOIDANCE IN FLEXIBLE MANUFACTURING CELLS
Open Access
Author:
Sidhu, Amiteshwar Singh
Graduate Program:
Industrial Engineering
Degree:
Master of Science
Document Type:
Master Thesis
Date of Defense:
None
Committee Members:
Richard Allen Wysk, Thesis Advisor/Co-Advisor
Keywords:
Problem Reduction Look Ahead Search Search Algorithms Flexible Manufacturing Systems Deadlock Avoidance Circuit Detection
Abstract:
A search based maximally permissive method for deadlock avoidance was developed in this research. The method developed is maximally permissive in that no safe part moves requests are denied. This leads to higher resource utilization than conservative approaches. Maximal permissiveness, however, is associated with a high computational expense.
Two different tree search strategies, a depth first search and a hybrid search, were developed to perform the look ahead evaluation of part move requests. Strategies for reducing the amount of search involved in deadlock avoidance were developed and are presented. A strategy for avoiding repetitive search is also presented.
A factorial experiment was conducted to evaluate the relative performance of the different deadlock avoidance algorithm combinations presented in this research. The results indicate that depth first search strategy when used with repeat avoidance performs better than the hybrid search.
From another experiment it was observed that evaluation of safety of most part move requests did not require evaluation of a large number of reachable states. Only a small percentage of part move requests required evaluation of a large number of reachable states.
