Space and time allocation in a shipyard assembly hall. (English) Zbl 1201.90109
Summary: We present a space and time allocation problem that arises in assembly halls producing large building blocks (namely, a shipyard which assembles prefabricated keel elements). The building blocks are very large, and, once a block is placed in the hall, it cannot be moved until all assembly operations on this block are complete. Each block must be processed during a predetermined time window. The objective is to maximize the number of building blocks produced in the hall.
The problem is modeled as a 3-dimensional bin packing problem (3D-BPP) and is handled by a Guided Local Search heuristic initially developed for the 3D-BPP. Our computational experiments with this heuristic demonstrate that excellent results can be found within minutes on a workstation. We also describe some additional real-life constraints arising in the industrial application, and we show how these constraints can be conveniently and flexibly integrated in the solution procedure.
The problem is modeled as a 3-dimensional bin packing problem (3D-BPP) and is handled by a Guided Local Search heuristic initially developed for the 3D-BPP. Our computational experiments with this heuristic demonstrate that excellent results can be found within minutes on a workstation. We also describe some additional real-life constraints arising in the industrial application, and we show how these constraints can be conveniently and flexibly integrated in the solution procedure.
References:
| [1] | Aarts, E., & Korst, J. (1989). Simulated annealing and Boltzmann machines–a stochastic approach to combinatorial optimization and neural computing. New York: Wiley. · Zbl 0674.90059 |
| [2] | Brunetta, L., & Grégoire, Ph. (2005). A general purpose algorithm for three-dimensional packing. INFORMS Journal on Computing, 17(3), 328–338. · Zbl 1239.90108 · doi:10.1287/ijoc.1030.0068 |
| [3] | Coffman, E. G., Garey, M. R., & Johnson, D. S. (1997). Approximation algorithms for bin packing: A survey. In D. S. Hochbaum (Ed.), Approximation algorithms for NP-hard problems. Boston: PWS Publishing Company. · Zbl 0558.68062 |
| [4] | Coffman, E. G., Galambos, G., Martello, S., & Vigo, D. (1999). Packing approximation algorithms: Combinatorial analysis. In D.-Z. Du & P. M. Pardalos (Eds.), Handbook of combinatorial optimization. Dordrecht: Kluwer Academic. · Zbl 1253.90191 |
| [5] | Dyckhoff, H. (1990). A typology of cutting and packing problems. European Journal of Operational Research, 44, 145–159. · Zbl 0684.90076 · doi:10.1016/0377-2217(90)90350-K |
| [6] | Dyckhoff, H., Scheithauer, G., & Terno, J. (1997). Cutting and packing. In M. Dell’Amico, F. Maffioli, & S. Martello (Eds.), Annotated bibliographies in combinatorial optimization. New York: Wiley. · Zbl 1068.90509 |
| [7] | Faroe, O., Pisinger, D., & Zachariasen, M. (2003). Guided local search for the three-dimensional bin-packing problem. INFORMS Journal on Computing, 15(3), 267–283. · Zbl 1238.90112 · doi:10.1287/ijoc.15.3.267.16080 |
| [8] | Focacci, F., Laburthe, F., & Lodi, A. (2003). Local search and constraint programming. In F. Glover & G. Kochenberger (Eds.), Handbook of metaheuristics. International Series in Operations Research & Management Science. Dordrecht: Kluwer Academic. · Zbl 1137.90729 |
| [9] | Garey, M. R., & Johnson, D. S. (1979). Computers and intractability: a guide to the theory of NP-completeness. New York: Freeman. · Zbl 0411.68039 |
| [10] | Glover, F. (1990). Tabu search: a tutorial. Interfaces, 20(4), 74–94. · doi:10.1287/inte.20.4.74 |
| [11] | Hansen, P., & Mladenovič, N. (2001). Variable neighborhood search: Principles and applications. European Journal of Operational Research, 130, 449–467. · Zbl 0981.90063 · doi:10.1016/S0377-2217(00)00100-4 |
| [12] | ILOG (2007). CP Optimizer user’s manual and reference manual. ILOG, Paris. |
| [13] | Imahori, S., Yagiura, M., & Ibaraki, T. (2003). Local search algorithms for the rectangle packing problem with general spatial costs. Mathematical Programming, 97, 543–569. · Zbl 1106.90370 · doi:10.1007/s10107-003-0427-1 |
| [14] | Imahori, S., Yagiura, M., & Ibaraki, T. (2005). Improved local search algorithms for the rectangle packing problem with general spatial costs. European Journal of Operational Research, 167, 48–67. · Zbl 1074.90022 · doi:10.1016/j.ejor.2004.02.020 |
| [15] | Jussien, N., & Lhomme, O. (2002). Local search with constraint propagation and conflict-based heuristics. Artificial Intelligence, 139, 21–45. · Zbl 1015.68056 · doi:10.1016/S0004-3702(02)00221-7 |
| [16] | Lodi, A., Martello, S., & Monaci, M. (2002). Two-dimensional packing problem: a survey. European Journal of Operational Research, 141, 241–252. · Zbl 1081.90576 · doi:10.1016/S0377-2217(02)00123-6 |
| [17] | Martello, S., Pisinger, D., & Vigo, D. (2000). The three dimensional bin packing problem. Operations Research, 48(2), 256–267. · Zbl 1106.90371 · doi:10.1287/opre.48.2.256.12386 |
| [18] | Martello, S., Pisinger, D., Vigo, D., Den Boef, E., & Korst, J. (2007). Algorithm 864: General and robot-packable variants of the three-dimensional bin packing problem. ACM Transactions on Mathematical Software, 33(1), 1–12. · doi:10.1145/1206040.1206047 |
| [19] | Martello, S., & Toth, P. (1990). Knapsack problems–algorithms and computer implementations. New York: Wiley. · Zbl 0708.68002 |
| [20] | Pisinger, D., & Sigurd, M. (2007). Using decomposition techniques and constraint programming for solving the two-dimensional bin-packing problem. INFORMS Journal on Computing, 19(1), 36–51. · Zbl 1241.90118 · doi:10.1287/ijoc.1060.0181 |
| [21] | Van Hentenryck, P., & Michel, L. (2005). Constraint-based local search. Cambridge, MA: The MIT Press. · Zbl 1153.90582 |
| [22] | Voudouris, C. (1997). Guided local search for combinatorial optimization problems. Ph.D. Thesis, Department of Computer Science, University of Essex, Colchester, United Kingdom. · Zbl 0882.90102 |
| [23] | Voudouris, C., & Tsang, E. (1997). Fast local search and guided local search and their application to British Telecom’s workforce scheduling problem. Operations Research Letters, 20, 119–127. · Zbl 0882.90102 · doi:10.1016/S0167-6377(96)00042-9 |
| [24] | Voudouris, C., & Tsang, E. (1999). Guided local search and its application to the traveling salesman problem. European Journal of Operational Research, 113, 469–499. · Zbl 0937.90094 · doi:10.1016/S0377-2217(98)00099-X |
| [25] | Wang, C. J., & Tsang, E. (1991). Solving constraint satisfaction problems using neural-networks. In Proceedings of IEE second international conference on artificial neural networks, pp. 295–299. |
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.
