Abstract
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.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
Aarts, E., & Korst, J. (1989). Simulated annealing and Boltzmann machines—a stochastic approach to combinatorial optimization and neural computing. New York: Wiley.
Brunetta, L., & Grégoire, Ph. (2005). A general purpose algorithm for three-dimensional packing. INFORMS Journal on Computing, 17(3), 328–338.
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.
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.
Dyckhoff, H. (1990). A typology of cutting and packing problems. European Journal of Operational Research, 44, 145–159.
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.
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.
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.
Garey, M. R., & Johnson, D. S. (1979). Computers and intractability: a guide to the theory of NP-completeness. New York: Freeman.
Glover, F. (1990). Tabu search: a tutorial. Interfaces, 20(4), 74–94.
Hansen, P., & Mladenovič, N. (2001). Variable neighborhood search: Principles and applications. European Journal of Operational Research, 130, 449–467.
ILOG (2007). CP Optimizer user’s manual and reference manual. ILOG, Paris.
Imahori, S., Yagiura, M., & Ibaraki, T. (2003). Local search algorithms for the rectangle packing problem with general spatial costs. Mathematical Programming, 97, 543–569.
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.
Jussien, N., & Lhomme, O. (2002). Local search with constraint propagation and conflict-based heuristics. Artificial Intelligence, 139, 21–45.
Lodi, A., Martello, S., & Monaci, M. (2002). Two-dimensional packing problem: a survey. European Journal of Operational Research, 141, 241–252.
Martello, S., Pisinger, D., & Vigo, D. (2000). The three dimensional bin packing problem. Operations Research, 48(2), 256–267.
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.
Martello, S., & Toth, P. (1990). Knapsack problems—algorithms and computer implementations. New York: Wiley.
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.
Van Hentenryck, P., & Michel, L. (2005). Constraint-based local search. Cambridge, MA: The MIT Press.
Voudouris, C. (1997). Guided local search for combinatorial optimization problems. Ph.D. Thesis, Department of Computer Science, University of Essex, Colchester, United Kingdom.
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.
Voudouris, C., & Tsang, E. (1999). Guided local search and its application to the traveling salesman problem. European Journal of Operational Research, 113, 469–499.
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.
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Bay, M., Crama, Y., Langer, Y. et al. Space and time allocation in a shipyard assembly hall. Ann Oper Res 179, 57–76 (2010). https://doi.org/10.1007/s10479-008-0461-8
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10479-008-0461-8