Source: http://www.journal.au.edu/ijcim/jan00

GENETIC ALGORITHMS OPTIMIZATION FOR
THE MACHINE LAYOUT PROBLEM

– RUSSIAN

– ENGLISH

Abstract

        This paper gives descriptions on various methods of solving the layout problem and describes a novel method based on genetic algorithms (GA) to solve the machine layout problem. Developing a machine layout is an important step in designing manufacturing facilities due to the impact of the layout to material handling cost and time, and consequently, affects the overall productivity of the shop floor. Poor layout would result in having more parts spending longer time moving from one machine to another, and thus results in increasing material handling costs. In contrast to the block layout, the objective of the machine layout problem is to find the appropriate placement of machines in a cell. The GA-based method developed to solve this uses the objective of minimizing the movements of parts being processed in the cell.

        

Layout of Manufacturing Cells

        One of the most important factors to consider in designing the manufacturing facilities is finding an effective layout. A general definition of plant layout problem is to find the best arrangement of physical facilities to provide an efficient operation. Layout affects the cost of material handling, time and throughput, and hence affects the overall productivity and efficiency of the plant (Hassan (1995)).

        The layout of machines normally depends on the type of manufacturing industry. In a case where product volumes are high and variety of products are low, the manufacturing process is known as a flow shop process and the layout is normally based on products. Hence, the layout is called layout by product. On the other extreme, a manufacturing plant may have a high variety of products with low production volume, where the process is known as job shop and the layout known as job shop layout, layout by function, functional layout or layout by process (Dilworth (1996)). Group technology (GT) or cellular manufacturing is normally applied to manufacturing systems that are in between these extremes with the layout known as the cellular layout. Figure 1 shows the type of layouts for different types of manufacturing systems.

        Figure 1: Relationships of product variety and volume with different manufacturing

        Another type of product layout is the fixed product layout. In contrast to other types of layout, in the fixed layout the production equipment moves toward the product and not otherwise. This type of layout is common when the products are large in size such as the making of ships or aeroplanes.

        In cellular manufacturing, the cell layout problem, or sometimes known as the machine layout problem, is basically concerned with finding the best arrangement of machines in each cell. The three major types of arrangement in the GT cells are the single-row, multi-rows or loop layout, as shown in Figure 2. The single-row layout, or sometimes known as the GT flow line layout, is used when the parts assigned to the group follow the same machine sequence. The multi-row layout, or the GT cell layout, permits parts to move from any machine to any other machine. The flow of parts may not be unidirectional in this layout. The GT centre layout, on the other hand, is based on a functional arrangement of the machines and is suitable when the product-mix changes frequently.

        Figure 2: Types of layout in the GT cell

        The development of the GT layout basically involves 3 steps (Jajodia et al (1992)):

        
• formation of part-family.
        
• arrangement of machines within cells or the machine layout problem.
        
• arrangement of cells with respect to each other.

        Each of these steps is a combinatorial problem and many heuristics have been proposed over the years to solve them.

        

These steps are normally performed sequentially.

        The primary data required to form the GT layout is as follows:

        
1. Machine/part matrix or the incidence matrix. This matrix is used for the cell formation problem.
2. The sequence of operations of the parts. This data is sometimes used in the cell-formation problem, i.e. finding the grouping of machines to put in cells, and for the construction of the cell layout. If the operations can be done in any arbitrary order, such as in the open shop problem, the best sequence found using a certain algorithm is usually found first before proceeding to find the best layout for the sequence.
3. The sequence data is used to construct a from-to chart, which represents material flow between machines in the construction cell layout.
4. The areas of the machine which are required, to estimate the size of the cell and the distance between them.

        Hassan and Albin (1994) give an extensive study on the type of data required in the machine layout problem. The machine layout data is considered in a hierarchy, (shown in Figure 3) depending on how detailed the layout is designed. When the layout required is only to find the relative arrangement of machines, data representing machine number and their flow relationships are sufficient, which is up to Level II in the hierarchy. However, if a detailed layout is needed, more data is required. In finding data at Level III, some difficulties may arise especially in new manufacturing facilities where the data is not yet available. When the layout is developed for modern and automated facilities, the required data cannot be obtained from historical data or from similar facilities since they may not exist.

        Another difficulty in preparing machine layout data is the requirement of quantifying some qualitative factors. Converting these factors are done subjectively and could cause inaccuracy. Data required in the relationship chart, which describes the desirability of adjacencies between machines, are initially qualitative but needs to be assigned numerical values. There is no universal agreement on the numerical values which should be assigned to the elements of the relationship chart.

        

