Single-row equidistant facility layout as a special case of single-row facility layout

References

• Adolphson, D. 1977. “Singlemachine Job Sequencing with Precedence Constraints.” SIAM Journal on Computing 6: 40–54.
   Google Scholar
• Altinel, I. K., and T. Öncan. 2005. “Design of Unidirectional Cyclic Layouts.” International Journal of Production Research 43(19): 3983–4008.
   Web of Science ®Google Scholar
• Amaral, A. R. S. 2006. “On the Exact Solution of a Facility Layout Problem.” European Journal of Operational Research 173(2): 508–518.
   Web of Science ®Google Scholar
• Amaral, A. R. S. 2008. “An Exact Approach to the One-Dimensional Facility Layout Problem.” Operations Research 56(4): 1026–1033. doi:10.1287/opre.1080.0548.
   Web of Science ®Google Scholar
• Amaral, A. R. S. 2009. “A New Lower Bound for the Single Row Facility Layout Problem.” Discrete Applied Mathematics 157(1): 183–190.
   Web of Science ®Google Scholar
• Amaral, A. R. S., and A. N. Letchford. 2012. “A Polyhedral Approach to the Single Row Facility Layout Problem”. Mathematical Programming, 1–25. Available online.
   Google Scholar
• Aneke, N. A. G., and A. S. Carrie. 1986. “A Design Technique for the Layout of Multi-product Flowlines.” International Journal of Production Research 24(3): 471–481.
   Web of Science ®Google Scholar
• Anjos, M. F., A. Kennings, and A. Vannelli. 2005. “A Semidefinite Optimization Approach for the Single-row Layout Problem with Unequal Dimensions.” Discrete Optimization 2(2): 113–122.
   Google Scholar
• Handbook on Semidefinite, Conic and Polynomial Optimization Theory, Algorithms, Software and Applications. International Series in Operations Research & Management Science Anjos MF Lasserre JB Springer-Verlag New York 2011
   Google Scholar
• Anjos, M. F., and A. Vannelli. 2008. “Computing Globally Optimal Solutions for Single-row Layout Problems Using Semidefinite Programming and Cutting Planes.” INFORMS Journal On Computing 20(4): 611–617.
   Web of Science ®Google Scholar
• Anjos, M. F., and G. Yen. 2009. “Provably Near-optimal Solutions for Very Large Single-row Facility Layout Problems.” Optimization Methods and Software 24(4): 805–817.
   Web of Science ®Google Scholar
• Bhasker, J., and S. Sahni. 1987. “Optimal Linear Arrangement of Circuit Components.” Proceedings of the 20th Annual Hawaii International Conference on System Sciences 2: 99–111.
   Google Scholar
• Bornstein, C. F., and S. Vempala. 2004. “Flow Metrics.” Theoretical Computer Science 321: 13–24.
   Web of Science ®Google Scholar
• Boyd, S., and L. Vandenberghe. 2004. Convex Optimization. New York: Cambridge University Press.
   Google Scholar
• Buchheim, C., A. Wiegele, and L. Zheng. 2010. “Exact Algorithms for the Quadratic Linear Ordering Problem.” INFORMS Journal on Computing 22(1): 168–177.
   Web of Science ®Google Scholar
• Caprara, A., M. Jung, M. Oswald, G. Reinelt, and E. Traversi. 2011. “Optimal Linear Arrangements Using Betweenness Variables.” Mathematical Programming Computation 3(3): 261–280.
   Google Scholar
• Caprara, A., A. N. Letchford, and J. Salazar-González. 2011. “Decorous Lower Bounds for Minimum Linear Arrangement.” INFORMS Journal on Computing 23(1): 26–40.
   Web of Science ®Google Scholar
• Charikar, M., M. T. Hajiaghayi, H. Karloff, and S. Rao. 2006. “l Spreading Metrics for Vertex Ordering Problems.” In Proceedings of the Seventeenth Annual ACM-SIAM Symposium on Discrete Algorithm, SODA ’06, 1018–1027, New York.
   Google Scholar
• Chen, P. P.-S. 1976. “The Entity-relationship Model-toward a Unified View of Data.” ACM Transactions on Database Systems 1: 9–36.
   Google Scholar
• Chimani, M., and P. Hungerländer. 2012a. “Multi-Level Verticality Optimization: Concept, Strategies, and Drawing Scheme.” Journal of Graph Algorithms and Applications. Accepted, preprint. http://www.ae.uni-jena.de/Research_Pubs/MLVO.html
   Google Scholar
• Chimani, M., and P. Hungerländer. 2012b. “Exact Approaches to Multi-Level Vertical Orderings.” INFORMS Journal on Computing. Accepted, preprint. http://www.ae.uni-jena.de/Research_Pubs/MLVO.html
   Google Scholar
