Solving facility layout problems with strict geometric constraints using a two-phase genetic algorithm

Abstract

This article puts forward a two-phase genetic algorithm that is able to solve facility layout problems strictly respecting the geometric constraints imposed on activities. In the first phase the algorithm attempts to locate an optimum slicing tree to group the activities appropriately. In the second phase the layout is obtained from this tree. In order to assess the slicing trees in the first phase we propose an evaluation function able to predict if, by making the appropriate cuts, the tree structure is able to generate layouts that satisfy the geometric restrictions imposed on the facilities to be arranged, and to minimize the cost of transporting materials between the production activities. It also permits the determination of the most suitable aspect ratio of the layout zone in order to minimize non-compliance with the geometric restrictions. The algorithm and the method of calculating the indicator proposed in the evaluation function are described, and the results obtained in the experiments carried out are also given.

Keywords:

• slicing tree
• layout problem
• genetic algorithm

Acknowledgments

We would like to thank the R&D+i Linguistic Assistance Office at the Universidad Politécnica de Valencia for their help in translating this paper.

Notes

† In this paper we will use the height-width ratio, which can be defined as the height of the facility or the plant divided by its width, but in Figure 1, the geometry of a facility is measured by means of the angle (in radians) formed by the diagonal of its rectangular area and the horizontal (Diego-Mas et al. 2006).

† It is common practice to consider only two types of cuts to be made in each node (vertical or horizontal) (Tam and Chan 1998). Here, however, two possible vertical cuts and two horizontal ones are distinguished, depending on which side of the cut the activities hanging from the node are located on (Tam 1992a, 1992b).

† In Tate and Smith (1995) the aspect ratio is defined as the width divided by height of the activity. Since the activities are freely oriented, height/width can be used in the same way.

†The Euclidean metric was used in this calculation.

‡The estimation made is bound to be inaccurate. However, after obtaining this, it could be used to determine the material transport cost of the partial layouts generating the solution, being very similar to the ones given by the authors.

† One should remember that the use of the height-width ratio as a measurement of the form of the areas of the activities causes the non-existence of linearity between the difference in ratios and the difference of forms. Hence, a difference in ratios of 0.1 when these take values close to the unit entails figures that are more similar to each other than if these ratios have values farther from the unit.