用遗传算法解决设施布局问题外文文献翻译文档格式.docx

1、（Received 12 May 2006; accepted 23 July 2006）Abstract: The component layout problem requires efficient search of large, discontinuous spaces. The efficient layout planning of a production site is a fundamental task to any project undertaking. This paper describes a genetic algorithm （GA） to solve th

2、e problem of optimal facilities layout in manufacturing system design so that material-handling costs are minimized. The performance of the proposed heuristic is tested over problems selected from the literature. Computational results indicate that the proposed approach gives better results compared

3、 to many existing algorithms in this area.Keywords: facility layout; flexible manufacturing; stochastic programming1. INTRODUCTION Component layout plays an important role in the design and usability of many engineering products. The layout problem is also classified under the headings of packing, p

4、ackaging, configuration, container stuffing, pallet loading or spatial arrangement in the literature. The problem involves the placement of components in an available space such that a set of objectivescan be optimized while satisfying optional spatial of performance constraints.Current tools availa

5、ble in practice to designers to aid in the general mechanical layout process mostly remain at the stages of physical or electronic models with the assistance of manual adjustment and visual feedback.The difficulty in automating the mechanical and electromechanical layout processes stems from: （1） th

6、e modeling of the design objectives and constraints; （2） the constraints; （3） the identification of appropriate optimization search strategies.A number of design goals can be modeled as layout objectives. In addition, a set of constrains often has to be satisfied to ensure the applicability of the l

7、ayouts. Efficient calculations of objectives and constraints are necessary to solve the layout problems in reasonable time since the analysis of objectives and constraints can be computationally expensive and a large number of evaluations may be required to achieve convergence. The search space of t

8、he layout problem is non-linear and multimodel, making it vital to identify a suitable algorithm to navigate the space and find good quality solutions. The layout goals are usually formulated as objective functions. The objectives may reflect the cost, quality, performance and service requirements.

9、Various constraints may be necessary to specify spatial relationships between components. The specifications of components, objectives,constraints, and topological connections define a layout problem and an optimization search algorithm takes the problem formulation and identifies promising solution

10、 by evaluating design alternatives and evolving design states. Analysis of objectives and constraints vary from problemto problem. However, the optimization search technique and geometric representation and the resulting interference evaluation are problem independent and are,thus, the focus for a g

11、eneric layout tool1. The primary objective of the design problem is to minimize the costs associatedwith production and materials movement layout, semiconductor manufacturing andservice center layout. For US manufacturers,between 20% and 50% of total operating expenses are spent on material handling

12、 and an appropriate facilities design can reduce these costs by at least 10%-30% 2,3. Altering facility designs due to incorrect decisions, forecasts or assumptions usually involves considerable cost, time and disruption of activities. On the other hand,good design decisions can reap economic and op

13、erational benefits for a long time period. Therefore, the critical aspects are designs that translate readily into physical reality and designs that are robust to departures from assumptions. The project manager or planner usually performs the task of preparing the layout based on his/her own knowle

14、dge and expertise. Apparently, this could result in layouts that differ significantly from one person to another. To put this task into more perspective, researchers have introduced different approaches to systematically plan the layout of production sites 4,5 Facility layout planning can generally

15、be classified according to two main aspects: （1） method of facility assignment and （2） layout planning technique. Mathematical techniques usually involve the identification of one or more goals that the sought layout should strive to achieve. A widely used goal is the minimization of transportation

16、costs on site. These goals are commonly interpreted to what mathematicians term objective functions. This objective function is then optimized under problem-specific constraints toproduce the desired layout. Systems utilizing knowledge-based techniques, in contrast, provide rules that assist planner

17、s in layout planning rather than perform the process based purely on a specified optimization goal（s）. Usually the selected fitness function is the minimum total costs of handling of work pieces. In general, those costs are the sum of the transport costs （these are proportional to the intensity of t

18、he flow and distances） and other costs.An effective facility layout design reduces. manufacturing lead-time, and increases the throughput, hence increases overall productivity and efficiency of the plant. The major types of arrangements in manufacturing systems are the process, the flow line or sing

19、le line, the multi-line, the semi-circular and the loop layout. The selection of a specific layout defines the way in which parts move from one machine to another machine. The selection of the machine layout is affected by a number of factors, namely the number of machines, available space, similari

20、ty of operation sequences and the material handling system used. There are many types of material handling equipment that include automated guided vehicles, conveyer systems, robots, and others. The selection of the material handling equipment is important in the design of a modern manufacturing fac

21、ility6.The problem in machine layout design is to assign machines to locations within a given layout arrangement such that a given performance measure is optimized. The measure used here is the minimization of material handling cost. This problem belongs to the non-polynomial hard （NP-hard） class. T

22、he problem complexity increases exponentially with the number of possible machine locations.2. LAYOUT SPACE CHARACTERISTICS AND SOLUTION APPROACHES The problem of plant layout involves distributing different departments,equipment, and physical resources as best as possible in the facility, in order

23、to provide greater efficiency in the production of goods or services.The aims to be achieved when dealing with a problem of the above type can generally be described from two stances. On the one hand, many researchers describe the problem as one of optimizing product flow, from the raw material stag

24、e through to the final product. This is achieved by minimizing the total material handling costs. Solving the problem in this sense requires knowing distances between departments （usually taken from their centroids）, the number of trips between departments, andthe cost per unit. On the other hand, l

25、ayout can be considered as a design problem. Seen from this angle, solving the problem involves not only collecting the quantitative information mentioned above, but also qualitative information, for instance, how different departments are related from the point of view of adjacency. The layout spac

26、e is defined as the mathematical representation of the space of configurations mapped against the cost per configuration. Deterministic algorithms are unable to navigate such a space for globally near-optimal solutions, and stochastic algorithms are usually required for solutions of good quality. Th

27、e manner of arranging of working devices largely depends on the type of production. NP-hard problems are unsolvable in polynomial time 7（Kusiak 1990）. Accurate mathematical solutions do not exist for such problem. The complexity of such problems increases exponentiallywith the number of devices. For

28、 instance, a flexible manufacturing system （FMS） consisting of N machines will comprise a solution space with the size N. The problem is theoretically solvable also by testing all possibilities （i.e., random searching） but practical experience shows that in suchmanner of solving the capabilities of

29、either the human or the computer are fast exceeded.For arranging the devices in the FMS the number of possible solutions is equal to the number of permutations of N elements. When N is large, it is difficult, if not impossible, to produce the optimal solution within a reasonable time, even with supp

30、ort of a powerful computer. With todays computation power of modern computers it is possible to search for the optimum solution by examining the total space of solutions somewhere up to the dimensions of space 10. In case of problems of larger dimensions it is necessary to use sophisticated solving

31、methods which, during examining the solution space somehow limit themselves and utilize possible solutions already examined 8.3. LAYOUT SEARCH ALGORITHMS The layout problem can have different formulations, but it is usually abstracted as an optimization problem. An assignment of the coordinates and

32、orientations of components that minimizes the cost and satisfies certain placement requirements is sought. The problem can be viewed as a generalization of the quadratic assignment problem and therefore belongs to the class of NP-hard problems 9. Consequently it is highly unlikely that exact solution to the general layout problem can be obtained in an amount of time that is bounded by a polynomial in the size of the problem, resulting in