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

Capabilities of enhanced simulated-annealing-based algorithms in solving process planning problems in reconfigurable manufacturing are investigated. The algorithms are enhanced by combining variants of the simulated annealing technique with other algorithm concepts such as (i) knowledge exploitation and (ii) parallelism. Four configurations of simulated annealing algorithms are devised and engaged to solve an instance of a process planning problem in reconfigurable manufacturing systems. These configurations include; a basic simulated annealing algorithm, a variant of the basic simulated annealing algorithm, a variant of the simulated annealing algorithm coupled with auxiliary knowledge and a variant of the simulated annealing algorithm implemented in a quasi-parallel architecture. Although differences in performances were observed, the implemented algorithms are capable of obtaining good solutions in reasonable time. Experimental results show that the performances of the variants of simulated annealing based algorithms are better in comparison to a basic simulated annealing algorithm. A computational analysis and comparison using ANOVA indicates that improvements towards a better optimal solution can be gained by implementing variants of the simulated annealing algorithm. In addition, little speed gains can be obtained by implementing variants of the simulated annealing algorithms that are coupled with other algorithmic concepts.

Due to the effects of globalization and the rapid changes in process system technologies, a number of new and innovative manufacturing styles have been introduced in the manufacturing arena. A prominent example is the advent of reconfigurable manufacturing systems (RMSs). The advantage of reconfigurable manufacturing lies in that manufacturers can address short windows of opportunities in dynamic environments as well as accommodate variations in production requirements [1]. Although implementation of RMSs, or their concepts and techniques, may result in a number of benefits, there are a number of challenges that are yet to be addressed in order to realize the full potential of a true reconfigurable manufacturing system [2]. For example, a reconfigurable manufacturing system thrives on logical reconfiguration of system components [2]. This is because logical reconfiguration of manufacturing system components can allow manufacturers to address short windows of opportunity as well as accommodate variations in production requirements. A challenging issue that can facilitate logical reconfiguration is process planning. That is, for cost-effective reconfigurable manufacturing, how can we generate process plans that can facilitate logical reconfiguration in a manufacturing system that is designed to be reconfigurable? In answering this question, the position taken in this paper is based on the fact that cost-effective logical reconfiguration heavily depends on the flexibility and reconfigurability inherent in a given manufacturing system. Flexibility and reconfigurability concepts are strategic decisions that must be integrated with production and operational decisions. Such integration facilitates cost-effective logical reconfiguration. One way of integrating flexibility and reconfigurability concepts in the operations of manufacturing systems is to capture the concepts in a process planning function. However, most of the current and conventional process planning methods and solutions do not take cognizance of both flexibility and reconfigurability issues. As a result, process plans obtained from such conventional methods cannot be implemented immediately in reconfigurable manufacturing activities. Therefore, new methods and techniques as well as new solutions that accommodate flexibility and reconfigurability must be developed to assist human process planners in reconfigurable manufacturing environments. Taking cognizance of flexibility and reconfigurability issues at the process planning stage is a challenging concept. This is because, on one hand flexibility decisions and considerations at the process planning phase usually focus on the operational, processing and routing issues for manufacturing parts [3]. On the other hand, reconfigurability decisions are concerned with how to plan manufacturing operations in order to allow for changes in capacity and functionality requirements in a bid to facilitate reconfiguration in manufacturing systems [4]. This makes process planning for reconfigurable manufacturing a challenging problem. In the case of reconfigurable manufacture of multiple parts in the same manufacturing system, process planning involves process identification and selection, process sequencing and multiple parts scheduling with respect to alternative part routings. Combining these issues in a single optimization framework leads to a hard optimization problem that is combinatoric in nature. Over the years, simulated annealing algorithms have been utilized successfully to address such type of problems. Simulated annealing (SA) has been found useful in providing feasible solutions to a variety of practical optimization problems [5]. This is evidenced by successful applications of SA algorithms to a wide variety of problems in various fields and domains. In the manufacturing arena, successful applications of simulated annealing cut across a range of problems that include: the travel salesmen problem [6], the quadratic assignment problem [7], the multidimensional assignment problem as well as scheduling problems of a wide variety [8], [9], [10], [11] and [12]. The nature of the problems cited above cuts across the spectrum of hard, combinatorial, N–P hard and N–P complete problems. This variety of successful applications shows that simulated annealing is a promising candidate for traversing rugged landscapes in search for a near optimal solution. The goal of a simulated annealing algorithm is to find the state of lowest cost (lowest energy or lowest objective function value) from a discrete space of possible configurations. For a specific problem to be solved, a cost function must be defined which maps each state to a real number denoting its cost. For many problems, the number of possible states grows exponentially with the size of the input. Optimization then becomes the process of searching for the state of lowest cost (lowest energy) in a multidimensional state space. With a large number of possible states to consider, most conventional methods fail to reach a solution in real time. However, the simulated annealing algorithm employs search strategies that can uncover the lowest cost solution in a rugged landscape. This can be achieved through simulated annealing procedures that mimic the efficient simulation of a collection of atoms in equilibrium at a given temperature. Unlike other algorithms, the simulated annealing procedures also allow moves to states that increase the cost function. At each temperature, the simulation proceeds long enough for the system to reach a steady state. The sequence of temperatures and the method to reach equilibrium at each temperature is known as an annealing schedule. Although a number of weaknesses of the basic simulated annealing technique have been documented in the public literature, recent years have witnessed success in implementing a number of variants of the basic simulated annealing algorithm. Although some of the variants are unique to specific problem domains, it has been generally observed that variants can provide improved feasible solutions in comparison to the basic simulated annealing algorithm [13]. It is clear from this observation that experiments with variants of the simulated annealing algorithm can reveal new implementations of simulated annealing that can be used to obtain more improved solutions to hard optimization problems. Moreover, it has been suggested that coupling the simulated annealing technique with other algorithm concepts may result in an algorithm that is more effective than the basic simulated annealing algorithm [14]. In such a case, the broader contributions of this paper would be to provide evidence for or against the allegedly improved performance of simulated annealing when coupled with other algorithmic concepts. Against this background, the new concept explored in this paper is to devise variants of the simulated annealing technique and combine the variants with other algorithm concepts such as (i) knowledge exploitation and (ii) parallelism. Therefore, the main objective of this paper is to investigate and test the capabilities of enhanced simulated annealing based algorithms in providing a solution method for the challenging problem of process planning for reconfigurable manufacturing. From the previous discussions, it can be observed that simulated annealing is a general optimization algorithm for locating a good approximation to the global optimum of a given objective function. It is a generic probabilistic metaheuristic that employs properties of statistical mechanics in locating a global optimum. Over the years, many versions of SA algorithm have been proposed in the literature [6], [15], [16] and [17]. The theory of the simulated annealing algorithm implemented in this paper is based on two concepts; (a) the probabilistic acceptance of moves in the search landscape and (b) a fast cooling schedule. The algorithm propagation can be described as follows. At each iteration during the search process, a random neighbor is selected (this activity is called a move). Such a move is realized based on two issues, either (i) the move is an improvement towards the global optimum or (ii) the move is performed according to an exponential time-decreasing probability. If the objective function (sometimes called the cost function), ΔF (y ), that results after the move is greater than 0 (i.e. ΔF (y ) > 0, then the move is accepted with a probability of expo−ΔF (y )/T , where T is a time-decreasing global parameter, generally called temperature in simulated annealing literature. This means that there will be a number of temperature levels during the search process. At each temperature level a number of neighbors, of the current solution exist in the search space. The algorithm then samples the neighborhood space in a bid to create a new solution. The new solution is accepted according to a probability distribution defined by expo−ΔF (y )/T . The value of the global parameter, T , is modified using the cooling schedule. The search process starts at an initial temperature value, T 0, and ends at a final temperature value, TF . Theoretically, it has been shown that simulated annealing can converge asymptotically to a global optima of the objective function [18] and [19]. For problems of a combinatoric nature like the one considered in this paper, it has been shown that simulated annealing converges if the cooling schedule is set according to the relationship Tn∝1/(logn)Tn∝1/(logn) [18]. The remainder of this paper is organized as follows: Section 2 describes the manufacturing process planning optimization framework while Section 3 discusses the formulation and configurations of the enhanced simulated annealing based algorithms. Section 4 discusses applications of enhanced simulated annealing algorithms. Finally concluding remarks are given in Section 5.

In this paper, a multiple parts process planning problem for reconfigurable manufacturing activities has been described. A solution method based on enhanced simulated annealing algorithms has been discussed. Since simulated annealing is a stochastic approach, the advantage of using this solution method lies in that it can provide alternative processing routes for multiple parts flowing in a manufacturing system. Such provision allows manufacturers to exploit the full potentials of flexibility and reconfigurability in manufacturing systems. Consequently, manufacturers can address short windows of opportunity, when it is required; as well alleviate problems associated with variations in production requirements. Obtained results show that although there are variances in the various performance metrics considered, simulated annealing based algorithms are capable of obtaining good solutions to complex process planning problems in reasonable time. The broader contribution of this paper was based on a computational analysis that incorporates ANNOVA tests. In this regard, the computational analysis indicated that, in comparison to the basic simulated annealing, improvements towards better optimal solutions can be gained by implementing simulated annealing variants. However, when the performance of a simple simulated annealing variant (i.e. VSA) is compared to simulated annealing variants that are coupled with other algorithmic concepts such as knowledge exploitation and quasi-parallelism (i.e. SAAK and SAQPA) little is gained in terms of the mean times to solutions. On the other hand, the simple variant, VSA, seems to outperform the other variants that are coupled with other algorithm concepts in terms of the mean objective function values obtained. In addition, the coefficients of variation suggest that the simple variant, VSA, is comparatively the most robust algorithm. Evaluation of the best process plans obtained from each of the implemented algorithms indicates that the recommended process plans have potential routing and processing flexibility that can be used for logically reconfiguring the manufacturing system when the need arises. Therefore, the findings in this paper illustrate the usefulness of simulated annealing based solution methods for handling complex manufacturing process planning optimization problems such as those found in reconfigurable manufacturing systems. The results indicate that improved performance can be gained by implementing variants of the basic simulated annealing algorithm. In addition, coupling the basic simulated annealing technique with other algorithmic concepts such as knowledge exploitation and parallelism may also result in the creation of algorithms that are more effective than the basic simulated annealing algorithm.