• Chimani, M., P. Hungerländer, M. Jünger, and P. Mutzel. 2011. “An SDP Approach to Multi-level Crossing Minimization.” In Proceedings of Algorithm Engineering & Experiments [ALENEX’2011], 116–126. San Francisco, CA.
   Google Scholar
• Chow, W.-M. 1986. “An Analysis of Automated Storage and Retrieval Systems in Manufacturing Assembly Lines.” IIE Transactions 18(2): 204–214.
   Web of Science ®Google Scholar
• Christofides, N., and E. Benavent. 1989. “An Exact Algorithm for the Quadratic Assignment Problem on a Tree.” Operations Research 37(5): 760–768.
   Web of Science ®Google Scholar
• Datta, D., A. R. S. Amaral, and J. R. Figueira. 2011. “Single Row Facility Layout Problem using a Permutation-based Genetic Algorithm.” European Journal of Operational Research 213(2): 388–394.
   Web of Science ®Google Scholar
• Díaz, J., J. Petit, and M. Serna. 2002. “A Survey of Graph Layout Problems.” ACM Computing Surveys 34: 313–356.
   Web of Science ®Google Scholar
• Drezner, Z. 2006. “Finding a Cluster of Points and the Grey Pattern Quadratic Assignment Problem.” OR Spectrum 28: 417–436.
   Web of Science ®Google Scholar
• Feige, U., and J. R. Lee. 2007. “An Improved Approximation Ratio for the Minimum Linear Arrangement Problem.” Information Processing Letters 101: 26–29.
   Web of Science ®Google Scholar
• Fischer, I., G. Gruber, F. Rendl, and R. Sotirov. 2006. “Computational Experience with a Bundle Method for Semidefinite Cutten Plane Relaxations of Max-cut and Equipartition.” Mathematical Programming 105: 451–469.
   Google Scholar
• Gane, C. P., and T. Sarson. 1979. Structured Systems Analysis: Tools and Techniques. 1st ed. Englewood Cliffs, NJ: Prentice Hall Professional Technical Reference.
   Google Scholar
• Garey, M. R., and D. S. Johnson. 1979. Computers and Intractability: A Guide to the Theory of NP-completeness. New York: W. H. Freeman & Co..
   Google Scholar
• Garey, M. R., D. S. Johnson, and L. Stockmeyer. 1974. “Some Simplified NP-complete Problems.” In STOC ’74: Proceedings of the Sixth Annual ACM Symposium on Theory of Computing, 47–63, New York.
   Google Scholar
• Goemans, M., and D. Williamson. 1995. “Improved Approximation Algorithms for Maximum Cut and Satisfiability Problems using Semidefinite Programming.” Journal of the ACM 42: 1115–1145.
   Web of Science ®Google Scholar
• Gomes de Alvarenga, A., F. J. Negreiros-Gomes, and M. Mestria. 2000. “Metaheuristic Methods for a Class of the Facility Layout Problem.” Journal of Intelligent Manufacturing 11 : 421–430.
   Google Scholar
• Hall, K. M. 1970. “An r-dimensional Quadratic Placement Algorithm.” Management Science 17(3): 219–229.
   Web of Science ®Google Scholar
• Harper, L. H. 1964. “Optimal Assignments of Numbers to Vertices.” SIAM Journal on Applied Mathematics 12: 131–135.
   Web of Science ®Google Scholar
• Harper, L. H. 1966. “Optimal Numberings and Isoperimetric Problems on Graphs.” Journal of Combinatorial Theory 1: 385–393.
   Google Scholar
• Helmberg, C. 2000. “Fixing Variables in Semidefinite Relaxations.” SIAM Journal on Matrix Analysis and Applications 21(3): 952–969.
   Web of Science ®Google Scholar
• Helmberg, C., F. Rendl, R. Vanderbei, and H. Wolkowicz. 1996. “An Interior-point Method for Semidefinite Programming.” SIAM Journal on Optimization 6: 342–361.
   Web of Science ®Google Scholar
• Heragu, S. S., and A. S. Alfa. 1992. “Experimental Analysis of Simulated Annealing Based Algorithms for the Layout Problem.” European Journal of Operational Research 57(2): 190–202.
   Web of Science ®Google Scholar
• Heragu, S. S., and A. Kusiak. 1988. “Machine Layout Problem in Flexible Manufacturing Systems.” Operations Research 36(2): 258–268.
   Web of Science ®Google Scholar
• Heragu, S. S., and A. Kusiak. 1991. “Efficient Models for the Facility Layout Problem.” European Journal of Operational Research 53(1): 1–13.
   Web of Science ®Google Scholar
• Hungerländer, P. 2012. “Semidefinite Approaches to Ordering Problems.” PhD thesis, Alpen-Adria Universität Klagenfurt.
   Google Scholar
