References
73
4.6 References and Further Reading
The UA-FLP has received much attention since it was first stated in Armour and
Buffa (1963). A MILO model for the problem was introduced by Meller et al
(1999) and enhanced in Sherali et al (2003). In the latter work, the area constraint is
replaced by a polyhedral outer approximation on Δ points of (4.4):
a i w i + 4
w min
i
+
λ
Δ − 1
(w max
i
− w min
i )
2
h i ≥ 2a i
w min
i
+
λ
Δ − 1
(w max
i
− w min
i )
,
for λ = 0, 1, . . . , Δ − 1. This approximation was also used in Meller et al (2007)
and Liu and Meller (2007). It is effective in practice but less efficient than the
second-order cone relaxation in Sect. 4.1. Moreover, second-order cone constraints
are supported by all state-of-the-art MILO solvers.
The sequence-pair representation was first used for circuit design in Murata et al
(1995) and for the FLP in Meller et al (2007) and Liu and Meller (2007).
The attractor–repeller paradigm is from Anjos and Vannelli (2002). The strategy
of measuring the centre-to-centre distance was presented in Jankovits et al (2011)
and Anjos and Vieira (2016). The definition of four sectors to establish the relative
position of the departments is due to Kulturel-Konak and Konak (2013). The
Delaunay triangulation is a standard construction in computational geometry; more
details can be found in Preparata and Shamos (2012). An accessible introduction to
genetic algorithms can be found in the excellent book of Mitchell (1998). Using a
two-stage approach closely following the ideas in this chapter, Anjos and Vieira
(2016) computed layouts for instances with up to 100 departments in less than
15 min of computational time. Flexible bay structures were considered in Meller
(1997), and a MILO formulation was proposed in Konak et al (2006).
References
Anjos MF, Vannelli A (2002) An attractor-repeller approach to floorplanning. Math Methods Oper
Res 56(1):3–27
Anjos MF, Vieira MVC (2016) An improved two-stage optimization-based framework for unequalareas facility layout. Optimization Letters 10(7):1379–1392
Armour GC, Buffa ES (1963) A heuristic algorithm and simulation approach to relative location
of facilities. Management Science 9(2):294–309
Jankovits I, Luo C, Anjos MF, Vannelli A (2011) A convex optimisation framework for the
unequal-areas facility layout problem. Eur J Oper Res 214(2):199–215
Konak A, Kulturel-Konak S, Norman BA, Smith AE (2006) A new mixed integer programming
formulation for facility layout design using flexible bays. Oper Res Lett 34:660–672
Kulturel-Konak S, Konak A (2013) Linear programming based genetic algorithm for the unequal
area facility layout problem. Int J Prod Res 51(14):4302–4324
Liu Q, Meller RD (2007) A sequence-pair representation and MIP-model-based heuristic for the
facility layout problem with rectangular departments. IIE Transactions 39(4):377–394
73
4.6 References and Further Reading
The UA-FLP has received much attention since it was first stated in Armour and
Buffa (1963). A MILO model for the problem was introduced by Meller et al
(1999) and enhanced in Sherali et al (2003). In the latter work, the area constraint is
replaced by a polyhedral outer approximation on Δ points of (4.4):
a i w i + 4
w min
i
+
λ
Δ − 1
(w max
i
− w min
i )
2
h i ≥ 2a i
w min
i
+
λ
Δ − 1
(w max
i
− w min
i )
,
for λ = 0, 1, . . . , Δ − 1. This approximation was also used in Meller et al (2007)
and Liu and Meller (2007). It is effective in practice but less efficient than the
second-order cone relaxation in Sect. 4.1. Moreover, second-order cone constraints
are supported by all state-of-the-art MILO solvers.
The sequence-pair representation was first used for circuit design in Murata et al
(1995) and for the FLP in Meller et al (2007) and Liu and Meller (2007).
The attractor–repeller paradigm is from Anjos and Vannelli (2002). The strategy
of measuring the centre-to-centre distance was presented in Jankovits et al (2011)
and Anjos and Vieira (2016). The definition of four sectors to establish the relative
position of the departments is due to Kulturel-Konak and Konak (2013). The
Delaunay triangulation is a standard construction in computational geometry; more
details can be found in Preparata and Shamos (2012). An accessible introduction to
genetic algorithms can be found in the excellent book of Mitchell (1998). Using a
two-stage approach closely following the ideas in this chapter, Anjos and Vieira
(2016) computed layouts for instances with up to 100 departments in less than
15 min of computational time. Flexible bay structures were considered in Meller
(1997), and a MILO formulation was proposed in Konak et al (2006).
References
Anjos MF, Vannelli A (2002) An attractor-repeller approach to floorplanning. Math Methods Oper
Res 56(1):3–27
Anjos MF, Vieira MVC (2016) An improved two-stage optimization-based framework for unequalareas facility layout. Optimization Letters 10(7):1379–1392
Armour GC, Buffa ES (1963) A heuristic algorithm and simulation approach to relative location
of facilities. Management Science 9(2):294–309
Jankovits I, Luo C, Anjos MF, Vannelli A (2011) A convex optimisation framework for the
unequal-areas facility layout problem. Eur J Oper Res 214(2):199–215
Konak A, Kulturel-Konak S, Norman BA, Smith AE (2006) A new mixed integer programming
formulation for facility layout design using flexible bays. Oper Res Lett 34:660–672
Kulturel-Konak S, Konak A (2013) Linear programming based genetic algorithm for the unequal
area facility layout problem. Int J Prod Res 51(14):4302–4324
Liu Q, Meller RD (2007) A sequence-pair representation and MIP-model-based heuristic for the
facility layout problem with rectangular departments. IIE Transactions 39(4):377–394