# A Branch and Bound Algorithm for Project Scheduling Problem with Spatial Resource Constraints

Authors: Shicheng Hu; Song Wang; Yonggui Kao; Takao Ito; Xuedong Sun
Journal: Mathematical Problems in Engineering
 (2015)

---

## Abstract

With respect to the block assembly schedule in a shipbuilding enterprise, a spatial resource constrained project scheduling problem (SRCPSP) is proposed, which aims to minimize the makespan of a project under the constraints of the availability of a two-dimensional spatial resource and the precedence relationship between tasks. In order to solve SRCPSP to the optimum, a branch and bound algorithm (BB) is developed. For the BB-SRCPSP, first, an implicitly enumerative branch scheme is presented. Secondly, a precedence based lower bound, as well as an effective dominance rule, is employed for pruning. Next, a heuristic based algorithm is used to decide the order of a node to be selected for expansion such that the efficiency of the algorithm is further improved. In addition, a maximal space based arrangement is applied to the configuration of the areas required each day in an available area. Finally, the simulation experiment is conducted to illustrate the effectiveness of the BB-SRCPSP.


---

## Body

## 1. Introduction

RCPSP [1] (resource constrained project scheduling problem) is originated from the techniques of CPM (critical path method) and PERT (project evaluation and review technique). Soon after the integer programming model of the RCPSP is proposed, it was proved to be a NP-hard problem. Due to the wide existence of the two conditions in practice, that is, precedence relationship between tasks and resource availability, the RCPSP, which employs these two conditions as hard constraints, has been the hot research topic so far. As the core classical problem in project scheduling, sufficient achievements have been acquired on its algorithms, models, and applications.The algorithms on RCPSP are classified into two categories, optimal algorithm and approximate algorithm, which produce optimal solution and nearly optimal solution, respectively. Branch and bound algorithm [2] is the most used optimal algorithm, which gets the optimal solution with the cost of time-consuming. For the improvement of efficiency, more efforts are paid to the theory of lower bound, which can avoid large amounts of unnecessary searches. The approximate algorithms are divided into heuristic, metaheuristic, and hybrid heuristic [3]. The heuristic is the mostly employed algorithm to RCPSP, which starts from a partial feasible solution to construct a complete feasible solution. A heuristic contains two parts, priority rule and schedule generation scheme. The metaheuristic often constructs a feasible solution by the use of a heuristic and then improves it to a nearly optimal solution. The classical metaheuristics include simulated annealing [4], tabu search [5], genetic algorithm [6], neural network [7], immune algorithm [8], ant colony [9], and particle swarm [10]. Recently, more and more efforts are involved in the research of hybrid heuristic [11] and satisfactory results have been achieved. The hybrid heuristic is one of the most potential researches in the future.To satisfy the needs of real applications, different variations are derived from the classical RCPSP: the strict precedence relationship between tasks was extended to a more general precedence relationship [12]; a new type of nonrenewable resource was introduced [13]; the resource usage can have more than one mode [14]; in addition to project makespan, the objective included project cost [15], net present value [16], resource leveling [17], resource investment [18], time-dependent cost [19–21], and position-dependent cost [22, 23]. The combinations of different constraints and objectives can produce different resource scheduling model with different background. Meanwhile, the different resource scheduling models were developed from deterministic ones to probabilistic ones so as to cope with different risks and uncertainties in applications.Lee was the first to study the spatial resource scheduling problem [24]. He employed Lozano-Perez’s two-dimensional arrangement algorithm to solve the problem of how to arrange the nonregular polygons in a rectangle. Lee applied this method to the curved-bottom block assembly scheduling and further to the flat-bottom block assembly scheduling. Also, several other different solution schemes were also proposed to this problem. Afterwards, the ship painting spatial resource scheduling problem was proposed [25]. Next, the ship block erecting spatial resource scheduling problem was studied [26]. Furthermore, the ship megablock assembly spatial resource scheduling problem was tackled [27]. In other application fields, an operation system for reconfigurable embedded platforms was developed [28] and a bin packing problem with the constraint of precedence relationship was presented [29].In this paper, a spatial resource constrained project scheduling problem is modeled and a corresponding branch and bound algorithm is developed. This paper is organized as follows: in Section2, a conceptual model is proposed; in Section 3 the branch and bound method is described; a demonstrative simulation example is presented in Section 4; and the summary conclusion is provided in the final section.