• Hungerländer, P., and M. Anjos. 2012. A Semidefinite Optimization Approach to Space-free Multi-row Facility Layout. Cahier du GERAD G-2012-03, GERAD, Montreal, QC, Canada.
   Google Scholar
• Hungerländer, P., and F. Rendl. 2013b. “A Computational Study and Survey of Methods for the Single-row Facility Layout Problem.” Computational Optimization and Applications 55(1): 1–20.
   Web of Science ®Google Scholar
• Hungerländer, P., and F. Rendl. 2013a. “Semidefinite Relaxations of Ordering Problems.” Mathematical Programming 140 (1): 77–97.
   Google Scholar
• Juvan, M., and B. Mohar. 1992. “Optimal Linear Labelings and Eigenvalues of Graphs.” Discrete Applied Mathematics 36(2): 153–168.
   Web of Science ®Google Scholar
• Karp, R. M. 1993. “Mapping the Genome: Some Combinatorial Problems Arising in Molecular Biology.” In Proceedings of the Twenty-fifth Annual ACM Symposium on Theory of Computing, STOC ’93, 278–285, New York: ACM.
   Google Scholar
• Karp, R. M., and M. Held. 1967. “Finite-state Processes and Dynamic Programming.” SIAM Journal on Applied Mathematics 15(3): 693–718.
   Web of Science ®Google Scholar
• Koopmans, T. C., and M. Beckmann. 1957. “Assignment Problems and the Location of Economic Activities.” Econometrica 25(1): 53–76.
   Web of Science ®Google Scholar
• Koren, Y., and D. Harel. 2002. “A Multi-scale Algorithm for the Linear Arrangement Problem.” In Revised Papers from the 28th International Workshop on Graph-theoretic Concepts in Computer Science, WG ’02, 296–309, London: Springer-Verlag.
   Google Scholar
• Kouvelis, P., W.-C. Chiang, and G. Yu. 1995. “Optimal Algorithms for Row Layout Problems in Automated Manufacturing Systems.” IIE Transactions 27(1): 99–104.
   Web of Science ®Google Scholar
• Kouvelis, P., and M. W. Kim. 1992. “Unidirectional Loop Network Layout Problem in Automated Manufacturing Systems.” Operations Research 40: 533–550.
   Web of Science ®Google Scholar
• Kumar, K. R., G. C. Hadjinicola, and T.-L. Lin. 1995. “A Heuristic Procedure for the Single-row Facility Layout Problem.” European Journal of Operational Research 87(1): 65–73.
   Web of Science ®Google Scholar
• Lovász, L., and A. Schrijver. 1991. “Cones of Matrices and Set-functions and 0–1 Optimization.” SIAM Journal on Optimization 1: 166–190.
   Web of Science ®Google Scholar
• Love, R. F., and J. Y. Wong. 1967. “On Solving a One-dimensional Space Allocation Problem with Integer Programming.” INFOR 14: 139–143.
   Google Scholar
• McAllister, A. J. 1999. “A New Heuristic Algorithm for the Linear Arrangement Problem.” Technical report, University of New Brunswick, Faculty of Computer Science, TR-99-126a.
   Google Scholar
• Meller, R., and K.-Y. Gau. 1996. “The Facility Layout Problem: Recent and Emerging Trends and Perspectives.” Journal of Manufacturing Systems 5(5): 351–366.
   Web of Science ®Google Scholar
• Mitchison, G., and R. Durbin. 1986. “Optimal Numberings of an N N Array.” SIAM Journal on Algebraic and Discrete Methods 7: 571–582.
   Google Scholar
• Nori, V. S., and B. R. Sarker. 1997. “Designing Multi-product Lines: Job Routing in Cellular Manufacturing Systems.” Journal of the Operational Research Society 48(4): 412–422.
   Web of Science ®Google Scholar
• Nugent, C. E., T. E. Vollmann, and J. Ruml. 1968. “An Experimental Comparison of Techniques for the Assignment of Facilities to Locations.” Operations Research 16(1): 150–173.
   Web of Science ®Google Scholar
• Obata, T. 1979. “Quadratic Assignment Problem: Evaluation of Exact and Heuristic Algorithms.” PhD thesis, Rensselaer Polytechnic Institute, Troy, NY.
   Google Scholar
• Palubeckis, G. 2012. “A Branch-and-bound Algorithm for the Single-row Equidistant Facility Layout Problem.” OR Spectrum 34: 1–21.
   Web of Science ®Google Scholar
• Petit, J. 2003a. “Combining Spectral Sequencing and Parallel Simulated Annealing for the MinLA Problem.” Parallel Processing Letters 13(1): 77–91.
   Google Scholar
• Petit, J. 2003b. “Experiments on the Minimum Linear Arrangement Problem.” ACM Journal of Experimental Algorithmics 8.
   Google Scholar
