Discrete Event Systems And Their Distributed Supervisory Control Theory

Manufacturing systems experiences dramatic changes thanks to the emergence of in-tensive market competition and the availability of computer and automation technology.To facilitate quick response to the market change and allow mass product customization,indus-trial practitioners resort to automated manufacturing systems(AMSs)which generally con-sist of a group of numerically-controlled machines,interconnected by a centralized control system,via loading,unloading,and storage stations,as well as through automated material handling systems.In practice,the avoidance of undesired behaviors requires the synthesis of supervisor upon all the possible system behavior,i.e.,the plant.In terms of AMSs,one of paramount properties is to ensure the noblockingness of systems.Based on this property,a series of control methods for deadlock problem have been developed by many researchers.In these existing control methods,a centralized control method is the most common method.In industry,most practical AMSs are always constituted by collections of small-sized,local,interacting,asynchronous,event-driven subsystems.Apparently,as the number of mod-ules increases,state explosion issue occurs when designing a monolithic and centralized supervisor.Moreover,all the monolithic approaches are not applicable to the real-world ap-plications because of the obstacles from the supervisor synthesis procedures in conventional supervisory control techniques(SCTs).In the past decades,many approaches have been conducted with an attempt to overcome the computational complexity issues;however,few of them really make progress.Taking Petri Nets(PNs)as mathematical tools,this thesis focuses on the deadlock-freeness analysis and distributed control for AMS.In the case of avoiding the enumeration of all the states,the liveness of the system can be ensured through monitoring the local states predicting the global information.The main results of this research are as follows.First,considering the systems with assembly operation,a special class of PNs,namely,Feedback Augmented Marked Graph(F-AMG)and the distributed control method based on it are developed.In F-AMG,after being processed in disassembly operation,a complete process is disassembled into multiple sub-processes.These disassembled sub-processes un-dergo further transport/processing individually and then synthesis a new process.Motivated by such structural features,three concepts,i.e.,sub-critical place,local critical place and global critical place,are first proposed.The difference in controlled object,i.e.,process and sub-process,provides a subdivision for the control method.For a complete process,other unchecked processes have no effect on its determining procedure,while for a sub-process,other sub-processes disassembled from the same process will have an impact on its verifica-tion.In other words,the determination of process is in the form of individual object,while the verification of sub-process is in the form of group.Second,for the systems embedding flexible routes into disassembly/assembly opera-tions,a special class of PNs,namely,Augmented Extended Marked Graph(AEMG)and the distributed control method based on it are developed.This work reveals the structural rules of critical places and propose corresponding control methods for different sub-process sets.Different from F-AMG,the disassembled sub-process in AEMG can select assembly routes to be processed arbitrarily.As a result,when determining critical place,only the assembly route set with minimum routes needs to be considered.In AEMG,the diversity of assembly routes classifies the controlled object into the sub-process sets from the same process and sub-process sets from different process.For the former,the control method based on F-AMG can be enforced on it,while for the latter,the lateral and hierarchical control strategy is developed.Third,for the systems assembling parts in batch,a special class of PNs,namely,Forward-conflict Free Net(FCFN)and the distributed control method based on it are developed.In FCFN,a set of sub-processes disassembled from the same process are assembled in batch.Such structure makes us find that applying the control method based on F-AMG directly to FCFN is not feasible,largely because of the fact that the control method focusing on sub-process cannot involve all the sub-processes from the same process but different batches.As a result,whether the unchecked sub-processes can induce deadlock cannot be predicted.Combining the control method based on F-AMG with the structure of FCFN,the longitudi-nal and hierarchical control strategy is introduced into FCFN.Fourth,for the systems embedding disassembly/assembly operations into flexible routes,a special class of PNs,namely,Weighted Augmented Free-choice Net(WAFN)and the dis-tributed control method based on it are developed.In WAFN,after being processed at dis-assembly station,the disassembled sub-process can select different combinations to be pro-cessed through various assembly route sets.Because of the diversity of assembly route set,local critical places are classified into two categories.For the first one,the assembly route sets where they are located are from the same disassembly station,while for the second one,the assembly route sets where they are located are from different disassembly stations.When checking the sub-process,the corresponding control strategy is imposed on it according to the selected combination.For the sub-process set disassembled from the same process,a search and prediction procedure is conducted on it,but for the sub-process set disassembled from the same process,the similar search and prediction procedure is required to be executed multiple times.This work also makes a comparison between the proposed control method and siphon-based method.The limitations existing in siphon-based methods,i.e.,negative coefficient problem and unpredictability of iterations,are fully presented.Fifth,considering the systems with multi-layer and hybrid assembling,a special class of PNs,namely,Augmented Hierarchical Marked Graph(AHMG)and the distributed control method based on it are developed.The structural analysis for AHMG reveals the deadlock formation:the circular wait of resources and the circular wait of sub-process to be assem-bled.Motivated by this feature,deadlock avoidance policies for these two deadlock circuits are proposed.In parallel with the development of deadlock control policies,an improvement is made for the achieved control method.For the sub-process set from different processes,a series of properties are deduced from the existing results,which can be used for the hierar-chical control.Finally,future research for optimization of system permissiveness and deadlock solu-tions based on structural analysis are prospected.