## 2. Spatial Resource Constrained Project Scheduling Problem (SRCPSP)

For ship manufacturing enterprises, spatial resource scheduling is a representative problem in the shipbuilding project management. Here, the ship block assembly project is used as an example to illustrate it. A block is a cubic module with different shape and volume that is divided from a ship in the design stage (a large ship is generally divided into hundreds of blocks), which is the most important intermediate product in a ship building. All blocks will be assembled together to form a ship according to the precedence relationship between them. The assembly of blocks is operated on a platform, which is a two-dimensional area equipped with jigs. Since for a shipbuilding enterprise, the platform is an expensive and scare resource, whose utility efficiency has a direct impact on the makespan of a ship. The optimization of the platform configuration is the key problem to be solved in a ship block assembly project scheduling. The platform scheduling is how to arrange the start time of each task such that the makespan of a ship block assembly project is minimized under the constraints of the precedence relationship between block assembly tasks and the availability of platform resource. In a ship building enterprise, except for the assembly of blocks, the painting of blocks, the general assembly of blocks, and the erecting of blocks into a final ship are also operated on different types of platforms, which are also expensive and scare resources in an enterprise. Therefore, for the different production project plans, the spatial resource scheduling is a key problem for a manufacturing enterprise to solve. The spatial resource constrained project scheduling problem (SRCPSP) can be expressed as follows:(1)minimizeSn+1(2)Si+di≤Sj,∀i∈Pj(3)aik∩ajk=ϕ,∀i,j∈N,∀k∈M(4)0≤wik≤Wk,∀i∈N,∀k∈M(5)0≤lik≤Lk,∀i∈N,∀k∈M(6)δi∈0,1,∀i∈N.A SRCPSP has a set of tasks,N={0,1,…,n,n+1}. Each task i has a requirement aik=wik×lik for spatial resourcek, where wik and lik denote the width and length of a two-dimensional area aik, respectively. And each task i will be completed in a period of di. The resource requirements and durations for the dummy start and end tasks 0 and n+1 are 0. There are a set of spatial resources, M={1,…,m}, each of which has a availability Ak=Wk×Lk, where Wk and Lk denote the width and length of a two-dimensional area Ak, respectively. Formula (2) represents the precedence relationship between tasks, which means that a task j cannot start before any of its predecessors Pj. Formulae (2)–(5) present the spatial resource constraint; they define that for each day, the spatial resource requirements aik and ajk for any two tasks i andj which have the same type of resource k cannot overlap (see (3)) and the width wik and length lik of spatial resource requirements aik for any tasks i should be confined in the corresponding dimensions Wk and Lk of the available spatial resource Ak (see (4) and (5)). In order to produce a better optimal solution, the 90-degree-based rotation of the required area is permitted. Formula (6) denotes two orientations for each required area aik; δi=0 indicating that the width of aik is parallel to the width of Ak and δi=1 indicating that the length of aik is parallel to the width of Ak. The objective of SRCPSP is to minimize the makespan Sn+1 (see (1)).


## 3. A Branch and Bound Algorithm for SRCPSP (BB-SRCPSP)

A branch and bound algorithm includes branch scheme and bound computation. For the branch and bound algorithm to SRCPSP, the arrangement of a spatial areaaik required by a task i in the available area Ak should also be specified. This section will tackle these three problems involved in the branch and bound algorithm for SRCPSP (BB-SRCPSP).


### 3.1. Branch Scheme

