Description
Date depot: 1 janvier 1900
Titre: Optimal Supervisory Control of Flexible Manufacturing Systems
Directeur de thèse:
Kamel BARKAOUI (CEDRIC)
Domaine scientifique: Sciences et technologies de l'information et de la communication
Thématique CNRS : Non defini
Resumé:
Flexible manufacturing system (FMS) is an automatically running system, which consists of a finite number of shared resources such as machines, automated guided vehicles, robots, and buffers. In an FMS, since parts are processed in a pre-established sequence to compete for a limited number of system resources, deadlocks can occur when some processes keep waiting indefinitely for other processes to release resources. In FMSs, deadlocks are a highly undesired situation, which always cause unnecessary cost and even may lead to catastrophic results in these systems. In order to meet the production requirements of a system and make the best use of the system resources, an effective deadlock control policy must be designed and implemented to ensure that deadlocks can never occur.
Generally, there are three very important criteria in evaluating the performance of a liveness-enforcing supervisor for a system to be controlled: behavioral permissiveness, structural complexity and computational complexity. A maximally permissive supervisor has the highest potential to lead to high utilization of system resources; A supervisor with a small number of control places can decrease the hardware and software costs in the stage of control validation and implementation; A deadlock control policy with low computational complexity means that it can be applied to complex systems. Thus, many researchers try their best to develop deadlock prevention algorithms that can obtain liveness-enforcing supervisors with maximal permissibility, a simple supervisory structure, and low computational complexity.
Based on reachability graph analysis, an optimal or suboptimal supervisor with high behavioral permissiveness can always be achieved. This thesis focuses on designing liveness-enforcing Petri net supervisors for FMSs by considering their behavioral permissiveness, supervisory structure, and computational complexity. The reachability graph of a net is classified into two parts: live-zone (LZ) and deadlock-zone (DZ). First-met bad markings (FBMs) are first derived from the reachability graph. An FBM is a marking in DZ, representing the very first entry from LZ to DZ. A maximally permissive control place is designed by a place invariant (PI) that forbids an FBM and no legal marking is forbidden. The PI is computed by solving an integer linear programming problem (ILPP). In order to overcome the complexity of this method, a vector covering approach is developed to reduce the sets of legal markings and FBMs to two small ones, i.e., the minimal covering set of legal markings and the minimal covered set of FBMs. Then, only the two reduced sets are considered for the design of a supervisor. In this case, the computational burden is greatly reduced since the number of constraints in an ILPP decreases remarkably. we propose an approach that can obtain a maximally permissive liveness-enforcing supervisor with the minimal number of control places. It is a non-iterative approach since all control places can be once obtained by solving an ILPP. Though this approach overcomes the problems of both behavior permissiveness and structural complexity, it still suffers from expensive computational cost. Finally, we consider a well trad-off between structural complexity and computational complexity, i.e., efficiently designing a maximally permissive supervisor with a small number of control places.
Doctorant.e: Chen Yufeng