Spatial scheduling for large assembly blocks in shipbuilding

• Development of a novel MIP model considering various tough constraints in practice.
• Development of space allocation method for spatial scheduling.
• Development of hierarchical heuristic algorithms with computational capability.
• Performance comparison between the MIP model and the heuristic.
• Robust computational times by the proposed algorithm with regard to the problem size.

This paper addresses the spatial scheduling problem (SPP) for large assembly blocks, which arises in a shipyard assembly shop. The spatial scheduling problem is to schedule a set of jobs, of which each requires its physical space in a restricted space. This problem is complicated because both the scheduling of assemblies with different due dates and earliest starting times and the spatial allocation of blocks with different sizes and loads must be considered simultaneously. This problem under consideration aims to the minimization of both the makespan and the load balance and includes various real-world constraints, which includes the possible directional rotation of blocks, the existence of symmetric blocks, and the assignment of some blocks to designated workplaces or work teams. The problem is formulated as a mixed integer programming (MIP) model and solved by a commercially available solver. A two-stage heuristic algorithm has been developed to use dispatching priority rules and a diagonal fill space allocation method, which is a modification of bottom-left-fill space allocation method. The comparison and computational results shows the proposed MIP model accommodates various constraints and the proposed heuristic algorithm solves the spatial scheduling problems effectively and efficiently.