The branching scheme involves how to develop the nodes of a tree from one root node. Each node in a tree represents a partial schedule, and the root node represents one in which only the start task 0 is schedule at time zero. Related to each decision timet, there are four sets of tasks, the partial schedule Qt in which each task is assigned a start time, the active schedule St in which each task is being processed but not completed, the complete schedule Ct in which each task is finished, and a decision set Dt in which the predecessors of each task are in Ct such that it could be selected as the next task to be scheduled.For the nodes that are expanded from an ancestor, they have the same decisions made previously, which means that except for the current tasks that are scheduled, the tasks that are scheduled previously have the same start time. Given a node, the production of its braches can be described as follows: at a decision timep, there are four sets of tasks, Qt, St, Ct, and Dt, related to a nodeb, which will produce several descendants at next timeq, each corresponding to a branch. We will select the complete time of the first task in St which has the earliest finish time as the next decision time q. Then we will decide the alternatives from Dt, each of which should satisfy the resource constraints. An alternative may be any task in Dt or a combination of the tasks in Dt that could be scheduled at timeq.A demonstrative example is shown on how to branch a node. Figure1 is the Gantt chart of a partial schedule: p=0, Qp={0,1,2}, Sp={1,2}, Cp={0}, and Dp={3,4,5}. Assume that the availability of the only one type of resource R=4 and the resource requirements r3, r4, and r5 of tasks 3, 4, and 5 are 1, 2, and 4, respectively. According to the tree creation process described above, the next decision time is the completion time of task 2; q=2. At time q, the alternative set Aq={{3},{4},{3,4}} since the requirement of each alternative in Aq is no more than the resource availability at time q. So from the node corresponding to partial schedule Qp={0,1,2} at timep, three branches will be produced, which correspond to three partial schedules at timeq, Qq1={0,1,2,3}, Qq2={0,1,2,4}, and Qq3={0,1,2,3,4}. As is indicated above, the three branches have a common partial schedule shown in Figure 1, Qp={0,1,2}. The current scheduled tasks at time q of the three descendant partial schedules are the only difference between them. The produced branches are shown in Figure 2.Figure 1
The Gantt chart of a partial schedule at timep.Figure 2
The produced branches from a partial schedule at timeq.


### 3.2. Bound Computation

The tree will have an exhaustive enumeration if no pruning is introduced and the branch and bound algorithm will be very time-consuming. In order to improve the efficiency of BB-SRCPSP, we design some pruning strategies.The lower bound based pruning is the most effective method that is employed in the literatures. A lower bound is a predicted value on the makespan of a partial schedule,LB(Qt). An upper bound is always set as the makespan of the incumbent optimal solution, UB. If LB(Qt)≥UB, it can be deduced that from the partial schedule Qt, a better optimal solution than the incumbent will never be produced and then the corresponding node should be pruned; that is, it is unnecessary to create branches from this node. The lower bound value will be computed once a new partial schedule is produced and the incumbent upper bound will be updated if a better optimal solution is found.For BB-SRCPSP, we compute the precedence based lower boundPLB(Qt). Given a partial schedule Qt, assuming the set of tasks that are scheduled at time t to beH, the PLB(Qt) can be computed as follows: (7)PLB=max⁡t+di+CPLj∣i∈H,j∈Si,where CPL(j) is the critical path length from node j to the end node n+1 of a project and S(i) is the set of immediate successors of nodei.Given a partial scheduleQ, if some tasks can be left-shifted without violating either the resource or precedence constraints, this partial schedule will be dominated. This is a very effective dominance rule that is used for pruning. A demonstrative example is given on how this dominance rule works. Emanating from a root node is three branches nodes 2, 3, and 4, shown in Figure 3. One of the descendants of node 1 is node 5, which corresponds to the partial schedule shown in Figure 4. Note that the task 2 in Figure 4 could be left-shifted by 3 time units without violating any constraint, so this partial schedule would be dominated and the corresponding node 5 in the tree should be pruned.Figure 3
The three branches emanated from the root node.Figure 4
The Gantt chart of a partial schedule corresponding to node 5.It is known that the order of the same node in the tree chosen to be expanded has a great impact on whether or when it will be pruned and thus on the efficiency of a BB algorithm. The node in the tree which has the largest lower bound will be selected for expansion. Then an arbitrary node will be selected to break the ties if more than one candidate tasks exist.


### 3.3. Arrangement of a Spatial Area

