This thesis considers a scheduling problem arising in a shipyard block assembly process. Given a set of blocks and a set of shops, the block schedule assigns each job to a shop and determines when the job will be started while satisfying the precedence and time window constraints. The precedence constraints restrict that the starting time of each job should be earlier than those of its successors. The time window constraints limit the starting time of the jobs to be assigned between their Earliest Starting Dates (ESD) and Latest Starting Dates (LSD). Resource leveling is the primary objective of the block scheduling problem. To attack this problem, we propose a heuristic algorithm, which is based on a decomposition of the problem into two sub-problems: leveling between periods, and leveling between shops. The first part of the algorithm adjusts the starting time of the jobs in each shop, using three types of operations: left hand moving operation, right hand moving operation, and exchange operation. The second part changes shop assignments of some jobs and re-levels. The algorithm combines these two subroutines appropriately so that the resource requirements at various shops could be balanced in each production planning periods. Computational result using a real world data is reported.