Types of Layout

        Machines can be arranged in a single row, multi-row, or loop layout depending on the sequence of operations. The single row layout may assume different configuration such as semi-circular, linear or U-shaped. The machines in the single row layout are arranged as close as possible to the sequence of operations of all the parts processed in the layout in order to minimise travelling time. In this layout, the sequence of operations are normally similar from one part to another and the material handling equipment used are normally conveyors. The multi-row layout is usually linear and the movements of parts can be between any machines in different rows as well as in the same row, which is suitable for FMS. In the loop layout, machines are arranged in an oval path with unidirectional movement.

Figure 3: Hierarchy of machine layout data

        

Factors Affecting the Layout

        The type of material handling equipment plays an important role in the design and operation of a modern manufacturing facility. It determines the travel time and affects the throughput and the flexibility of the FMS. Ideally, developing the machine layout and selecting the handling equipment should be considered simultaneously. However, the combinatorial nature of each problem prohibits the joint consideration (Hassan (1994)). Normally, this is solved sequentially, where the solution of the first problem is used as an input to the second problem. There are many types of material handling equipments, amongst which are AGVs (Automated Guided Vehicles), conveyor systems and robots. A conveyor system is more suited for flow line type processes where every part goes from one machine in a single line, while robots are normally used in a job-shop processes or FMS.

        There are two types of movements associated with the flow-line layout which affects the flow of operations, namely, backtracking and bypassing. Backtracking is the movement of a part from one machine to another that precedes it in the sequence of machines in flow-line arrangement. Backtracking occurs when the parts being processed have different sequence of operations in the flow-line type of arrangement. On the other hand, bypassing occurs when a part skips some machines while it is moving towards the end of a flow line arrangement. Similar to backtracking, bypassing occurs due to the difference in the sequence of operations of the parts. Ideally, both of these movements should be minimized as much as possible since they affect the movement cost and productivity.

        

Approaches to finding the best layout - Conventional Approaches

        The conventional technique to find the best layout possible involves the use of diagrams and graphs. A detailed analysis needs to be done on the routing of parts, volume moved, distance, frequency of move, rate of which the part travel and the cost of the move (Apple (1977)). Some common techniques used are assembly charts which gives the graphical representation of flow of parts, operation process charts, multi-product process charts, string diagrams, and from/to charts, etc.

        

Quantitative approach

        The quantitative approaches on the other hand, are primarily concerned with optimising the location of equipment with the movement of material, and include techniques from the operations research in addition to mathematical techniques. The measure of effectiveness used in the quantitative approach is the distance travelled by the parts.

        Mathematical Technique

        Among the techniques used to solve the layout problems are linear programming, assignment problem, transportation programming, transshipment programming, and integer programming, etc. Koopmans and Beckman (1957) developed a quadratic assignment problem (QAP) model to solve for the multi-row layout. In the model, the objective is to minimise the materials handling cost by maximising the profit obtained by deducting the profit of using a certain layout to the cost of transportation. The QAP is proven to be an NP-complete problem by Garey and Johnson (1979). The equation used is given as follows:

        Maximise

        where,
        aij - net revenue from operating machine i at location j
        cjl - cost of transporting a unit of material from location j to l
        fik - flow of material from machine i to k
        n - total number of locations
        xij = 1, if machine i is at location j, = 0 otherwise

        Other Techniques

        More recent approaches to solve the layout problem include simulated annealing, and genetic algorithms. Suresh et. al. (1995) used a genetic approach to solve the facility layout problem, where the objective is to minimize the cost of interaction between various departments. Unlike the machine layout problem, the facility layout problem is more involved in finding the best layout for cells/departments and not finding the arrangement of machines. Hassan (1994) has given a good description of the differences between machine layout and facility layout or block layout.

        Kouvelis et. al. (1995) use the design objective of minimizing the total backtracking distance for the material handling device in a row layout problem of an automated manufacturing system, where the machines are arranged in a straight line.

        Gupta et. al. (1996) used a GA to find the part-family as well as the layout between cells. In his formulation, he limited the arrangement of cell as either linear single row or linear double row. The developed algorithm is more towards the cells system layout, or the layout of production floor, rather than the cell layout, or the machine layout. The actual layout of machines within cells was not considered. Banerjee and Zhou (1995) formulated the facilities design optimisation problem for a single-loop layout using genetic algorithms. The developed algorithm is for the cell systems layout and hence does not consider the layout of machines within cell.

        

