Spatial scheduling for shape-changing mega-blocks in a shipbuilding company

To overcome space restriction and to increase productivity, some shipbuilding companies use floating-docks on the sea instead of dry-docks on the land. In that case, a floating-crane that is capable of lifting very heavy objects (up to 3600?tons) is used to handle the blocks which are the basic units in shipbuilding processes, and therefore, very large blocks (also called mega-blocks) can be used to build a ship, but because there are some positional restrictions under which the mega-block assembly yard can be constructed, the space is the scarcest resource in the process. The focus of the research reported in this paper is to develop an efficient spatial schedule for the mega-block assembly yard. First, we develop a length-time two-dimensional packing model for this problem. Since the optimisation model cannot be solved using an analytical method, we propose a GA-based heuristic algorithm using computational geometry theory. Through performing a series of computational experiments, we finally show that the proposed spatial scheduling algorithm can provide solutions of good quality very efficiently.