متا هیوریستیک از طبیعت برای مسئله طراحی طرح حلقه
|کد مقاله||سال انتشار||مقاله انگلیسی||ترجمه فارسی||تعداد کلمات|
|8044||2006||17 صفحه PDF||سفارش دهید||8831 کلمه|
Publisher : Elsevier - Science Direct (الزویر - ساینس دایرکت)
Journal : International Journal of Production Economics, Volume 101, Issue 2, June 2006, Pages 312–328
The loop-layout design problem (LLDP) arises when the machines in a flexible manufacturing system (FMS) are arranged in a closed ring-like network and the materials are transported around this network in only one direction. Evaluation of this layout is usually performed by estimating the traffic congestion, i.e., the number of cycles spent by each part in the network until its processing through the required machines is completed. The problem is known to be NP-hard and thus the right way to proceed is through the use of heuristics techniques. This paper addresses the unidirectional LLDP using a differential evolution algorithm (DEA); a modern meta-heuristic from the field of evolutionary computation. The performance of the DEA is measured through multiple characteristic experiments and compared to that of other known meta-heuristics such as genetic algorithms and simulated annealing.
Flexible manufacturing systems (FMS) play a crucial role in modern complex production lines. Such systems generally consist of a group of machines capable of performing a number of different operations, interconnected through an automated parts-transportation and handling mechanism all operating under the hierarchical control of a common computer system. An important factor in designing a FMS is the determination of an effective layout of the machines, i.e., an optimum arrangement of the machines in the shop floor so that to provide efficient operation (Kusiak and Heragu, 1987). The layout of the machines has a significant impact to the material-handling cost, the time of processing, the throughput of the production system, and therefore affects the overall productivity of the FMS. Good surveys on the general layout design problem for FMS can be found in Kusiak and Heragu (1987), Kusiak (1990), Hassan, 1994 and Hassan, 1995, Meller and Gau (1996), Ioannou and Minis (1998). The layout of machines in a FMS is typically determined by the type of material-handling device used such as material-handling robots, automated guided vehicles (AGVs), gantry robots, etc. In practice, the most commonly used types of machine layouts are the following (see Fig. 1): the linear single-row layout (Fig. 1(a)), the linear double-row (Fig. 1(b)), the cluster layout based on gantry robot (Fig. 1(c)), the semi-circular layout with a single robot, (Fig. 1(d)), and the closed-loop layout (Fig. 1(e)). In the first two layouts (Figs. 1(a)–(b)) an AGV transports parts between the machines moving in both directions in a straight line. The third machines layout (Fig. 1(c)) based on a gantry robot is used when the space in the shop floor is limited. In the fourth layout (Fig. 1(d)) a material-handling industrial robot carries parts between the machines traversing with its end-effector a semi-circular (pre-specified) trajectory. While, in the closed-loop layout, a conveyor moves in a closed-loop rail in only one direction transporting parts among the machines.This work addresses the unidirectional loop-layout design problem (LLDP), i.e., the problem of designing loop-layout-manufacturing systems of the form shown in Fig. 1(e). The problem has been proven to be NP-hard (Leung, 1992), meaning that there is no algorithm that can solve it in polynomial time, unless it is proved that P=NP (Garey and Johnson, 1979). In contrary to other layout configurations, there are at least two main factors that make loop layouts attractive for use (Afentakis, 1989): firstly, due to their relatively low initial costs since they need minimal material-handling links for connecting the machines, and secondly, due to their high flexibility in material-handling since all machines are reachable from all others. The objective with the LLDP is the determination of the ordering of the machines around the loop so that to optimize some performance criteria. The most usually used layout design criteria concern the minimization of material-handling costs. To that purpose, Afentakis (1989) proposed the minimization of a measure called traffic congestion. This measure is defined as the number of times a specific part traverses the loop before its processing is completed. In the literature two traffic congestion measures are usually used, called MIN–SUM, and MIN–MAX congestion, respectively. The objective with the former is to minimize the total congestion of all parts, while with the latter is to minimize the maximum congestion among parts of the same family. Afentakis (1989) proposed a graph theoretic model for solving the MIN–SUM LLDP. In this model a block interchange heuristic utilizes information from the dual of a linear programming formulation of a related problem. Leung (1992) addressed the MIN–MAX LLDP using a heuristic based on a graph-theoretic framework. This heuristic constructs a layout from a solution to the linear-programming relaxation of the problem. Millen et al. (1992), examined the impact of the number of the loading/unloading stations in automated manufacturing systems with unidirectional closed-loop machines layout. Kaku and Rachamadugu (1992) also addressed the layout design problem for FMS. In particular, the authors considered the problem of minimizing material-handling costs in loop-conveyor, and linear-track conveyor systems. Tansel and Bilen (1998) investigated the use of descent heuristics for the unidirectional LLDP. These heuristics were applied on permutations of machines with the form of two known small neighborhood moves: the pairwise interchange and the insertion interchange. Potts and Whitehead (2001) developed a three-phase integer programming model for combined scheduling and loop-layout design in FMS. The authors considered two main goals: maximizing the throughput (primary objective) and minimizing the movement of work among machines (secondary objective). Recently, genetic algorithms (GAs) have been used for the solution of the unidirectional LLDP (Cheng et al., 1996; Cheng and Gen, 1998). The authors proposed a hybrid approach of GAs and neighborhood search and investigated its performance on both the MIN–SUM and MIN–MAX congestion measures. Moreover, an increased research interest in the use of evolutionary algorithms (EAs) for the solution of various layout design problems in FMS is also observed in the recent literature. For instance, Plaquin and Pierreval (2000) applied an EA for the formation of manufacturing cells which takes into account specific constraints such as: the bounded size of cells, machines that must stay together, machines that must be separated, and machines around which the cells have to be formed. Uddin and Shanker (2002) addressed generalized grouping problems where each part has more than one process routes. The problem has been formulated as zero–one integer programming problem and solved by a GA with objective the minimization of intercell movements. Gómez et al. (2003) applied a GA to solve factory layout problems which involve the explicit consideration of passageways between sections along with the possibility of being these sections variable in width. Hicks (2004) developed a GA for minimizing material movement in a manufacturing cell with applications on practical problems related to the capital goods industry. Due to the combinatorial nature of LLDP, heuristics methods are normally the most promising research direction to deal with. The last two decades, a rapidly growing number of researchers developed meta-heuristics techniques for a wide range of complex combinatorial problems. Characteristic examples are the meta-heuristics inspired by the study of natural processes, such as the genetic and EAs (Gen and Cheng, 1997; Michalewicz, 1999; Dimopoulos and Zalzala, 2000) inspired by the analogy of population genetics, and Darwin's natural selection, and simulated annealing (Kirkpatrick et al., 1983; Tian et al., 1999) in which the natural analogy is the annealing process of metals. This paper introduces the differential evolution algorithm (DEA), another biological inspired meta-heuristic for the solution of the unidirectional LLDP. The performance of the DEA is examined over multiple characteristic experiments and compared to that of two other known meta-heuristics from the literature: the hybrid GA proposed by Cheng and Gen (1998), and the general simulated annealing algorithm (SAA) proposed by Tian et al. (1999) for combinatorial optimization of problems with permutation property. Differential evolution (DE) is a biologically inspired optimization method, which has been very recently applied with high success to solve various complex numerical optimization problems (Storn and Price, 1997; Price and Storn, 1997). Actually, it is a simple EA (Michalewicz, 1999) that mutates vectors (chromosomes) by adding weighted, random differentials to them. The main features of a DEA that make it attractive for use in the optimization of complex search problems are: • It is a stochastic search algorithm able to handle non-differentiable, non-linear and multi-modal cost functions. • It searches for the global optimal solution by manipulating a population of candidate solutions, which equivalently means, searching different areas of the problem's solution space simultaneously. Therefore, it is less likely to become trapped in a local optimum. • It does not need any derivative information and thus, it is very robust in solving optimization problems with non-smooth objective functions. • It manipulates pure floating-point numbers without any other extra processing, and therefore, utilizes computer resources efficiently. • It is easy to use and tune, since it requires the settings of very few control parameters. • It does not need to maintain populations of large sizes and thus it runs faster than other population-based techniques. The rest of this paper is organized as follows: Section 2 describes and formulates the LLDP. Section 3 gives a brief introduction to the basic DEA for optimization. Section 4 introduces a DEA for the solution of the LLDP, while Section 5 reports and discusses computation results of comparative experimental evaluations. Finally, Section 6 summarizes the contribution of the paper and states some directions for future work
نتیجه گیری انگلیسی
In this study, a DEA was proposed for the solution of the unidirectional loop layout design problem (LLDP). Two types of the basic LLDP were examined, named MIN–SUM and MIN–MAX, respectively. The objective with the former is the minimization of the total number of cycles spent by all parts in the loop network of the machines. While, the objective with the latter is the minimization of the maximum number of cycles spent by parts of the same family until the completion of their processing in the loop. Experimental comparisons over a large set of randomly generated test problems show that the proposed DEA is superior to previous existing meta-heuristics approaches, such as GAs and simulated annealing algorithms. Future work will investigate the application of the DEA to other types of layout design problems such as the single-row, and the multiple-row layout design problems. Furthermore, the investigation of the DEA in situations with uncertainty in the design phase of the machine layout problem is a second idea of future research. For instance, in real-world manufacturing there are cases where the value for the clearance between any pair of adjacent machines may be hardly provided with precision. Hybridizing the DEA with fuzzy systems is perhaps a promising area to start with and may result to a more robust optimization tool. Finally, another direction of future work is to incorporate the algorithm in a general optimization tool and integrate it with existing CAD or CIM software tools in order to be used in layout design and scheduling applications of a real-world facility floor.