Intelligent Scheduling Technology In Flexible Manufacturing Shop Floor Based On Mechanism Of Autonomy And Coordination

Scheduling problems in flexible manufacturing environment possess features of high complexity, uncertainty, multi-objects, coordination of multi-constraints and multi-resources, etc. Due to their important significances in theory and industrial practice, scheduling problems in flexible manufacturing environment have been extensively studied over the last five decades, and continue to attract the interests of researchers both in academia and industry.To provide effective and efficient solutions to the scheduling problems in discrete job shop with multiple cells each having flexible process routings, this dissertation presents a Holon-based autonomic and coordinated intelligent scheduling technique, which is integrated with reinforcement-learning-based contract net protocol (CNP) and modified filtered-beam-search (FBS) algorithms, based on the recent researches in Agent or Holon-based decentrated production scheduling. The proposed intelligent scheduling technique is studied based on the key techniques of Agent or Holon-based autonomic and coordinated scheduling, i.e., encapsulation of entities, the control architectures, coordinated mechanism and core autonomic algorithms.The main contributions of the dissertation are described as follows:1. Firstly, the state-of-the-art of Agent or Holon-based autonomic and coordinated scheduling and the key techniques (i.e., encapsulation of entities, the control architectures, coordinated mechanism, core autonomic algorithms, as well as learning mechanism) are reviewed, and the existing problems in these fields are discussed, which leads to the driving force and significances of this research;2. To fulfill the requirements of reliability, extensibility and adaptability, this dissertation proposes a Holon-based control architecture for flexible manufacturing shop floor using a bottom-up design approach. The inner structure of component Holon (mainly Cell Holon), the relationships of data and functions among Holons, the model of message transfer and the basic specification of communication language are described in detail. Then, from the aspect of software architecture, a formal description and analysis of the proposed architecture is conducted by First-order Polyadic pi-Calculus. This lays the foundation for the next Holon-based autonomic and coordinated scheduling.3. Since it only defines the basic process of interactions among Agents or Holons, the basic contract net protocol for manufacturing scheduling is lack of the capability of optimization and dynamic learning. To overcome this issue and to improve its real-time adaptive capability for dynamic environment, a coordinated mechanism named after CNP-QL(Contract Net Protocol-Q Leaning)is proposed, which results from the integration of basic CNP for manufacturing scheduling and Q-leaning algorithm. To implement the CNP-QL mechanism, the main elements of the mechanism are defined and described, including the message description, the decision process, the interaction process for learning and key elements of Q-learning algorithm (e.g., the criterion of state determination, state space division, the reward function and the definition of search strategy, etc.). Then, to testify the effectiveness of the CNP-QL, the CNP-QL is used to solve the dynamic coordination problem of tasks among multiple cells with flexible process routings. And the effectiveness of the CNP-QL is demonstrated through simulations with comparison of the basic CNP.4. Since the scheduling algorithm is the engine for the autonomic decision of a cell, this dissertation proposes a mechanism for autonomic scheduling of a cell, in which a heuristic based on Filtered-Beam-Search algorithm (HFBS) is as the core. To solve the Flexible Job-shop Scheduling problem after the task coordination among alternative cells, a mathematic model with multiple objectives is built and the analysis of the model complexity is discussed. Then, four key elements of the HFBS, namely, the solution space for the problem, the selection of beamwidth and filterwidth, the generation procedure of branches and selection of evaluation functions are illustrated in detail. Finally, based on the performance analysis of key elements of HFBS, the performance of HFBS are evaluated and compared with those of other AI-based heuristics and dispatching rules via benchmarks and simulation examples. The results demonstrate the effectiveness of HFBS.5. To realize the continuous optimization of cell autonomic scheduling and to improve its real-time adaptive capability for unanticipated or stochastic internal and/or external disturbances (e.g., machine breakdown, new job arrival, etc.), a dynamic rescheduling decision process is proposed based on the description of theory of dynamic rescheduling (including rescheduling environment, strategy, approaches and techniques). Meanwhile, a FBS-based heuristic algorithm is proposed, which makes improvement of FBS algorithm in the generation procedure of branches and the local/global evaluation functions. Thus, it can easily consider and incorporate the due dates and priority weights of jobs and machine workload balance during the process of assignment jobs to machines. Then, the worst-case time complexity is analyzed. Finally, with respect to a due date-based objective, (weighted quadratic tardiness), computational experiments are conducted to evaluate the performance of the proposed algorithm in comparison with those of other popular methods. The results show that the proposed FBS-based algorithm performs very well for dynamic rescheduling in terms of computational efficiency and solution quality.6.Finally, based on the JADE platform, a preliminary prototype is designed and developed, in which JADE Agent is used to represent Holons mentioned above. The main functions of negotiation between Holons and their autonomous scheduling decisions are shown in this prototype. This in turn will lay the foundation for the future practical implementation of Holon-based scheduling and rescheduling in shop floor.The research makes some contributions in key techniques of Agent or Holon-based autonomic and coordinated scheduling approach. It can be used to improve the production management and control, and it can give some guidelines to enhance production performance and to improve the competitive capability in complex market. In addition, if modified and further studied in this direction, the thought and the results of this research is promising for solving other combinatorial optimization problems and complex scheduling problems, and it is also promising for practical potential implementation.Acknowledgement This dissertation is supported by the National High Technology Research and Development Program of China under grant 2003AA414120, the National Key Lab. Program under grant 51458060104JW0316 and the Trans-Century Training Programme Foundation for the Talents by the State Education Commission 2006.