Space allocation; Optimization; Decision making; Scheduling; Planning; Shipbuilding; 3D bin-packing
Abstract :
[en] In this paper we describe the development of a tool that allows planners to efficiently
and effectively plan space within valuable areas of a shipyard. Traditionally, space is
considered as resource; however, it is difficult to accurately account for and plan its
consumption with the current planning software tools available. The spatial scheduling
tool described in this paper can be used by planners to manually or automatically
reserve space within the shipyard for construction of large blocks over the entire ship
erection period. The software is coupled with a heuristic optimization solver which is
inspired by an algorithm used for "3D bin-packing problems". The result is the ability to
efficiently generate and compare multiple space allocation alternatives in a reduced
time with the ultimate goal of maintaining the critical ship erection schedule. Better
solution than manual or semi-automatic allocation of blocks can be obtained through
the optimization module.
Hugues O (1994) Applied computer aided design. Technical report, International Ship and Offshore Structure Congress - ISSC, inst. marine dynamics, Newfoundland
List of the world's largest cruise ships. http://en.wikipedia.org/wiki/
Kim Y, Lee D (2007) A study on the construction of detail integrated scheduling system of shipbuilding process. J Soc Naval Archit Korea 44:48-54
Bair F, Langer Y, Caprace J, Rigo P (2005) Modelling, simulation and optimization of a shipbuilding workshop. COMPIT'05 - the 4th international conference on computer applications and information technology in the maritime industries, May, vol 1, Hamburg, pp 283-293
Nedeb C, Friedewald A, Wagner L, Hubler M (2006) Simulation of material flow processes in the planning of production spaces in shipbuilding. COMPIT'06 - the 5th international conference on computer applications and information technology in the maritime industries, May, vol 1, Leiden, pp 186-198
Park K, Lee K, Park S, Kim S (1996) Modeling and solving the spatial block scheduling problem in a shipbuilding company. Comput Ind Eng 30:357-364
Okumoto Y, Iseki R (2005) Optimization of block allocation in assembly area using simulated annealing method. J Jpn Soc Naval Archit Ocean Eng 1:71-76 (in Japanese)
Lee K, Lee J, Choi S (1996) A spatial scheduling system and its application to shipbuilding: DAS-CURVE. Exp Syst Appl 10:311-324
Lee D, Kang Y, Kim H (2005) Block assignment planning for shipbuilding considering preference shop and load balancing. Proc 12th ICCAS 2005 1:55-68
Wibisono M, Hamada K, Kitamura M, Kesavadey V (2007) Optimization system of block division using genetic algorithm and product model. J Jpn Soc Naval Archit Ocean Eng 6:109-118
Finke DA, Ligetti CB, Traband MT, Roy A (2007) Shipyard space allocation and scheduling. J Ship Prod 23:197-201
Finke DA, Ligetti CB, Traband MT, Roy A (2008) Activity-based spatial scheduling. J Ship Prod 24:12-16
Cho K, Chung K, Park C, Park J, Kim H (2001) A spatial scheduling system for block painting process in shipbuilding. CIRP Ann Manuf Technol 50:339-342
Shin JG, Kwon OH, Ryu C (2008) Heuristic and metaheuristic spatial planning of assembly blocks with process schedules in an assembly shop using differential evolution. Prod Plan Control 19:605-615
Martello S, Pisinger D, Vigo D (2000) The three dimensional bin packing problem. Oper Res 48:256-267
Wu Y, Li W, Goh M, de Souza R (2010) Three-dimensional bin packing problem with variable bin height. Eur J Oper Res 202:347-355
Lee JK, Lee KJ, Park HK, Hong JS, Lee JS (1997) Developing scheduling systems for Daewoo Shipbuilding: DAS project. Eur J Oper Res 97(2):380-395
Lim A, Rodrigues B, Yang Y (2005) 3-D container packing heuristics. Appl Intell 22:125-134
Lodi A, Martello S, Vigo D (2002) Heuristic algorithms for the three-dimensional bin packing problem. Eur J Oper Res 141:410-420
Garey MR, Johnson DS (1990) Computers and intractability; a guide to the theory of NP-completeness. W. H. Freeman & Co, LinkedIn
Brunetta L, Gregoire P (2005) A general purpose algorithm for three-dimensional packing. INFORMS J Comput 17:328-338
Faroe O, Pisinger D, Zachariasen M (2003) Guided local search for the three-dimensional bin-packing problem. INFORMS J Comput 15:267-283
Martello S, Pisinger D, Vigo D, Boef ED, Korst J (2007) Algorithm 864: general and robot package variants of the three-dimensional bin packing problem. ACM Trans Math Softw 33:1-12
Langer Y, Bay M, Crama Y, Bair F, Caprace J, Rigo P (2005) Optimization of surface utilization using heuristic approaches. COMPIT'05 - the 4th international conference on computer applications and information technology in the maritime industries, May, vol 1, hamburg, pp 419-425.
Bay M, Crama Y, Langer Y, Rigo P (2010) Space and time allocation in a shipyard assembly hall. Ann Oper Res 179:57-76