A mixed-integer programming formulation of the double row layout problem based on a linear extension of a partial order
- PDF / 452,413 Bytes
- 17 Pages / 439.37 x 666.142 pts Page_size
- 54 Downloads / 194 Views
A mixed-integer programming formulation of the double row layout problem based on a linear extension of a partial order André R. S. Amaral1 Received: 4 January 2020 / Accepted: 3 October 2020 © Springer-Verlag GmbH Germany, part of Springer Nature 2020
Abstract The double row layout problem (DRLP) occurs in automated manufacturing environments, where a material-handling device transports materials among machines arranged in a double-row layout, i.e. a layout in which the machines are located on either side of a straight line corridor. The DRLP is how to minimize the total cost of transporting materials between machines. The problem is NP-Hard and one great challenge nowadays is how to solve problem instances in reasonable computational times. In this paper, we give a new mixed-integer programming model of the DRLP, which is based on a linear extension of a partial order. In addition, we propose a reformulation of this model, which yields stronger results. The new models have the least number of 0–1 variables in comparison with previous models in the literature. Computational experiments demonstrate that the proposed models obtain optimal solutions faster than previously published ones. Keywords Facility layout · Integer programming · Combinatorial optimization
1 Introduction A double-row layout of machines in a flexible manufacturing system is a layout in which the machines are located on either side of a straight line corridor. The problem of allocating machines according to a double row layout in such a way that the total cost of transporting materials between machines is minimized is called the double row layout problem (DRLP). The DRLP has been investigated by several researchers (e.g. [7,9,21,31,39]). The problem has relevant applicability in the industrial practice
B 1
André R. S. Amaral [email protected] Graduate School of Computer Science (PPGI), Federal University of Espírito Santo, UFES, Vitória 29075-910, Brazil
123
A. R. S. Amaral
such as, for example, in semiconductor manufacturing [44,47], in a LCD fabrication line [21] and in flexible manufacturing systems design [31,36]. This paper focuses on the exact solution of the DRLP. The following notation will be utilized throughout: n N = {1, . . . , n} R = {upper row, lower row} ci j i L := nk=1 i
number of machines set of machines set of rows that defines a corridor amount of flow between machines i and j (1 ≤ i < j ≤ n) length of machine i (1 ≤ i ≤ n) sum of lengths of all facilities
Assumptions: i. ii. iii. iv.
The corridor lies with its length along the x-axis on the interval [0, L]; The width of the corridor is negligible; The distance between two machines is taken as the x-distance between their centers. The total cost of transporting materials between machines to be minimized is given ϕ by 1≤i< j≤n ci j di j ϕ where di j is the distance between the centers of machines i and j with reference to a double row layout ϕ.
We also assume that clearances between machines are all equal and have been included in the dimensions of the machine
Data Loading...
