This paper deal with the block storage planning problem of storing and retrieving assembly blocks in a temporary storage yard with limited capacity, which is one of the critical managerial problems in shipbuilding. The block storage planning problem is required to minimize the number of relocations of blocks while the constraints for storage and retrieval time windows are satisfied. We first show NP-hardness of the block storage planning problem. Next we propose a heuristic algorithm to generate good quality solutions for larger instances in very short computational time. The proposed heuristic algorithm was validated by comparing the results with the mathematical model presented in the previous study.