ترکیبی مدل شبکه پتری و مبتنی بر هوش مصنوعی جستجوی دوگانه اکتشافی برای تولید انعطاف پذیر سیستم های- بخش II. جستجوی دوگانه اکتشافی

This two-part paper presents modelling and scheduling approaches of flexible manufacturing systems using Petri nets (PNs) and artificial intelligence (AI)-based heuristic search methods. In Part I, PN-based modelling approaches and basic AI-based heuristic search algorithms were presented. In Part II, a new heuristic function that exploits PN information is proposed. Heuristic information obtained from the PN model is used to dramatically reduce the search space. This heuristic is derived from a new concept, the resource cost reachability matrix, which builds on the properties of B-nets proposed in Part I. Two hybrid search algorithms, (1) an approach to model dispatching rules using analysis information provided by the PN simulation and (2) an approach of the modified stage-search algorithm, are proposed to reduce the complexity of large systems. A random problem generator is developed to test the proposed methods. The experimental results show promising results.

The increasing automation and complexity of manufacturing systems has highlighted the need for the development of improved scheduling and planning techniques for flexible manufacturing systems (FMS). The successful development of realistic scheduling and planning techniques for FMS could have a significant impact on the manufacturing industry. Production scheduling is concerned with the effective allocation of resources over time. The purpose of scheduling is to determine when to process which job by which resources so that production constraints are satisfied and production objectives are met. On-line scheduling is the automatic rescheduling of the system in response to, either disturbances in the plant operation mode, or to changes in product demand. The objective of this paper is to make a contribution to the solution of the scheduling problem through the combination of Petri net (PN) modelling and artificial intelligence (AI)-based heuristic search techniques. Many industry and research communities are now focusing on developing methods for quickly solving real-world scheduling problems—a challenge that maintains its momentum because no perfect solution has been found for all problems, due primarily to the complexity of FMS scheduling. The general FMS scheduling problem belongs to one of the NP hard combinatorial problems (Tzafestas & Triantafyllakis, 1998) for which the development of optimal polynomial algorithms is unlikely.

The combination of PN modelling and heuristic search methodologies has been presented in this paper. PN allows the systematic modelling of high abstractions of FMS. A new class of PN B-nets or Buffer-nets has been proposed and studied. A formal language for defining basic Job Shop Systems has been introduced and the semantics of this language has been presented. It has been shown that it is possible to obtain formalised heuristic information from the mathematical expression of a PN that can be integrated with the traditional search strategies. However, to make this integration useful, the complexity explosion for larger problems must be attacked. Two hybrid techniques based on the reduction of the scope of selection and recovery, respectively, have been developed and implemented in a hybrid algorithm. A comparison with a previous work (Lee & Dicesare, 1994) has shown very promising improvements.