• Picard, J.-C., and M. Queyranne. 1981. “On the One-dimensional Space Allocation Problem.” Operations Research 29(2): 371–391.
   Web of Science ®Google Scholar
• Rao, S., and A. W. Richa. 2005. “New Approximation Techniques for Some Linear Ordering Problems.” SIAM Journal on Computing 34: 388–404.
   Web of Science ®Google Scholar
• Ravi, R., A. Agrawal, and P. Klein. 1991. “Ordering Problems Approximated: Single-processor Scheduling and Interval Graphs Connection.” In 18th International Colloquium on Automata, Languages and Programming, Vol. 150 of Lecture Notes in Computer Science, edited by J. L. Albert, B. R. Artalejo, and B. Monien, 751–762. New York: Springer-Verlag.
   Google Scholar
• Rendl, F., G. Rinaldi, and A. Wiegele. 2010. “Solving Max-cut to Optimality by Intersecting Semidefinite and Polyhedral Relaxations.” Mathematical Programming 212: 307–335.
   Web of Science ®Google Scholar
• Rodriguez-Tello, E., J.-K. Hao, and J. Torres-Jimenez. 2008. “An Effective Two-stage Simulated Annealing Algorithm for the Minimum Linear Arrangement Problem.” Computers & Operations Research 35 : 3331–3346.
   Google Scholar
• Romero, D., and A. Sánchez-Flores. 1990. “Methods for the One-dimensional Space Allocation Problem.” Computers & Operations Research 17(5): 465–473.
   Web of Science ®Google Scholar
• Samarghandi, H., and K. Eshghi. 2010. “An Efficient Tabu Algorithm for the Single Row Facility Layout Problem.” European Journal of Operational Research 205(1): 98–105.
   Web of Science ®Google Scholar
• Sarker, B., W. Wilhelm, and G. Hogg. 1998. “One-Dimensional Machine Location Problems in a Multi-product Flowline with Equidistant Locations.” European Journal of Operational Research 105(3): 401–426.
   Web of Science ®Google Scholar
• Sarker, B. R. 1989. “The Amoebic Matrix and One-dimensional Machine Location Problems.” PhD thesis, Department of Industrial Engineering, Texas A &M University, College Station, TX.
   Google Scholar
• Sarker, B. R., and Y. Xu. 2000. “Designing Multi-product Lines: Job Routing in Cellular Manufacturing Systems.” IIE Transactions 32: 219–235.
   Web of Science ®Google Scholar
• Sarker, B. R., and J. Yu. 1994. “A Two-phase Procedure for Duplicating Bottleneck Machines in a Linear Layout, Cellular Manufacturing System.” International Journal of Production Research 32(9): 2049–2066.
   Web of Science ®Google Scholar
• Schwarz, R. 2010. “A Branch-and-Cut Algorithm with Betweenness Variables for the Linear Arrangement Problems.” Diploma thesis, Heidelberg.
   Google Scholar
• Simmons, D. M. 1969. “One-dimensional Space Allocation: An Ordering Algorithm.” Operations Research 17: 812–826.
   Web of Science ®Google Scholar
• Simmons, D. M. 1971. “A Further Note on One-dimensional Space Allocation.” Operations Research 19: 249.
   Web of Science ®Google Scholar
• Suryanarayanan, J., B. Golden, and Q. Wang. 1991. “A New Heuristic for the Linear Placement Problem.” Computers & Operations Research 18(3): 255–262.
   Web of Science ®Google Scholar
• Tucker, A. W. 1960. “On Directed Graphs and Integer Programs.” Technical report, IBM Mathematical Research Project.
   Google Scholar
• Vanelli, A., and G. S. Rowan. 1986. “An Eigenvector Based Approach for Multistack VLSI layout.” Proceedings of the Midwest Symposium on Circuits and Systems 29: 135–139.
   Google Scholar
• Wang, S., and B. R. Sarker. 2002. “Locating Cells with Bottleneck Machines in Cellular Manufacturing Systems.” International Journal of Production Research 40(2): 403–424.
   Web of Science ®Google Scholar
• Handbook of Semidefinite Programming Kluwer Academic Boston, MA 2000
   Google Scholar
• Younger, D. H. 1963. “Minimum Feedback Arc Sets for a Directed Graph.” IEEE Transactions on Circuit Theory 10(2): 238–245.
   Google Scholar
• Yu, J. 1999. “Machine-cell Location Problems for Multi-product Flowlines.” PhD thesis, Department of Industrial and Manufacturing Systems Engineering, Louisiana State University, Baton Rouge.
   Google Scholar
• Yu, J., and B. R. Sarker. 2003. “Directional Decomposition Heuristic for a Linear Machine-cell Location Problem.” European Journal of Operational Research 149(1): 142–184.
   Web of Science ®Google Scholar