Heuristic Algorithms for Assigning Ship Assembly Blocks to Storage Locations at a Shipyard

Abstract

We consider the problem of assigning ship assembly blocks to storage locations at a ship yard while allowing one-way movement of the blocks. The objective is to minimize the number of blocks obstructing other blocks’ movements. We show that the integer program in a previous study contains errors in identifying obstructive blocks and therefore, suggest another integer program without the error. Also, we suggest construction heuristics and a tabu search algorithm using properties characterizing optimal solutions of subproblems. Computational experiment results indicate that our heuristics outperform the existing algorithm in terms of solution quality.