×

Decorous combinatorial lower bounds for row layout problems. (English) Zbl 1443.90238

Summary: In this paper we consider the Double-Row Facility Layout Problem (DRFLP). Given a set of departments and pairwise transport weights between them the DRFLP asks for a non-overlapping arrangement of the departments along both sides of a common path such that the weighted sum of the center-to-center distances between the departments is minimized. Despite its broad applicability in factory planning, only small instances can be solved to optimality in reasonable time. Apart from this even deriving good lower bounds using existing integer programming formulations and branch-and-cut methods is a challenging problem. We focus here on deriving combinatorial lower bounds which can be computed very fast. These bounds generalize the star inequalities of the Minimum Linear Arrangement Problem. Furthermore we exploit a connection of the DRFLP to some parallel identical machine scheduling problem. Our lower bounds can be further improved by combining them with a new distance-based mixed-integer linear programming model, which is not a formulation for the DRFLP, but can be solved close to optimality quickly. We compare the new lower bounds to some heuristically determined upper bounds on medium-sized and large DRFLP instances. Special consideration is given to the case when all departments have the same length. Furthermore we show that the lower bounds that we derive using adapted variants of our approaches for the Parallel Row Ordering Problem, a DRFLP variant where the row assignment of the departments is given in advance and spaces between neighboring departments are not allowed, are even better with respect to the gaps.

MSC:

90B80 Discrete location and assignment
90C11 Mixed integer programming
90C27 Combinatorial optimization

Software:

CPLEX; RowLayout
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Ahmadi, A.; Pishvaee, M. S.; Jokar, M. R.A., A survey on multi-floor facility layout problems, Computers & Industrial Engineering, 107, 158-170 (2017)
[2] Ahonen, H.; de Alvarenga, A. G.; Amaral, A. R.S., Simulated annealing and tabu search approaches for the corridor allocation problem, European Journal of Operational Research, 232, 1, 221-233 (2014) · Zbl 1305.90246
[3] Amaral, A. R.S., A mixed-integer programming formulation for the double row layout of machines in manufacturing systems, International Journal of Production Research, 57, 1, 34-47 (2019)
[4] The IV Latin-American Algorithms, Graphs, and Optimization Symposium · Zbl 1341.05236
[5] Amaral, A. R.S., On the exact solution of a facility layout problem, European Journal of Operational Research, 173, 2, 508-518 (2006) · Zbl 1110.90068
[6] Amaral, A. R.S., An exact approach to the one-dimensional facility layout problem, Operations Research, 56, 4, 1026-1033 (2008) · Zbl 1167.90556
[7] Amaral, A. R.S., A new lower bound for the single row facility layout problem, Discrete Applied Mathematics, 157, 1, 183-190 (2009) · Zbl 1155.90413
[8] Amaral, A. R.S., On duplex arrangement of vertices, Technical Report (2011), Departamento de Informática, Universidade Federal do Espírito Santo (UFES), Brazil
[9] Amaral, A. R.S., The corridor allocation problem, Computers & Operations Research, 39, 12, 3325-3330 (2012) · Zbl 1349.90552
[10] Amaral, A. R.S., Optimal solutions for the double row layout problem, Optimization Letters, 7, 2, 407-413 (2013) · Zbl 1267.90116
[11] Amaral, A. R.S., A parallel ordering problem in facilities layout, Computers & Operations Research, 40, 12, 2930-2939 (2013) · Zbl 1348.90380
[12] Amaral, A. R.S.; Letchford, A. N., A polyhedral approach to the single row facility layout problem, Mathematical Programming, 141, 1-2, 453-477 (2013) · Zbl 1280.90132
[13] Anjos, M. F.; Fischer, A.; Hungerländer, P., Solution approaches for the double-row equidistant facility layout problem, (Lübbecke, M.; Koster, A.; Letmathe, P.; Madlener, R.; Peis, B.; Walther, G., Operations research proceedings 2014 (2016), Springer International Publishing: Springer International Publishing Cham), 17-23 · Zbl 1342.90086
[14] Anjos, M. F.; Fischer, A.; Hungerländer, P., Improved exact approaches for row layout problems with departments of equal length, European Journal of Operational Research, 270, 2, 514-529 (2018) · Zbl 1403.90466
[15] Anjos, M. F.; Kennings, A.; Vannelli, A., A semidefinite optimization approach for the single-row layout problem with unequal dimensions, Discrete Optimization, 2, 2, 113-122 (2005) · Zbl 1077.90046
[16] Anjos, M. F.; Liers, F., Global approaches for facility layout and VLSI floorplanning, (Anjos, M. F.; Lasserre, J. B., Handbook on semidefinite, conic and polynomial optimization. Handbook on semidefinite, conic and polynomial optimization, International Series in Operations Research & Management Science, 166 (2012), Springer US), 849-877 · Zbl 1334.90096
[17] Anjos, M. F.; Vannelli, A., Computing globally optimal solutions for single-row layout problems using semidefinite programming and cutting planes, INFORMS Journal On Computing, 20, 4, 611-617 (2008) · Zbl 1243.90174
[18] Anjos, M. F.; Vieira, M. V.C., Mathematical optimization approaches for facility layout problems: The state-of-the-art and future research directions, European Journal of Operational Research, 261, 1-16 (2017) · Zbl 1403.90467
[19] Anjos, M. F.; Yen, G., Provably near-optimal solutions for very large single-row facility layout problems, Optimization Methods and Software, 24, 4, 805-817 (2009) · Zbl 1180.90258
[20] Bracht, U.; Dahlbeck, M.; Fischer, A.; Krüger, T., Combining simulation and optimization for extended double row facility layout problems in factory planning, (Baum, M.; Brenner, G.; Grabowski, J.; Hanschke, T.; Hartmann, S.; Schöbel, A., Simulation science (2018), Springer International Publishing: Springer International Publishing Cham), 39-59 · Zbl 1421.90188
[21] Butler, T. W.; Karwan, K. R.; Sweigart, J. R.; Reeves, G. R., An integrative model-based approach to hospital layout, IIE Transactions, 24, 2, 144-152 (1992)
[22] Caprara, A.; Letchford, A. N.; Salazar-González, J.-J., Decorous lower bounds for minimum linear arrangement, INFORMS Journal on Computing, 23, 1, 26-40 (2011) · Zbl 1243.90185
[23] Chung, J.; Tanchoco, J. M.A., The double row layout problem, International Journal of Production Research, 48, 3, 709-727 (2010) · Zbl 1197.90282
[24] Cravo, G. L.; Amaral, A. R.S., A grasp algorithm for solving large-scale single row facility layout problems, Computers & Operations Research, 106, 49-61 (2019) · Zbl 1458.90424
[25] Dahlbeck, M., Fischer, A., & Hungerländer, P. (2020). Heuristics for the double row facility layout problem based on solutions of the single row facility layout problem. Working paper.
[26] Dantzig, G. B.; Fulkerson, D. R.; Johnson, S., Solution of a large scale traveling salesman problem, Journal of the Operations Research Society of America, 2, 393-410 (1954) · Zbl 1414.90372
[27] Datta, D.; Amaral, A. R.S.; Figueira, J. R., Single row facility layout problem using a permutation-based genetic algorithm, European Journal of Operational Research, 213, 2, 388-394 (2011) · Zbl 1215.90039
[28] Drira, A.; Pierrval, H.; Hajri-Gabouj, S., Facility layout problems: A survey, Annual Reviews in Control, 31, 255-267 (2007)
[29] Edmonds, J., Matroids and the greedy algorithm, Mathematical Programming, 1, 1, 127-136 (1971) · Zbl 0253.90027
[30] Elshafei, A. N., Hospital layout as a quadratic assignment problem., Journal of the Operational Research Society, 28, 1, 167-179 (1977) · Zbl 0353.90096
[31] Fischer, A.; Fischer, F.; Hungerländer, P., A new exact approach to the space-free double row layout problem, (Doerner, K. F.; Ljubic, I.; Pflug, G.; Tragler, G., Operations research proceedings 2015, selected papers of the international conference of the German, Austrian and Swiss operations research societies (GOR, ÖGOR, SVOR/ASRO), University of Vienna, austria, September 1-4, 2015.. Operations research proceedings 2015, selected papers of the international conference of the German, Austrian and Swiss operations research societies (GOR, ÖGOR, SVOR/ASRO), University of Vienna, austria, September 1-4, 2015., Operations Research Proceedings (2015), Springer), 125-130 · Zbl 1375.90163
[32] Fischer, A.; Fischer, F.; Hungerländer, P., New exact approaches to row layout problems, Mathematical Programming Computation (2019) · Zbl 1432.90085
[33] Garey, M. R.; Johnson, D. S.; Stockmeyer, L. J., Some simplified NP-complete problems, Proceedings of the sixth annual ACM symposium on theory of computing, 47-63 (1974), ACM
[34] Guan, J.; Lin, G.; Feng, H.-B.; Ruan, Z.-Q., A decomposition-based algorithm for the double row layout problem, Applied Mathematical Modelling, 77, 963-979 (2020) · Zbl 1443.90240
[35] Gülşen, M.; Murray, C. C.; Smith, A. E., Double-row facility layout with replicate machines and split flows, Computers & Operations Research, 108, 20-32 (2019) · Zbl 1458.90434
[36] Hahn, P. M.; Krarup, J., A hospital facility layout problem finally solved, Journal of Intelligent Manufacturing, 12, 5-6, 487-496 (2001)
[37] Hall, L. A.; Schulz, A. S.; Shmoys, D. B.; Wein, J., Scheduling to minimize average completion time: Off-line and on-line approximation algorithms, Mathematics of Operations Research, 22, 3, 513-544 (1997) · Zbl 0883.90064
[38] Harper, L. H., Optimal assignments of numbers to vertices, SIAM Journal on Applied Mathematics, 12, 1, 131-135 (1964) · Zbl 0222.94004
[39] Harper, L. H., Optimal numberings and isoperimetric problems on graphs, Journal of Combinatorial Theory, 1, 3, 385-393 (1966) · Zbl 0158.20802
[40] Hassan, M. M.D., Machine layout problem in modern manufacturing facilities, International Journal of Production Research, 32, 11, 2559-2584 (1994) · Zbl 0896.90120
[41] Heragu, S. S.; Kusiak, A., Efficient models for the facility layout problem, European Journal of Operational Research, 53, 1, 1-13 (1991) · Zbl 0726.90024
[42] Hosseini-Nasab, H.; Fereidouni, S.; Fatemi Ghomi, S. M.T.; Fakhrzad, M. B., Classification of facility layout problems: a review study, The International Journal of Advanced Manufacturing Technology, 94, 1, 957-977 (2018)
[43] Hungerländer, P., A Semidefinite Optimization Approach to the Parallel Row Ordering Problem, Technical Report (2014), Alpen-Adria Universität Klagenfurt, Mathematics, Optimization Group, TR-ARUK-M-O-14-05
[44] Hungerländer, P., Single-row equidistant facility layout as a special case of single-row facility layout, International Journal of Production Research, 52, 5, 1257-1268 (2014)
[45] Hungerländer, P., The checkpoint ordering problem, Optimization, 66, 10, 1699-1712 (2017) · Zbl 1383.90031
[46] Hungerländer, P.; Anjos, M. F., A Semidefinite Optimization Approach to Space-Free Multi-Row Facility Layout, Cahiers du GERAD (2012), GERAD: GERAD Montreal, QC, Canada
[47] Hungerländer, P.; Anjos, M. F., A semidefinite optimization-based approach for global optimization of multi-row facility layout, European Journal of Operational Research, 245, 1, 46-61 (2015) · Zbl 1346.90500
[48] Hungerländer, P.; Rendl, F., A computational study and survey of methods for the single-row facility layout problem, Computational Optimization and Applications, 55, 1, 1-20 (2013) · Zbl 1272.90070
[49] Hungerländer, P.; Rendl, F., Semidefinite relaxations of ordering problems, Mathematical Programming, 140, 1, 77-97 (2013) · Zbl 1272.90046
[50] IBM (2018). ILOG CPLEX Optimization Studio 12.8.
[51] Kawaguchi, T.; Kyan, S., Worst case bound of an lrf schedule for the mean weighted flow-time problem, SIAM Journal on Computing, 15, 4, 1119-1129 (1986) · Zbl 0621.68024
[52] Keller, B.; Buscher, U., Single row layout models, European Journal of Operational Research, 245, 3, 629-644 (2015) · Zbl 1346.90501
[53] Kothari, R.; Ghosh, D., Population heuristics for the corridor allocation problem, Technical Report (2012), IIMA Working Papers WP2012-09-02, Indian Institute of Management Ahmedabad, Research and Publication Department
[54] Kothari, R.; Ghosh, D., Tabu search for the single row facility layout problem using exhaustive 2-opt and insertion neighborhoods, European Journal of Operational Research, 224, 1, 93-100 (2013) · Zbl 1292.90170
[55] Kothari, R.; Ghosh, D., A scatter search algorithm for the single row facility layout problem, Journal of Heuristics, 20, 2, 125-142 (2014)
[56] Langevin, A.; Montreuil, B.; Riopel, D., Spine layout design, The International Journal of Production Research, 32, 2, 429-442 (1994) · Zbl 0903.90080
[57] Lee, C.-Y.; Uzsoy, R., A new dynamic programming algorithm for the parallel machines total weighted completion time problem, Operations Research Letters, 11, 2, 73-75 (1992) · Zbl 0760.90057
[58] http://www.sciencedirect.com/science/article/pii/S016750600870743X · Zbl 0301.90025
[59] Liu, W.; Vannelli, A., Generating lower bounds for the linear arrangement problem, Discrete Applied Mathematics, 59, 2, 137-151 (1995) · Zbl 0827.90136
[60] Loiola, E. M.; de Abreu, N. M.M.; Boaventura-Netto, P. O.; Hahn, P.; Querido, T., A survey for the quadratic assignment problem, European Journal of Operational Research, 176, 2, 657-690 (2007) · Zbl 1103.90058
[61] Maadi, M.; Javidnia, M.; Jamshidi, R., Two strategies based on meta-heuristic algorithms for parallel row ordering problem (PROP), Iranian Journal of Management Studies, 10, 2, 467-498 (2017)
[62] Murray, C. C.; Smith, A. E.; Zhang, Z., An efficient local search heuristic for the double row layout problem with asymmetric material flow, International Journal of Production Research, 51, 20, 6129-6139 (2013)
[63] Palubeckis, G., A branch-and-bound algorithm for the single-row equidistant facility layout problem, OR Spectrum, 34, 1, 1-21 (2012) · Zbl 1238.90091
[64] Palubeckis, G., Fast local search for single row facility layout, European Journal of Operational Research, 264, 3, 800-814 (2015) · Zbl 1346.90515
[65] Palubeckis, G., Fast simulated annealing for single-row equidistant facility layout, Applied Mathematics and Computation, 263, 287-301 (2015) · Zbl 1410.90119
[66] Palubeckis, G., Single row facility layout using multi-start simulated annealing, Computers & Industrial Engineering, 103, 1-16 (2017)
[67] Samarghandi, H.; Eshghi, K., An efficient tabu algorithm for the single row facility layout problem, European Journal of Operational Research, 205, 1, 98-105 (2010) · Zbl 1187.90179
[68] Schrijver, A., Combinatorial optimization. Polyhedra and efficiency. Vol. B, Algorithms and Combinatorics, 24 (2003), Springer-Verlag: Springer-Verlag Berlin · Zbl 1041.90001
[69] Secchin, L. D.; Amaral, A. R.S., An improved mixed-integer programming model for the double row layout of facilities, Optimization Letters, 13, 1, 193-199 (2019) · Zbl 1417.90105
[70] Smith, W. E., Various optimizers for single-stage production, Naval Research Logistics Quarterly, 3, 1-2, 59-66 (1956)
[71] Tompkins, J. A.; White, J. A.; Bozer, Y. A.; Tanchoco, J. M.A., Facilities planning (2010), John Wiley & Sons
[72] Wang, S.; Zuo, X.; Liu, X.; Zhao, X.; Li, J., Solving dynamic double row layout problem via combining simulated annealing and mathematical programming, Applied Soft Computing, 37, 303-310 (2015)
[73] Yang, X.; Cheng, W.; Smith, A. E.; Amaral, A. R.S., An improved model for the parallel row ordering problem, Journal of the Operational Research Society, 71, 3, 475-490 (2020)
[74] Yu, J.; Sarker, B. R., Directional decomposition heuristic for a linear machine-cell location problem, European Journal of Operational Research, 149, 1, 142-184 (2003) · Zbl 1036.90048
[75] Zhang, Z.; Murray, C. C., A corrected formulation for the double row layout problem, International Journal of Production Research, 50, 15, 4220-4223 (2012)
[76] Zuo, X.; Gao, S.; Zhou, M.; Yang, X.; Zhao, X., A three-stage approach to a multirow parallel machine layout problem, IEEE Transactions on Automation Science and Engineering, 16, 1, 433-447 (2019)
[77] Zuo, X.; Murray, C. C.; Smith, A. E., Solving an extended double row layout problem using multiobjective tabu search and linear programming, IEEE Transactions on Automation Science and Engineering, 11, 4, 1122-1132 (2014)
[78] Zuo, X. Q.; Murray, C. C.; Smith, A. E., Sharing clearances to improve machine layout, International Journal of Production Research, 54, 14, 4272-4285 (2016)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.