For a traditional RCPSP, the resource constraint requires that the sum of the quantities of the resource demands of the tasks on each day is no larger than the quantity of the same type resource availability. But for a SRCPSP, the satisfaction of the resource constraint means that in addition to that for a RCPSP, the precise position of an area required by a task should also be specified in an available area. The configuration of an area is a very complicated problem. In order to get a better optimal solution, the area available on each day should be filled more efficiently; alternatively speaking, the configuration of an area will impact the quality of a solution.The configuration of an area is a two-dimensional packing problem. So far, many methods have been presented to tackle it, among which the maximal space-based algorithm is proved to be very effective and is employed in our BB-SRCPSP. Each time if there would be more than one maximal space produced, the one with the smallest distance to a corner of the available area will be chosen as the one to be filled and the corner of the selected maximal space with the least distance to a corner of the available area will be chosen as the position that a task will be put on.To illustrate how the maximal space is produced, the reader is referred to Figure5. Initially, the left-bottom corner of area 1 is used to put an area and then two maximal spaces are produced, areas 2 and 3. Afterwards, the area 2 is selected and three maximal spaces are generated, areas 4, 5, and 6.Figure 5
The production of maximal spaces.


## 3.1. Branch Scheme

The branching scheme involves how to develop the nodes of a tree from one root node. Each node in a tree represents a partial schedule, and the root node represents one in which only the start task 0 is schedule at time zero. Related to each decision timet, there are four sets of tasks, the partial schedule Qt in which each task is assigned a start time, the active schedule St in which each task is being processed but not completed, the complete schedule Ct in which each task is finished, and a decision set Dt in which the predecessors of each task are in Ct such that it could be selected as the next task to be scheduled.For the nodes that are expanded from an ancestor, they have the same decisions made previously, which means that except for the current tasks that are scheduled, the tasks that are scheduled previously have the same start time. Given a node, the production of its braches can be described as follows: at a decision timep, there are four sets of tasks, Qt, St, Ct, and Dt, related to a nodeb, which will produce several descendants at next timeq, each corresponding to a branch. We will select the complete time of the first task in St which has the earliest finish time as the next decision time q. Then we will decide the alternatives from Dt, each of which should satisfy the resource constraints. An alternative may be any task in Dt or a combination of the tasks in Dt that could be scheduled at timeq.A demonstrative example is shown on how to branch a node. Figure1 is the Gantt chart of a partial schedule: p=0, Qp={0,1,2}, Sp={1,2}, Cp={0}, and Dp={3,4,5}. Assume that the availability of the only one type of resource R=4 and the resource requirements r3, r4, and r5 of tasks 3, 4, and 5 are 1, 2, and 4, respectively. According to the tree creation process described above, the next decision time is the completion time of task 2; q=2. At time q, the alternative set Aq={{3},{4},{3,4}} since the requirement of each alternative in Aq is no more than the resource availability at time q. So from the node corresponding to partial schedule Qp={0,1,2} at timep, three branches will be produced, which correspond to three partial schedules at timeq, Qq1={0,1,2,3}, Qq2={0,1,2,4}, and Qq3={0,1,2,3,4}. As is indicated above, the three branches have a common partial schedule shown in Figure 1, Qp={0,1,2}. The current scheduled tasks at time q of the three descendant partial schedules are the only difference between them. The produced branches are shown in Figure 2.Figure 1
The Gantt chart of a partial schedule at timep.Figure 2
The produced branches from a partial schedule at timeq.


## 3.2. Bound Computation

The tree will have an exhaustive enumeration if no pruning is introduced and the branch and bound algorithm will be very time-consuming. In order to improve the efficiency of BB-SRCPSP, we design some pruning strategies.The lower bound based pruning is the most effective method that is employed in the literatures. A lower bound is a predicted value on the makespan of a partial schedule,LB(Qt). An upper bound is always set as the makespan of the incumbent optimal solution, UB. If LB(Qt)≥UB, it can be deduced that from the partial schedule Qt, a better optimal solution than the incumbent will never be produced and then the corresponding node should be pruned; that is, it is unnecessary to create branches from this node. The lower bound value will be computed once a new partial schedule is produced and the incumbent upper bound will be updated if a better optimal solution is found.For BB-SRCPSP, we compute the precedence based lower boundPLB(Qt). Given a partial schedule Qt, assuming the set of tasks that are scheduled at time t to beH, the PLB(Qt) can be computed as follows: (7)PLB=max⁡t+di+CPLj∣i∈H,j∈Si,where CPL(j) is the critical path length from node j to the end node n+1 of a project and S(i) is the set of immediate successors of nodei.Given a partial scheduleQ, if some tasks can be left-shifted without violating either the resource or precedence constraints, this partial schedule will be dominated. This is a very effective dominance rule that is used for pruning. A demonstrative example is given on how this dominance rule works. Emanating from a root node is three branches nodes 2, 3, and 4, shown in Figure 3. One of the descendants of node 1 is node 5, which corresponds to the partial schedule shown in Figure 4. Note that the task 2 in Figure 4 could be left-shifted by 3 time units without violating any constraint, so this partial schedule would be dominated and the corresponding node 5 in the tree should be pruned.Figure 3
The three branches emanated from the root node.Figure 4
The Gantt chart of a partial schedule corresponding to node 5.It is known that the order of the same node in the tree chosen to be expanded has a great impact on whether or when it will be pruned and thus on the efficiency of a BB algorithm. The node in the tree which has the largest lower bound will be selected for expansion. Then an arbitrary node will be selected to break the ties if more than one candidate tasks exist.


