کاربرد الگوریتم ترکیبی مبتنی بر تئوری بازی های برای برنامه ریزی فرایند یکپارچه چندهدفه و زمان بندی

Process planning and scheduling are two key sub-functions in the manufacturing system. Traditionally, process planning and scheduling were regarded as the separate tasks to perform sequentially. Recently, a significant trend is to integrate process planning and scheduling more tightly to achieve greater performance and higher productivity of the manufacturing system. Because of the complementarity of process planning and scheduling, and the multiple objectives requirement from the real-world production, this research focuses on the multi-objective integrated process planning and scheduling (IPPS) problem. In this research, the Nash equilibrium in game theory based approach has been used to deal with the multiple objectives. And a hybrid algorithm has been developed to optimize the IPPS problem. Experimental studies have been used to test the performance of the proposed approach. The results show that the developed approach is a promising and very effective method on the research of the multi-objective IPPS problem. Highlights ► Propose a game theory based hybrid algorithm. ► Solve the multi-objective integrated process planning and scheduling problem effectively. ► The Nash equilibrium in the game theory has been used to deal with the multiple objectives. ► The hybrid algorithm has been applied to optimize the IPPS problem. ► Some solutions are better than the solutions of some other approaches.

Process planning and scheduling are two key sub-functions in a manufacturing system. A process plan specifies what raw materials or components are needed to produce a product, and what processes and operations are necessary to transform those raw materials into the final product. The outcome of process planning is the information required for manufacturing processes, including the identification of the machines, tools, fixtures, and a job may have one or more alternative process plans. Process planning is the bridge of the product design and manufacturing. With the process plans of jobs as inputs, a scheduling function is to arrange the operations of all the jobs on machines while precedence relationships in the process plans are satisfied. Scheduling is the link of the two production steps which are the preparing processes and putting them into action. Although there is a close relationship between process planning and scheduling, the integration of them is still a challenge in both researches and applications (Sugimura, Hino, & Moriwaki, 2001). In traditional approaches, process planning and scheduling were carried out in a sequential way. Those methods have become the obstacles to improve the productivity and responsiveness of the manufacturing systems and to cause the following problems (Kumar & Rajotia, 2003): • In traditional manufacturing organization, process planners plan jobs separately. For each job, manufacturing resources on the shop floor are usually assigned on it without considering the competition for the resources from other jobs (Usher & Fernandes, 1996). This may lead to the process planners favoring to choose the desirable resources for each job repeatedly. Therefore, the resulting optimal process plans often become infeasible when they are carried out in practice at the later stage (Lee & Kim, 2001). • Even though process planners consider the restrictions of the current resources on the shop floor, because of the time delay between planning phase and execution phase, the constraints considered in the planning phase may have already changed greatly; this may lead to the optimal process plans infeasible (Kuhnle, Braun, & Buhring, 1994). • Traditionally, scheduling plans are often determined after process plans. In the scheduling phase, scheduling planners have to consider the determined process plans. Fixed process plans may drive scheduling plans to end up with severely unbalanced resource loads and create superfluous bottlenecks. • In most cases, both for process planning and scheduling, a single criterion optimization technique is used for determining the best solution. However, the real production environment is best represented by considering more than one criterion simultaneously (Kumar & Rajotia, 2003). Furthermore, the process planning and scheduling may have conflicting objectives. Process planning emphasizes the technological requirements of an operation, while scheduling involves the timing aspects. If there is no appropriate coordination, it may create conflicting problems. To overcome these problems, there is an increasing need for deep researches and applications of the integrated process planning and scheduling (IPPS) system. It can introduce significant improvements to the efficiency of manufacturing through eliminating scheduling conflicts, reducing flow-time and work-in-process, improving production resources utilizing and adapting to irregular shop floor disturbances (Lee & Kim, 2001). Without IPPS, a true computer integrated manufacturing system (CIMS), which strives to integrate the various phases of manufacturing in a single comprehensive system, may not be effectively realized. Therefore, in a complex manufacturing situation, it is ideal to integrate the process planning and scheduling more closely to achieve the global optimum in manufacturing, and increase the flexibility and responsiveness of the systems (Li & McMahon, 2007). In the beginning research of CIMS, some researchers have found that the IPPS is very important to the development of CIMS (Tan & Khoshnevis, 2000). The preliminary idea of IPPS was introduced by Chryssolouris, Chan, and Cobb (1984) and Chryssolouris and Chan (1985). Beckendorff, Kreutzfeldt, and Ullmann (1991) used alternative process plans to improve the flexibility of manufacturing systems. Khoshnevis and Chen (1989) introduced the concept of dynamic feedback into IPPS. The integration model proposed by Zhang (1993) and Larsen (1993) extended the concepts of alternative process plans and dynamic feedback and defined an expression to the methodology of the hierarchical approach. Some earlier works of IPPS had been summarized in Tan and Khoshnevis (2000) and Wang, Shen, and Hao (2006). In recent years, in the area of IPPS, several models have been reported, and they can be classified into three basic models based on IPPS (Li, Gao, Zhang, & Shao, 2010a): nonlinear process planning (Kim et al., 1997 and Thomalla, 2001), closed loop process planning (Seethaler and Yellowley, 2000 and Usher and Fernandes, 1996) and distributed process planning (Wang et al., 2005 and Zhang et al., 2003). In the past decades, the optimization approaches of the IPPS problems also have achieved several improvements. Especially, several optimization methods have been developed based on the modern artificial intelligence technologies, such as evolutionary algorithms, simulated annealing (SA) algorithm, particle swarm optimization (PSO) algorithm and the multi-agent system (MAS) based approach. Kim, Park, and Ko (2003) used a symbiotic evolutionary algorithm for the integration of process planning and job shop scheduling. Shao, Li, Gao, and Zhang (2009) used a modified genetic algorithm (GA) to solve IPPS problem. Li, Gao, Shao, Zhang, and Wang (2010b) proposed the mathematical models of IPPS and an evolutionary algorithm based approach to solve it. Chan, Kumar, and Tiwari (2009) proposed an enhanced swift converging SA algorithm to solve IPPS problem. Guo et al., 2009a and Guo et al., 2009b proposed the PSO based algorithms to solve the IPPS problem. Shen, Wang, and Hao (2006) provided a literature review on the IPPS, particularly on the agent-based approaches for the IPPS problem. Wong, Leung, Mak, and Fung (2006) presented an online hybrid agent-based negotiation MAS for integrating process planning with scheduling/rescheduling. Shukla, Tiwari, and Son (2008) presented a bidding-based MAS for solving IPPS. Li, Zhang, Gao, Li, and Shao (2010c) developed an agent-based approach to facilitate the IPPS. Most of the current researches on IPPS have been concentrated on the single objective. However, because different departments in a company have different expectations in order to maximize their own profits, for example, the manufacturing department expects to reduce costs and improve work efficiency, the managers want to maximize the utilization of the existing resources, and the sale department hopes to better meet the delivery requirements of the customers, in this case, only considering the single objective can not meet the requirements from the real-world production. Therefore, further studies are required for IPPS, especially on the multi-objective IPPS problem. However, only seldom papers focused their researches on the multi-objective IPPS problem. Morad and Zalzala (1999) proposed a GA based on weighted-sum method to solve multi-objective IPPS problem. Li and McMahon (2007) proposed a SA based approach for multi-objective IPPS problem. Baykasoglu and Ozbakir (2009) proposed an approach which made use of grammatical representation of generic process plans with a multiple objective tabu search (TS) framework to solve multi-objective IPPS effectively. Zhang and Gen (2010) proposed a multi-objective GA approach for solving process planning and scheduling problems in a distributed manufacturing system. In this paper, a novel approach has been developed to facilitate the multi-objective IPPS problem. A game theory based hybrid algorithm has been applied to solve the multi-objective IPPS problem. The remainder of this paper is organized as follows: problem formulation is discussed in Section 2. In Section 3, the game theory model of the multi-objective IPPS has been presented. A proposed algorithm for solving multi-objective IPPS problem is given in Section 4. Experimental results are reported in Section 5. Section 6 is conclusions.

Considering the complementarity of process planning and scheduling, and the multiple objectives requirement from the real-world production, the research has been conducted to develop a game theory based hybrid algorithm to facilitate the multi-objective IPPS problem. In this proposed approach, the Nash equilibrium in game theory has been used to deal with the multiple objectives. And a HA has been used to optimize the IPPS problem. Experimental studies have been used to test the performance of the proposed approach. The results show that the developed approach has achieved satisfactory improvement. The contributions of this research include: • The game theory has been used to deal with the multiple objectives of the IPPS problem. This is a new idea on the multi-objective manufacturing problems, and it also can be used to deal with the multiple objectives of other problems in the manufacturing field, such as process planning problem, assembly sequencing problem, scheduling problems and so on. • To find optimal or near optimal solutions from the vase search space efficiently, a HA has been applied to the multi-objective IPPS problem. Experiments have been conducted and the results have shown the effectiveness of applying this approach.