GA-based method for machine layout

        A genetic algorithms (GA) is an adaptive search technique which imitates the process of biological evolution (Goldberg (1989)). A method using genetic algorithms has been developed to solve the machine layout problem and the programming is done using the Matlab software with GA toolbox (Chipperfield et. al. (1994)). Two types of layout are considered, the single-row layout usually associated with the flow-line problems, where parts have to undergo similar sequence of processes, and the multi-row layout, which is more appropriate to the job-shop problems where the parts can undergo processes in any sequence. Since the cost associated with the layout is proportional to the distance travelled by the parts, the algorithms developed for the multi-row layout has the objective of minimizing the distance travelled by the parts. In the formulations, cost incurred using the material handling equipment is assumed to be constant. Hence, the resultant layout will actually minimize the cost of travelling the distance. The values of the genetic parameters used are given in Table 1, with the initial population generated at random. The stochastic universal sampling is used to assign the expected number of offspring to be produced in the next generation for each individuals. A generation gap (GGAP) of 0.1 is employed, which means that 10 percent of the best individuals are carried forward to the next generation.

        

The single-row layout

        The single-row layout is described as a layout which has machines in only one side of the material handling equipment. The type of material handling equipment used in this type of layout is normally a conveyor system or an AGV. In the manufacturing process, however, there are occasions where not all parts will go through all machines for processing in the same sequence. Some parts may need to backtrack the conveyor to undergo a certain process. The handling of such parts is normally done using AGVs or an operator, assuming the conveyor is unidirectional. For this type of problem, the appropriate objective to be used is to minimize backtracking. The formula is given as follows:

        where,
        wij = number of parts processed in machine i per unit of time that must be routed to j.
        xij = back track distance from machine j to i.
        The wij matrix is actually the from/to chart which shows the number of batches that goes from one machine from another.

        This matrix is obtained using the information found in the sequence of process for all the parts. Should the sequence be changed, a different from/to matrix will be formed.

        

Chromosome representation and genetic operations

        The chromosome representation is based on permutation of integers representing the sequence of machines in the layout. For example, an individual {3 2 1 4} would represent a layout of machine 3 followed by machines 2, 1 and 4, respectively. The xij matrix can be calculated based on each individual. This matrix shows the individual backtracking distance depending on the layout. Nonetheless, parts that bypass certain operation are not included since the cost of bypassing a certain workstation is minimal in a conveyor system as compared to the cost of backtracking. Hence, the total backtracking distance of all parts gives the objective value of the individual. The genetic operators used in this formulation are order-based operators and position-based operators.

        

The multi-row layout

        The multi-row layout is usually associated with job-shop and FMS environments where the parts can be processed in any sequence. Normally, the sequence of processing is optimized using various scheduling methods. The layout is based on the sequence found by minimizing the distance travelled. Unlike the single-row layout, the material handling equipment used for the multi-row layout are AGVs or human operators to handle fork lifts or other equipment.

        The chromosome representation is based on the permutation of integer which represent the machine numbers, where the location of the gene represents the location of the machines. For example : chromosome {5 2 1 3 4} would represent a layout shown in Figure 4.

        Рисунок 4: Layout for chromosome {5 2 1 3 4}

        The distances between locations, as well as the possible locations of machines, are known in advance, hence the objective is to find the best position of machines that would minimize the total distance travelled by parts. Another important data required for the layout problem is the frequency of movement between machines, which indicates the number of times a part has to move from one location to another.

        

The Objective Function

        The criterion most often used in the layout problem is to minimize the travel cost of the parts, with the cost related to the distance travelled. Consequently, the objective is formulated as minimising the total travelling distance of parts. The objective function is given as follows:

        where,  fij = frequency/volume of movement,
        ij = cost to move one unit load per one distance unit between two machines,
        dij = distance between machine i and j.

        Assuming the cost cij remain constant, the objective would be reduced to minimizing the total distance travelled for the parts. In certain company, which foresee a possible future expansion of the shopfloor, there are ample space available, creating a situation where the number of possible machine locations exceed the number of machines. In this situation, dummy machine numbers are used in the representation. For example, in a case of seven locations and 5 machines, we assign machine 6 and 7 to be dummy machines and machines 1-5 as real machines. The algorithm will find the locations which minimise the total distance travelled by parts, leaving empty spaces for locations assigned to the dummy machines. These empty spaces can be used for other uses such as storage area in the shop floor. Should the company decide to buy extra machines these spaces will then be used to put the new machines.

        

Conclusions

        This paper describes in detailed issues concerning the machine layout problem associated with manufacturing cells. A novel approach using genetic algorithms is proposed to handle the problem. Two algorithms are developed to solve the single row and multi-row layouts in a cellular manufacturing cell to find the relative locations of machines in a cell. The reported results show that the genetic-based approaches are able to produce good solutions in reasonably short computational time compared to using enumerative approaches. The advantage of this algorithm is that the machine layout can be determined using a minimal amount of data, offering an advantage in areas where the cost of changing from one layout to another is not known due to unavailability of data on the cost incurred per distance of movement. However, in the multi-row layout, if the material handling equipment used are different from one location to another, and thus the unit cost incurred would vary, this algorithm could still be applied by incorporating the unit cost, cij, in the objective function.