Discrete OptimizationCombining evolutionary computation and dynamic programming for solving a dynamic facility layout problem☆
Introduction
One task in factory planning is to determine good locations for a given set of departments on some workshop floor––frequently called facility layout problem (FLP). A first objective is to minimize material handling costs. Yet, other criteria like manpower requirements, work-in-process inventory, flow of information, etc. may play an important role, too. In all cases, certain departments need to be physically close to each other. Often one cannot satisfy all these needs by placing such departments next to each other, one has to decide which adjacencies are the most favorable.
There are industrial production processes which require rigid installation of heavy equipment. The layout of such a plant has to ensure good system performance for a wide variety of demand scenarios. In such case, one typically has to solve a static optimization problem, which yields the best performance on average. Yet, many products can be processed on flexible manufacturing systems which allow to respond efficiently to changes in production demands by changing the layout. In this case the layout designer is faced with the problem of considering carefully the costs of rearranging a layout and the savings by an improved performance. Hence the dynamic FLP (DFLP) for a sequence of T time periods with different adjacency requirements consists in finding for each period a layout such that the resulting cost function is minimized. This cost function combines the costs for the rearrangement necessary between layouts of consecutive periods and costs for each period which depend on how the layout satisfies the adjacency requirements of this period. A first algorithmic treatment of this problem dates back to the work of Rosenblatt (1986) who assumed departments of equal size and formulated the problem as a dynamic program.
In this paper we present an approach which can handle unequal sizes of departments, which in addition may change from one period to the next. Our algorithm combines genetic search and dynamic programming. We will describe a representation of layouts which we can use as genetic code. For finding a sequence of layouts that gives us a good solution to some DFLP with T periods we create for each period a population, where each individual in the population represents a specific layout. Each population is evolved by a genetic algorithm (GA). For this purpose the fitness of each individual needs to be known. Yet, the benefit of preferring a certain layout for a given period cannot be evaluated without considering the preceding and the subsequent period. Therefore, we search for each individual a sequence of layouts which contains this individual and minimizes the cost function over all possible sequences that can be formed from the given populations. This is done by a dynamic program (DP).
The remainder of this paper is organized as follows. In Section 2 we introduce a mathematical model for the DFLP for unequally sized departments. Section 3 presents our algorithm. We start with a literature review on different methods to solve the DFLP. Finally, we discuss our numerical experiments and compare them with other works in Section 4.
Section snippets
The model
As in Yang and Peters (1998) we model workshop floor area and departments by rectangles. The shape of a rectangle is determined by its side lengths, which we allow to change from period to period. This enables us to model expansion, shrinking or replacement by a new department. The position is described by the coordinates of the center point and the orientation. There are two possible orientations––the long side is parallel to the x-axis or to the y-axis.
The cost of a layout for a given period
The algorithm
Let us consider a DFLP with a finite number of locations for placing the departments. In this case the possible layouts for each period can be enumerated. The sets are finite. Rosenblatt (1986) first solved this problem by dynamic programming which is based on the following recursive relationship:Since , the number of possible layouts, increases rapidly with the number N of departments, , the size of problems which can be
Problem Setting
In order to compare our algorithm to previous results let us consider the two examples P6 and P12 from Yang and Peters (1998) (just our numbering of the departments will start from 0 instead of 1). We refer to Yang and Peters (1998) for the dimensions, the initial layout (little mistake in table A.1. department 3 has to be in vertical position) and the weight matrix. The weights for moving where all set to 100. As floor area we chose a 30 × 30 and 50 × 50 workshop floor, respectively.
As the mixed
Acknowledgements
We would like to thank the referees for their valuable suggestions.
References (19)
- et al.
Dynamic layout algorithms: A state-of-the-art survey
Omega
(1998) - et al.
Genetic search and the dynamic layout problem
Computers and Operations Research
(2000) - et al.
Solutions for the constrained dynamic facility layout problem
European Journal of Operational Research
(1992) - et al.
A simulated annealing algorithm for dynamic layout problem
Computers and Operations Research
(2001) - et al.
Genetic search and the dynamic facility layout problem
Computers and Operations Research
(1994) An interactive layout heuristic based on hexagonal adjacency graphs
European Journal of Operational Research
(1992)- et al.
Dynamic layout design given a scenario tree of probable futures
European Journal of Operational Research
(1992) - et al.
A parametric approach to solving bicriterion shortest path problems
European Journal of Operational Research
(1991) - et al.
Flexible machine layout design for dynamic and uncertain production environments
European Journal of Operational Research
(1998)
Cited by (123)
Economically optimal hydropower development with uncertain climate change
2023, Journal of HydrologyCapability-based machine layout with a matheuristic-based approach
2022, Expert Systems with ApplicationsIntegrating facility layout design and aisle structure in manufacturing systems: Formulation and exact solution
2021, European Journal of Operational ResearchA two-stage optimization approach for aircraft hangar maintenance planning and staff assignment problems under MRO outsourcing mode
2020, Computers and Industrial EngineeringA systematic study on meta-heuristic approaches for solving the graph coloring problem
2020, Computers and Operations Research
- ☆
This research was supported by DFG research project SFB 467 “Wandlungsfähige Unternehmensstrukturen für die variantenreiche Serienproduktion”.