بازپخت شبیه سازی شده با دانش مکمل و کمکی برای بهینه سازی برنامه ریزی عملیات در تولید پیکر بندی مجدد

In this paper, three simulated annealing based algorithms that exploit auxiliary knowledge in different ways are devised and employed to handle a manufacturing process planning problem for reconfigurable manufacturing. These algorithms are configured based on a generic combination of the simulated annealing technique with; (a) heuristic knowledge, and (b) metaknowledge. Capabilities of the implemented algorithms are tested and their performances compared against a basic simulated annealing algorithm. Computational and optimization performances of the implemented algorithms are investigated and analyzed for two problem sizes. Each problem size consists of five different forms of a manufacturing process planning problem. The five forms are differentiated by five alternative objective functions. Experimental results show that the implemented simulated annealing algorithms are able to converge to good solutions in reasonable time. A computational analysis indicates that significant improvements towards a better optimal solution can be gained by implementing simulated annealing based algorithms that are supported by auxiliary knowledge.

In the past years, simulated annealing (SA) has found many applications in solving difficult optimization problems. For example, SA has been implemented successfully in: travel salesmen problem [1] and [2]; the quadratic assignment problem [3] and [4]; multidimensional assignment problems [5] and [6]; scheduling problems of a wide variety and manufacturing process planning problems [7] and [8]. These examples show that the nature of the problems that have been solved through applications of SA is wide and cuts across the spectrum of combinatorial, N-P Hard and N-P Complete problems. Therefore, simulated annealing is a potential candidate for solving difficult optimization problem. Simulated annealing (SA) is usually implemented as a trajectory-based search technique [9]. It was first introduced by Kirkpatrick et al. [10]. In most applications, simulated annealing has been utilized to locate a good approximation to an optimal solution for a given function in a large search space. Although a number of weaknesses of simulated annealing have been observed, variants of the standard simulated annealing algorithm have been developed to overcome the documented weaknesses [11]. In addition, current research has shown that search techniques that systematically exploit knowledge about the problem being solved are more effective than their corresponding counterparts [12]. Therefore, the contribution of this paper is in investigating the effects, on the quality of computed solutions, of exploiting auxiliary knowledge in simulated annealing implementations. The effects will be observed for implementations in which SA with auxiliary knowledge will be tasked to search for an optimal solution of a complex manufacturing process planning (MPP) problem in reconfigurable manufacturing. In the public literature, most implementations of simulated annealing are based on the pseudocode template of the simulated annealing algorithm described in Algorithm 1[13] and [14]. Algorithm 1 propagates iteratively keeping a tentative solution, Sα, at any time during implementation. At each iteration, a new solution, Sn, is generated from the previous one, Sα. This new solution will either replace the old one or not. The decision to replace or not to replace is based on an acceptance criterion. The acceptance criterion is described in Algorithm 2. The logic in the above algorithm lies in that if the new solution is better than the old one (tentative solution), then the new solution will replace the tentative solution. If it is worse, it replaces it with probability that depends on the difference between their quality values and a control parameter, T, usually named as temperature in the public literature [7]. This acceptance criterion provides a way for the algorithm to elude local optima. The mathematical expression for the probability, P, used in the acceptance criterion can be represented by the expression: equation(1) P=e−((En−Eα)/T)P=e−((En−Eα)/T) Turn MathJax on Therefore, with more iterations, the value of the control parameter, T, is changed according to a predefined schedule, thus enforcing the SA algorithm towards accepting only better solutions. Algorithm 1. Steps Pseudocode 1. T←0; 2. Initialize (T, Sα) 3. Evaluate (Sα) 4. While not endCondition (T, Sα) DO 5. While not coolingCondition (T) DO 6. Sn←chooseNeighbor (Sα) 7. Evaluate (Sn) 8. IF accept (Sα, Sn, T) THEN 9. Sα←Sn 10. END IF 11. T←T+1 12. END While 13. coolDown (T) 14. END While Table options In operating the line depicted in Fig. 1, it is always necessary to assess the routing of parts and sequencing of processing machines in terms of manufacturing system performance-based criteria. Since implementation of reconfigurable manufacturing system concepts and techniques is relatively expensive, essential manufacturing system performance criteria is often based on operating costs. Other researchers have also suggested that process planning for reconfigurable manufacturing should be based on a cost criterion [17]. The process planning optimization problem, therefore, precipitates to determining an optimal manufacturing process plan that minimizes operating costs. Solving such a problem requires a comprehensive analysis of interrelated decision making activities that aim at selecting an optimal manufacturing process plan since a large number of possible combinations of processing machines/modules and processing sequences exist. Hence, an optimization perspective in the solution method is inevitable. An illustrative example of the manufacturing process planning in RMSs is described in the next section.

In this paper the capabilities of simulated annealing algorithms that exploit auxiliary knowledge have been investigated. The relative performances of four algorithms were tested when tasked to solve a manufacturing process planning optimization problem in reconfigurable manufacturing systems that manufacture multiple parts. In order to pursue the concept of knowledge exploitation and its effects and influence on computational performance, auxiliary knowledge was incorporated in two ways: (i) heuristic process planning knowledge, which was deployed through problem specific heuristics that guide the search process and (ii) process planning metaknowledge, which was interfaced and made available for use by the simulated annealing algorithm through subroutines. In addition to, seeding the algorithm, deploying heuristic process planning knowledge and interfacing the algorithms with metaknowledge, a suitable neighborhood topology that helped in propagating the simulated annealing algorithm, was devised and implemented successfully. The findings of this investigation can be summarized as follows. Simulation results show that all implemented simulated annealing algorithms cases are able to converge to good solutions in reasonable time. However, auxiliary knowledge was shown to produce significant improvements in the quality of the computed solutions. In addition, the way in which auxiliary knowledge is implemented has an influence on the quality of the computed solution as well as the time required to reach an optimal solution. Although differences in performances were noted for simulated annealing algorithms that exploit knowledge in different ways, the results indicate that simulated annealing algorithms that implement auxiliary knowledge are more effective when compared to a basic simulated annealing algorithm. The effectiveness of the algorithms was judged based on the quality of the computed solutions. It was further noted that the simulated annealing algorithm that implements heuristic knowledge only was found to be the most efficient method time wise. Therefore, it can be concluded that significant improvements towards better optimal solution can be gained by implementing simulated annealing with auxiliary knowledge. Moreover, it was observed that relative robustness in solving both problem sizes of twenty and thirty parts increases when simulated annealing with auxiliary knowledge is implemented. In interpreting the results of the experiments carried out in this work, it is acknowledged that auxiliary knowledge can be implemented in a variety of ways. Further work will involve investigating other forms of incorporating auxiliary knowledge other than those discussed in this paper. This includes devising ‘hyper’ heuristics based on the simulated annealing algorithm. Another consideration involves comparing the computational performance of the simulated annealing algorithms discussed in this paper with other metaheuristics based on say genetic algorithms. An interesting option for further work would be to design, develop and test the performance of multiobjective algorithm when tasked to solve the process planning optimization problem in reconfigurable manufacturing.