## 3.3. Arrangement of a Spatial Area

For a traditional RCPSP, the resource constraint requires that the sum of the quantities of the resource demands of the tasks on each day is no larger than the quantity of the same type resource availability. But for a SRCPSP, the satisfaction of the resource constraint means that in addition to that for a RCPSP, the precise position of an area required by a task should also be specified in an available area. The configuration of an area is a very complicated problem. In order to get a better optimal solution, the area available on each day should be filled more efficiently; alternatively speaking, the configuration of an area will impact the quality of a solution.The configuration of an area is a two-dimensional packing problem. So far, many methods have been presented to tackle it, among which the maximal space-based algorithm is proved to be very effective and is employed in our BB-SRCPSP. Each time if there would be more than one maximal space produced, the one with the smallest distance to a corner of the available area will be chosen as the one to be filled and the corner of the selected maximal space with the least distance to a corner of the available area will be chosen as the position that a task will be put on.To illustrate how the maximal space is produced, the reader is referred to Figure5. Initially, the left-bottom corner of area 1 is used to put an area and then two maximal spaces are produced, areas 2 and 3. Afterwards, the area 2 is selected and three maximal spaces are generated, areas 4, 5, and 6.Figure 5
The production of maximal spaces.


## 4. Simulation Experiment

In this section, a set of simulated data is used to illustrate the proposed branch and bound algorithm for SRCPSP, which is adapted from the well-known PSPLIB [30]. The instance includes 9 tasks; the precedence relationship between tasks is shown in Figure 6. There are two types of spatial resources, whose availability is 4×3 square units. The parameters for each task are listed in Table 1.Table 1
The parameters of tasks.
Task number
Duration
Length, width
Area type
1
0
0, 0
2
6
3, 1
1
3
2
3, 2
2
4
3
2, 1
1
5
7
2, 2
2
6
2
2, 2
1
7
7
3, 1
2
8
4
3, 2
1
9
0
0, 0Figure 6
The precedence relationships between tasks.At timet=0, Qt={1}, St=Φ, Ct={1}, and Dt={2,3,4}. 7 nodes numbered 2, 3, 4, 5, 6, 7, and 8 are created as shown in Figure 7 and the corresponding partial schedules are illustrated in Figures 8, 9, 10, 11, 12, 13, and 14.Figure 7
The search tree.Figure 8
The partial schedule corresponding to node 2.Figure 9
The partial schedule corresponding to node 3.Figure 10
The partial schedule corresponding to node 4.Figure 11
The partial schedule corresponding to node 5.Figure 12
The partial schedule corresponding to node 6.Figure 13
The partial schedule corresponding to node 7.Figure 14
The partial schedule corresponding to node 8.The lower bounds,LB(Qt), for nodes 2, 5, 6, and 8, are equal to 13, respectively. So node 6 is selected arbitrarily for expansion.From node 6,t=3, Qt={1,2,4}, St={2}, Ct={1,4}, and Dt={3,8}. 3 nodes numbered 9, 10, and 11 are created as shown in Figure 7 and the corresponding partial schedules are illustrated in Figures 15, 16, and 17.Figure 15
The partial schedule corresponding to node 9.Figure 16
The partial schedule corresponding to node 10.Figure 17
The partial schedule corresponding to node 11.The lower bounds,LB(Qt), for nodes 2, 5, 8, 9, 10, and 11, are equal to 13, respectively. So node 10 is selected arbitrarily for expansion.From node 10,t=6, Qt={1,2,4,8}, St={6}, Ct={1,2,4}, and Dt={3,7}. 3 nodes numbered 12, 13, and 14 are created as shown in Figure 7 and the corresponding partial schedules are illustrated in Figures 18, 19, and 20.Figure 18
The partial schedule corresponding to node 12.Figure 19
The partial schedule corresponding to node 13.Figure 20
The partial schedule corresponding to node 14.The lower bounds,LB(Qt), for nodes 2, 5, 8, 9, 11, 12, 13, and 14, are equal to 13, respectively. So node 14 is selected arbitrarily for expansion.From node 14,t=7, Qt={1,2,4,8,3,7}, St={3,7}, Ct={1,2,4,8}, and Dt=Φ. Then t=8, Qt={1,2,4,8,3,7}, St={7}, Ct={1,2,4,8,3}, and Dt={5}. 1 node numbered 15 is created as shown in Figure 7 and the corresponding partial schedule is illustrated in Figure 21.Figure 21
The partial schedule corresponding to node 15.The lower bounds,LB(Qt), for nodes 2, 5, 8, 9, 11, 12, 13, and 15, are equal to 13, respectively. So node 15 is selected arbitrarily for expansion.From node 15,t=13, Qt={1,2,4,8,3,7,5}, St={5}, Ct={1,2,4,8,3,7}, and Dt=Φ. Then t=15, Qt={1,2,4,8,3,7,5}, St=Φ, Ct={1,2,4,8,3,7,5}, and Dt={6}. 1 node numbered 16 is created as shown in Figure 7 and the corresponding partial schedule is illustrated in Figure 22.Figure 22
The partial schedule corresponding to node 16.The lower bounds,LB(Qt), for nodes 2, 5, 8, 9, 11, 12, 13, and 16, are equal to 13, respectively. So node 16 is selected arbitrarily for expansion.From node 16,t=17, Qt={1,2,4,8,3,7,5,6}, St=Φ, Ct={1,2,4,8,3,7,5,6}, and Dt={9}. 1 node numbered 17 is created as shown in Figure 7 and the corresponding partial schedule is illustrated in Figure 23. As Qt=9, then an optimal schedule is produced, UB=17.Figure 23
The partial schedule corresponding to node 17.The lower bounds,LB(Qt), for nodes 2, 9, 12, and 13, are equal to 13, respectively. So node 13 is selected arbitrarily for expansion.From node 13,t=7, Qt={1,2,4,8,7}, St={7}, Ct={1,2,4,8}, and Dt={3}. 1 node numbered 18 is created as shown in Figure 7 and the corresponding partial schedule is illustrated in Figure 24.Figure 24
The partial schedule corresponding to node 18.For the partial schedule corresponding to node 18, the task 3 can left-shift to 0 without violating the constraints, so this partial schedule is dominated and the node 18 is pruned. The dominance rule is also applied to nodes 9 and 12, and the descendants of nodes 2, 3, 4, 5, and 7, as shown in Figure7.The same algorithm process is implemented to node 8 and another optimal schedule is produced as shown in Figure25. The descendants expanded from node 8 are illustrated in Figure 7. As it is better than the previous one shown in Figure 23, it is the best solution for the instance.Figure 25
The partial schedule corresponding to node 23.


## 5. Conclusion

For the spatial resource scheduling problem, a sophisticated branch and bound algorithm is developed to achieve the optimal solution. The branching is an implicit enumeration based scheme and the lower bound is computed based on the critical path of a network. In order to improve the efficiency of BB-SRCPSP, an effective dominance rule is employed and a heuristic based node selection is adopted. For the optimization of the area arrangement, the maximal space based algorithm is applied. The proposed BB-SRCPSP is the first to solve a spatial resource scheduling problem to its optimal solution and thus is a guideline for the design of a more efficient branch and bound algorithm in this field.



---

*Source: 628259-2015-10-25.xml*