الگوریتم های ژنتیکی اصلاح شده برای برنامه ریزی عملیات تولید در خطوط ساخت بخش های متعدد

Manufacturing process planning for multiple parts manufacturing is cast as a hard optimization problem for which a modified genetic algorithm is proposed in this paper. A cyclic crossover operation for an integer-based representation is implemented to ensure that recombination will not result in any violation of processing constraints. Unlike classical approaches, in which the mutation operator alone is used to foil the tendency towards premature convergence, a combination of a neighborhood search based mutation operator and a threshold operator were implemented. This combined approach was designed to; (a) improve the exploring potential and (b) increase population diversity of neighborhoods, in the genetic search process. Capabilities of a modified genetic algorithm method were tested through an application example of a multiple parts reconfigurable manufacturing line. Simulation results show that the proposed modified genetic algorithm method is more effective in generating manufacturing process plans when compared to; a simple genetic algorithm, and simulated annealing. A computational analysis indicates that improved, near optimal manufacturing process planning solutions for multiple parts manufacturing lines can be obtained by using a modified genetic algorithm method.

One of the most important functions in manufacturing engineering is process planning. Manufacturing process planning has a wide engineering background. As pointed out in Scallan (2003), the actual activities in manufacturing process planning depends on the type of manufacturing system as well as the nature of the products of manufacture. Most of the process planning methods, tools and techniques discussed in manufacturing engineering literature are more related to mature manufacturing system technologies such as; job shop systems (Zhang & Nee, 2001), cellular manufacturing systems (Morad & Zalzala, 1999) and flexible manufacturing systems (Saygin & Kilic, 1999). Little, however, is available to guide process planners for recent, new and innovative manufacturing styles. An example of such deficiencies is found in reconfigurable manufacturing systems (RMSs) that manufacture multiple parts in a given planning horizon. There is, therefore, a need to review conventional process planning methods, tools and techniques for application in new manufacturing styles. For multiple parts production, interface issues such as parts flow intensities, machine load limits, part loading constraints as well as manufacturing capability limits cannot be ignored during the process planning phase. This requirement makes it difficult to implement process plans of a linear nature. Moreover, the dynamics in the operational and structural complexity in multiple parts manufacturing lines (MPMLs) that allow reconfigurable flow of parts will render linear process plans infeasible with time. To circumvent this challenge, flexible process plans that can accommodate reconfigurable flow of multiple parts should be implemented. To generate such flexible process plans, a multidimensional approach that captures some of the issues mentioned above is described in this paper. In light of the discussion above, the manufacturing process planning problem for reconfigurable MPMLs can be described as follows. Given a set of flexible production machines for the manufacture of a multiple parts production scenario with multiple parts of total number, np, belonging to a number of part families, npf, the total number of feasible manufacturing process plans can be estimated mathematically as follows: Let each part, p, require Y activities for manufacture, where Y is multi-dimensional. Let the ith sub-activity have y(i) alternatives, and let each part require xi elements in dimension i of D dimensions, where D ϵ Y. Then the total number of feasible plans, z, can be approximated by the following expression equation(1) View the MathML sourcez=∏i=2Dx!(xi-x1)!∑i=1npf∑i=1npy(i) Turn MathJax on Although the expression in Eq. (1) is approximate, it serves to demonstrate that it is difficult to find an optimal solution by enumerating all the feasible solutions. Consequently, this manufacturing process planning problem is a hard optimization problem. Since manufacturing process planning is crucial in the operations of a reconfigurable MPML, it is important to develop effective optimization methods that are capable of recommending high-quality process planning solutions with a reasonable computational effort. Over the past years, hard optimization problems have been solved through algorithm design techniques that are robust in nature and non-math-knowledge dependent (Hromkovič, 2004). This includes heuristics such as simulated annealing (SA) and genetic algorithms (GAs). Genetic algorithms have found wide applications in many engineering fields including manufacturing process planning (Zhang and Nee, 2001 and Zhang et al., 1997). However, it is difficult to ensure the convergence of GAs since there is a possibility of premature convergence in the genetic search process. Moreover, it is time consuming to parameterize a genetic algorithm implementation. For successful practical applications, it is almost always necessary to devise techniques that enhance a genetic algorithm application in a specific problem domain. It has been observed that more recent successful applications of GAs in complex solution spaces have tended to focus more on modified genetic algorithms in a bid to implement GAs that are more competent than the simple genetic algorithm (Chen, 2006, Li and Wang, 2007 and Wang et al., 2007). This work explores the effectiveness of a modified genetic algorithm (MGA) method in obtaining optimal manufacturing process planning solutions for reconfigurable MPMLs. In the practical implementations of genetic algorithms, it has been observed that the effectiveness of an implemented genetic algorithm in solving a given problem depends on the chosen fitness function and the appropriateness of the genetic operators used (Chen, 2006). Therefore, in modifying the genetic algorithms, the emphasis in this work was to model the problem rigorously by adopting a decision-making perspective that focuses on generic issues such as capturing relevant production information, evaluating alternatives and selecting the best alternative. Unlike conventional approaches, this approach helps to reduce alternative choices in the decision making process towards optimization. The steps in developing the modified genetic algorithm method used in this work were as follows. Firstly, a comprehensive fitness function that captures and models a rigorous evaluation criterion was devised. Secondly, a cyclic crossover operator for an integer-based representation was implemented to ensure that recombination will not result in any violation of processing constraints. Thirdly, heuristics that support the progression of the genetic algorithm towards convergence were devised. Fourthly, a combination of a neighborhood search based mutation operator and a customized threshold operator were implemented to foil the tendency towards premature convergence in the genetic search process. In exploring the effectiveness of the proposed modified genetic algorithm, an application example of a multiple parts reconfigurable manufacturing line was used. The appropriateness of the MGA in generating manufacturing process plans for a MPML was compared with that of a simple genetic algorithm (SGA) and a simulated annealing (SA) algorithm. The reminder of the paper is organized as follows: In Section 2, the proposed modified genetic algorithm method is discussed. In Section 3, the representation of the solution and optimization operators for the MPMLs is presented. In Section 4, the proposed MGA is applied to an instance of a manufacturing process planning optimization problem and the corresponding computational and comparative results are presented. Finally, concluding remarks are given in Section 5.

In this paper, the issue of generating manufacturing process plans for reconfigurable multiple parts manufacturing lines has been discussed. Modeling the decision making process in an optimization framework was found to be helpful and feasible in implementing a genetic algorithm methodology. Capabilities of three (3) algorithms, one (1) simulated annealing (SA) and two (2) genetic algorithms; i.e. the simple genetic algorithm (SGA) and a modified genetic algorithm (MGA), in generating manufacturing process plans were tested. It was observed that all three (3) algorithms are able to find a near optimal manufacturing process planning solution. The solutions were obtained with satisfactory convergence in real time. Therefore, all three (3) algorithms can be used to generate feasible manufacturing process plans for reconfigurable multiple parts manufacturing. A computational study, based on a case illustration, demonstrated the practical use of implementing the modified genetic algorithm (MGA) method. In comparison to both simulated annealing (SA) and a simple genetic algorithm (SGA), it was clear that the modified genetic algorithm can obtain better solution quality for the same experimental settings. Therefore, significant improvements towards obtaining near optimal manufacturing process planning solution for a reconfigurable multiple parts manufacturing line can be achieved by implementing a modified genetic algorithm method.