This thesis considers a scheduling problem on a shipyard block assembly process. Given a set of blocks and a set of bays, the block scheduler assigns each job to a bay and determines when the job will be started while satisfying the precedence constraints, the time window constraints and the resource constraints. The precedence constraints make each job precedes its successors. The time window constraints limit the starting times of the jobs to be assigned between their Earliest Starting Day (ESD) and Schedule Starting day (SSD). We mainly consider two types of resources for each bay: space resource, manpower resource. During the process, each job requires a space resource and a manpower resource. The resource constraints prevent each bay from being overloaded. Balancing the manpower resource is the primary objective of our problem.
To solve this problem, an algorithm based on CSP (Constraints Satisfaction Problems) techniques is proposed. To use the CSP techniques, we first model the problem with linear and nonlinear constraints, integer variables and the feasible domain of each variable. Then we use a tree-search based algorithm. This algorithm was tested on two data sets from real world problem.
