| Modern society features with intensive competition in market and certain ?uctua-tion in demand. Companies cannot stay competitive if they totally rely on traditionalmass production systems. Hence, they have gradually resorted to automated manufac-turing systems (AMS). Consequently, it attracts a great deal of research attention toanalyze and control such systems. This thesis focuses on the investigation of various su-pervisory control theories and techniques in the context of AMS. It is supported in partby two grants from National Science Foundation of China, under grants 60474018 and60773001, and entitled"Deadlock analysis and control in AMS using Petri nets"and"Elementary siphon theory in Petri nets", respectively. It is also supported in part byScientific Research Foundation for Returned Scholars, Ministry of Education of China,under grant 2004-527, Laboratory Foundation for Returned Scholars, Ministry of Edu-cation of China, under grant 030401, and the National High Technology Research andDevelopment Program("863"Program) of China, entitled"Design of multiple life-cycleand green electronic products", under grant 2008AA04Z109.This thesis investigates some key technical problems in manufacturing industry,which is largely related to the economy of our nation and the welfare of our people.As known, the competitiveness of an advanced manufacturing industry is significantlydependant on the advancement of its underlying manufacturing systems. In the presentand foreseeable 20 to 30 years, there is no doubt that modern manufacturing systems,e.g., advanced semiconductor manufacturing systems, can strongly support and main-tain the sustainable development of our national economy. Also, they constitute animportant part in demonstrating our comprehensive national strength. The wide adop-tion of information technology in manufacturing systems changes an increasing numberof mechanized systems into automated ones and rigid systems into ?exible ones. As aresult, modern manufacturing systems evidently appear as complex and large-scaled sys-tem with multiple objectives, multiple constraints, dynamics, and strong discreteness.During the past two decades since 1990s, it becomes a challenging scientific problemto model, analyze, and control such systems in the field of control theory. It is a keytechnological one to be solved in manufacturing industry. It is noteworthy that manyscientists show great research interest in such research field. Most of them are fromdeveloped countries and areas such as the United States and Canada in North Amer-ica, Germany, France, Italy, and Spain in Europe, Japan, Korea and Taiwan in Asia.Some investigation shows that its yearly profit increasement can be calculated in units of millions of dollars if there is one percentage of increasement in the automation levelof a semiconductor production line.AMS are regarded as a kind of resource allocation systems composed of such re-sources as manufacturing centers, robots, and conveyers. In AMS, several raw partsand semi-finished products are processed and manufactured through predefined routes.Deadlock may occur due to the competition for the limited resources among these con-current manufacturing processes. Schemes are needed to appropriately assign resourcesto di?erent products. This assignment must ensure the system performance withoutcausing deadlocks. Most AMS belong to discrete event systems (DES) as they featurewith a discrete event-driven property. Their trajectory is discrete not only in time butalso in space. Their characters include asynchrony, concurrency, and uncertainty. Petrinets can describe DES in a compact and formal way. Thus, they are widely utilized anddeveloped in the modeling, analysis, and control of AMS. In terms of their role in DES,Petri nets are equivalent to di?erential and di?erence equations in continuous systems.This thesis focuses on the deadlock-freeness analysis and control for AMS. Such topicsare of appreciable theoretical and practical significance for both AMS and Petri nettheory. They are very challenging. Informally speaking, deadlock-freeness in AMS canbe analogous to stability in continuous systems. No matter how good performance anAMS has, deadlocks in its operation are unacceptable. This is because deadlocks at anytime imply the stagnation at that time, which leads to serious and even catastrophicconsequences.This thesis makes the following pioneering and promising research contributions asbrie?y summarized as follows.First, this thesis for the first time proposes that the set of elementary siphons isnot unique. This is owing to the fact that a set of elementary siphons corresponds to aset of independent linear vectors given dependent vectors. A system can be controlledby considering only the elementary siphons. This principle can facilitate the simplifi-cation of a supervisor structure. However, the resultant number of reachable states inthe controlled net can be quite di?erent when di?erent sets of elementary siphons arecontrolled. Therefore, the non-uniqueness of elementary siphons inspires us to searchfor a set of elementary siphons that may lead to the most reachable states. This issueis of great significance in control theory and industrial practice. As a consequence, thisthesis proposes the concept of optimal elementary siphons. With regard to elementarysiphons, the other siphons are dependent ones. Generally speaking, the set of optimalelementary siphons is a set of siphons which can produce the largest set of reachablestates. However, such definition is too general and of only theoretical significance. This is because it is impractical to enumerate either all the siphons or all the reachablestates for a large net. This thesis shows that a set of elementary siphons can be con-trolled to ensure its controlled systems to produce the most reachable states when allthe other siphons are strongly dependant on them. This discovery also makes it feasibleto compute optimal elementary siphons in practice. Furthermore, this thesis proposesan algebraic algorithm to derive them.The investigation shows that a siphon must be a member in the set of optimalelementary siphons if it cannot be linearly represented by the other siphons in termsof their transition characteristic vectors. This result elegantly changes a combinationaloptimization problem to a linear programming problem. The former proves to be ofexponential time complexity while the latter is of polynomial one. As a result, muchachievement is made in the aspect to derive the set of optimal elementary siphons.The existing research of elementary siphons is largely limited to the context of ordinaryPetri nets, which is not suitable for the analysis and control of more structurally complexAMS. This thesis extends the concept of elementary siphons to general net systems. Newtechniques are proposed by su?ciently considering the sophisticated resource allocationcharacteristics in AMS. With the aid of the insu?ciently marked siphons instead ofthe emptied ones, this thesis describes the mechanism for deadlocks to occur in AMSfrom a broad viewpoint. Compared with the existing methods, the proposed approachcan greatly reduce the control complexity and improve the performance of controlledsystems. In addition, it reduces the computational burden to design a controller andestablish theoretical basis for further research. Moreover, the approach in this thesiscan also be successfully applied to other resource allocation systems. This shows itssolid theoretical foundation and its potential of industrial applications. The majorcontributions in this part of research are published in IEEE Transactions on Systems,Man, and Cybernetics - Part C: Applications and Reviews, 2007, IEEE Transactionson Automation Science and Engineering, 2009, and IEEE Transactions on Multimedia,2009.Second, this thesis identifies deadlock and ratio control issues in AMS. The ap-proach is inspired by the invariant properties of Petri nets. The concern of the firstissue is to avoid the occurrence of deadlock situations so as to inhibit stagnation andstandstill of job processing in an AMS. The other issue involves the determination ofa reasonable regulation scheme such that a desired production ratio can be guaranteedamong di?erent processes. Without the aid of invariant properties, one needs to resortto the reachability graphs and identify the critical manufacturing paths, states, andevents. To avoid deadlocks, low priority may be assigned to an event that can lead the system from a live state to deadlock. To satisfy ratios, a fixed probability is assignedto each manufacturing process. Obviously, neither priority nor probability can helpavoid deadlocks or ensure the desirable ratio. More importantly, these pre-determinedschemes cannot properly accommodate uncertainties or variations that a practical sys-tem exhibits. As a result, the real priority and probability can significantly drift awayfrom their predefined values. Also, in the same system, it also becomes quite challeng-ing, and completely impossible in many cases, to coordinate the ratio assignment anddeadlock resolution in one system. To the best of our knowledge, there is no researchto integrate these two schemes together to resolve such issues.On the basis of the invariance principle of Petri net models, this thesis integratesthe abovementioned two schemes together through supervisory controllers. To prop-erly tackle such an issue, this thesis proposes two new classes of Petri nets. They aresuitable to model AMS allowing ?exible routes and assembly operations, respectively.At each operation stage, both of them allow the multiple acquisition of more than onetype of resources. This ensures the general applicability of the research results. Thisthesis theoretically proves that no new siphons can be induced after the introductionof ratio-enforcing supervisors. In other words, no additional deadlock can result by thesupervisor to ensure a given ratio. This implies that one can design and implementliveness and ratio-enforcing supervisors independently. A novel approach is proposed toiteratively produce undermarked siphons as the solutions of a set of linear inequalities.This also results in a quite e?cient design algorithm for supervisors. It can solve thedeadlock detection problems in the general nets by a simple mathematical programmingmethod rather than a complicated enumeration operation. The latter proves to be ex-ponential in its time complexity. It can identify and control all deadlock states andtheir corresponding siphons without enumerating them. On the other hand, the derivedmathematical programming models can intuitively explain the relationship between thedeadlock states and undermarked siphons, thus providing the mathematical fundamen-tal for further development of more e?cient deadlock resolution policies. The majorcontribution in this part of research is published in IEEE Transactions on Systems,Man, and Cybernetics - Part A: Systems and Humans, 2010. Related results will alsoappear in IEEE Transactions on Industrial Informatics, 2010.Third, this thesis proposes a method to realize liveness-enforcing supervisors withlow-cost and high-performance in the framework of AMS considering resource allocationmechanisms. In any practical AMS, a controller has two parts, i.e., observation andcontrol units. They correspond to in-going and out-going arcs of control places inPetri net models, respectively. In other words, a controller is composed of sensors and actuators. Apparently, the system structure can be overly-complex owing to sensors andactuators if they are excessive in their number or unreasonable in their design. Also, thismeans the increase of implementation cost and failure probability. Despite its extremeimportance, this issue is largely ignored in the existing literature. Also, few studiesquantitatively analyze the performance of these controlled systems and their e?ciencyunder the supervisors. Thus the existing methods often lead to high implementationcost, restrictive constraint, and low e?ciency of AMS. This thesis presents a methodto derive the supervisors with minimum costs and reduce the control cost for systems.On the basis of this, it extends the result to timed Petri nets in order to facilitate thecomprehensive evaluation of the control cost and operation e?ciency. In fact, these twoindices prove to be contradictory to each other in many situations. One must sacrificethe system performance to achieve a reasonable implementation cost of a supervisor;otherwise, one must bear the higher cost to improve the systems performance. With theaid of a weight coe?cient method, this thesis proposes a mathematical programmingapproach to comprehensively evaluate multiple control objectives. The method can beapplied to make a good trade-o? between the supervisor implementation cost and systeme?ciency.In this thesis, for Petri net models, each transition is associated with an observationand control cost, which represent the implementation cost of a sensor and an actuatorat certain physical positions. A mathematical programming approach is devised to ef-fectively determine the supervisor with minimum comprehensive cost. This method isapplied to AMS allowing ?exible routes and assembly operation, respectively. The ex-perimental results prove its e?ectiveness and e?ciency. To keep the balance betweenthe supervisor implementation cost and the system throughput, the places or transitionsare further associated with time information so as to re?ect their temporal characteris-tics. Specifically, this thesis proposes two new classes of Petri nets, which can deal withthe time aspects properly. The research results show two scenarios. First, for the sys-tems allowing assembly operations, time delays associated with Petri nets cannot causedeadlock. Therefore, a mathematical programming method can be directly applied toachieve supervisors with low cost and high performance. Second, for the systems allow-ing ?exible routes, time delay and di?erent choices of processes may lead to deadlock.As a consequence, one needs to make appropriate pretreatment before the design of su-pervisors. To this end, this thesis proposes the application of ratio supervisor to avoidthe occurrence of potential deadlock phenomena among di?erent routes. The majorcontribution in this part of research is published in IEEE Transactions on AutomationScience and Engineering, 2010. Some related results are submitted to IEEE Transac- tions on Automation Science and Engineering and IEEE Transactions on AutomaticControl for review.Fourth, this thesis proposes a synthesis policy to design supervisors for AMS consid-ering the global time information. The policy proves to be of polynomial time complexityto enforce a constraint. As a physical system in the real world, the operation of AMSis dependant on the time. Thus, time dimension is of great significance and must becombined with the plant model of a system. Accordingly, many control specificationsmust be temporal rather than only algebraic or logical one in most prior research. In thisregard, many existing approaches are based on the application of supervisory controltechnique of automata and its combination with regional theory. It proves that suchkinds of methods are NP complete. This is because that either automata or regionaltheory requires the enumeration of all states whose quantity increases exponentially withthe size of the system. This thesis shows that this problem is solvable in polynomialtime through the application of general linear constraints. Compared with linear mark-ing constraints, general linear constraints are quite powerful in their description ability.By dividing each constraint into marking, firing vector, and Parikh terms, its respectivecontrol place can be synthesized algebraically without considering the separation of thedangerous states and events; otherwise, one needs to establish the reachability graph, toenumerate all the reachable states, to search for all the directed circuits, and to composealgebraic equations for all these circuits. Any of these operations means a huge amountof storage and computation even for a system with moderate size.This thesis pays attention to the impact of global time in the design process of asupervisor. It proposes a new class of Petri nets to involve global time information.Such Petri nets are composed of two parts. One is devoted to the description of alogical structure for AMS while another one is dedicated to the explicit representationof global time. Apparently, the former is observable and controllable whereas the latteris observable but uncontrollable. This is because that time cannot be stopped in anysituation. In the case of purely logical control, the occurrence of an operation event isdetermined by its fulfillment with certain logical constraints. In the case that globaltime information is involved, the occurrence of an operation event is determined byits simultaneous satisfaction with the logical and temporal constraints. This thesispresents an algebraic method to realize the Petri net supervisor by considering timewithout the adoption of its reachability graph. Since general linear constraints candivide the incidence matrix into input and output ones, self-loops are allowed for asupervisor. This technique can e?ectively solve the di?cult control problem in thecase that uncontrollable events are involved. Furthermore, self-loops make it possible that the firing of certain uncontrollable transitions cannot be a?ected by the outgoingarcs from a control place to this transition. This can avoid the necessity to convert aconstraint to be a more restrictive one and thus e?ectively ensure the optimality of aresultant system. The major contribution in this part of research is published in IEEETransactions on Automation Science and Engineering, 2010.
|
PDF Full Text Request