A planning problem that determines the product mix and construction schedule for a large shipyard is discussed. The objectives are to achieve the annual sales target and to smooth the workloads over time. A number of technological and resource constraints, including dock space restrictions, should be satisfied. The complicated decision problem is decomposed into several subproblems and search-based heuristic algorithms for the subproblems are developed. Experimental results are reported.