Document [original]

A Branch-and-Price Algorithm for Multi-Mode

Resource Leveling

Eamonn T. Coughlan1, Marco E. L¨ubbecke2, and Jens Schulz1

1Technische Universit¨at Berlin, Institut f¨ur Mathematik, Straße d. 17. Juni 136,

10623 Berlin, Germany, {coughlan,jschulz}@math.tu-berlin.de

2Technische Universit¨at Darmstadt, Fachbereich Mathematik, Dolivostr. 15,

64293 Darmstadt, Germany, [email protected]

Abstract Resource leveling is a variant of resource-constrained project

scheduling in which a non-regular objective function, the resource avail-

ability cost, is to be minimized. We present a branch-and-price approach

together with a new heuristic to solve the more general turnaround

scheduling problem. Besides precedence and resource constraints, also

availability periods and multiple modes per job have to be taken into ac-

count. Time-indexed mixed integer programming formulations for similar

problems quite often fail already on instances with only 30 jobs, depend-

ing on the network complexity and the total freedom of arranging jobs. A

reason is the typically very weak linear programming relaxation. In par-

ticular for larger instances, our approach gives tighter bounds, enabling

us to optimally solve instances with 50 multi-mode jobs.

1 Introduction

Motivated by an industrial application from chemical engineering, we study a

resource leveling problem, which was recently introduced as turnaround schedul-

ing problem [MMS09]. In turnaround scheduling, for inspection and renewal of

parts, plants are shut down, disassembled, and rebuilt, so there is a partial or-

dering of jobs to be done. The time horizon and the number of workers hired

for each job determine production downtime and working cost, the two of which

are conflicting in a time-cost tradeoff manner. Once a time horizon is fixed, the

problem turns into a resource leveling problem, on which we focus in this paper.

Different types of renewable resources are given, each associated with avail-

ability periods which can be thought of as working shifts. Besides the actual

scheduling of jobs, the task is to decide how many workers need to be assigned

to each job such that working costs are minimized, that is, we must determine a

minimum amount of resources needed. We break down the granularity of plan-

ning, so that each job needs exactly one resource, possibly several units of which.

Heuristics, rather than exact methods, are prominent for solving such com-

plex scheduling problems. This is also due to the fact that mixed integer program-

ming formulations for scheduling problems in general, and for ours in particular,

often yield very weak bounds from the linear programming relaxation.

2 Eamonn T. Coughlan, Marco E. L¨ubbecke, and Jens Schulz

Our Contribution. We approach the turnaround scheduling from both ends.

Besides presenting a heuristic which improves on the results reported in [MMS09],

we formulate a mixed integer program which is based on working shifts, and thus

has an exponential number of variables. A branch-and-price algorithm to solve

this model computes optimal schedules for instances with up to 50 jobs, which is

a large number in this area of scheduling. In particular the derived lower bounds

demonstrate that our heuristic solutions are mostly near the optimum or at least

near the best solution found by exact methods within half an hour.

2 Formal Problem Description

For a recent survey on resource-constrained project scheduling (RCPSP) we

refer to [HB09]. We are given a set Jof non-preemptable jobs and a set Rof

renewable resources. Precedence constraints between jobs are given as an acyclic

digraph G= (J, E) with ij ∈Eiff job ihas to be finished before job jstarts.

Each job jmay be run in exactly one out of a set Mjof modes. Processing job j

in mode m∈ Mjtakes pjm time units and requires rjmk units of resource k∈ R.

Due to a fine granularity of planning, in our setting each job needs exactly one

resource for execution, so we write rjm if the resource is clear from the context.

All jobs have to finish before T, the time horizon. Each resource k∈ R has a

set Ik:= {[a1, b1],...,[aki, bki]}of ki∈Navailability periods, also called shifts,

where a1< b1< . . . < aki< bki. A job requiring resource kcan only be executed

during a time interval I∈ Ik. We use a parameter δkt which is one if resource k

is available at time t, i.e., t∈Ifor some I∈ Ik, and zero otherwise. Each

resource k∈ R is associated with a per unit cost ck. For each resource kwe have

to determine the available capacity Rksuch that at any time the total resource

requirement of all the jobs does not exceed Rk.

We denote by S= (S1, .. . , Sn) the vector of start times of jobs, and by M=

(m1, . . . , mn) the vector of modes in which jobs are executed. For a given sched-

ule (S, M), denote by A(S, M, t) := j∈ J :Sj≤t<Sj+pjmjthe set of

jobs active at time t. The amount rk(S, M, t) := Pj∈A(S,M,t)rjmjkof resource k

used at time tmust never exceed the provided capacity. Thus, we obtain re-

source constraints with calendars: rk(S, M, t)≤Rk·δkt,∀k∈ R,∀t. Besides

this resource feasibility a feasible schedule must obey precedence feasibility, i.e.,

Si+pimi≤Sjfor all ij ∈E. The objective of the resource leveling problem is

to minimize the resource availability costs Pk∈R ck·Rk.

Following the extended α|β|γ-classification scheme [BDM+99], we consider

MPSm, ∞|prec, shifts|Pck·max rk(S, M, t) for multi-mode project scheduling

with mrenewable resources of unbounded capacity, with precedence constraints

and working shifts, with the objective to minimize the resource availability cost.

Related Work. Turnaround scheduling comprises project scheduling with cal-

endars, multi-mode scheduling, and resource leveling; see [MMS09] for an in-

dustrial application. The zoo of scheduling problems is large, and we give an

idea only of the most related problems. Makespan minimization is a classical

A Branch-and-Price Algorithm for Multi-Mode Resource Leveling 3

scheduling goal. In contrast to this regular objective function, i.e., being non-

decreasing in the completion time of the jobs, a measure of the variation of

resource utilization, e.g., f(rk(S, t)) is not regular; see e.g., [NSZ03].

The resource leveling problem with single-modes per job, which is denoted

by PS|temp|Pckmax rk(S, t) with general temporal constraints has been con-

sidered earlier under the name resource investment problem. The special case

without generalized precedence constraints PS|prec|Pckmax rk(S, t) has been

considered e.g., by [Dem95] and [M¨oh84]. They competed on the same instance

set which contained about 16 jobs and four resources, with a time horizon be-

tween 47 and 70. Further computational studies were done containing 15 to 20

jobs and four resources. In the same setting, [DK01] propose lower bound com-

putations, one based on Lagrangean relaxation, and one based on a column

generation procedure, where variables represent schedules as in our approach.

Small job sizes with 20 jobs can be handled; but for 30 jobs the Lagrangean

relaxation wins against the column generation approach.

Multi-mode (also known as malleable) jobs are a key feature of turnaround

scheduling. Such problems of the form MPS|prec|Cmax have been investigated

with renewable and non-renewable resources, with limited capacity, and makespan

minimization, known as multi-mode RCPSP, see e.g., [DH02,Har01].

For benchmarking, different problem sets are available in the PSPLib [PSP],

where several variants of the RCPSP and of resource investment problems can

be found. For the RCPSP single-mode case, test sets containing 60 jobs could

not be solved in total by a vast number of researchers. In the multi-mode case

instances with 30 jobs are not solved yet. For the resource investment problem,

test sets containing 10, 20, or 30 jobs are available, but they do not contain

working shifts, are in single-mode and include time-lags. On the other hand

a job may need more than one resource. Even though none of these problems

is suited for a direct comparison, they are similar to ours, and the mentioned

instances inspired us when generating our own test set (see Sect. 5).

Algorithms have also taken calendars into account. Scheduling problems with

fixed processing times and calendars, but without resource capacities were con-

sidered by [Zha92] who provides an exact pseudo-polynomial time algorithm

(turned into a polynomial one by [FNS01]) for computing earliest and latest

start times for preemptable as well as non-preemptable jobs.

3 Integer Programming Formulations

For solving large-scale scheduling problems, mixed integer programming (MIP) is

not considered as primary choice since the linear programming (LP) relaxations

may be weak. Huge numbers of variables and constraints may result in high

computation times and memory failures for solving only the LP relaxation.

3.1 Obstacles of Integer Programming for RCPSP

One of the most prominent models for the RCPSP was introduced by [PWW69].

Their formulation adapted to resource leveling looks as follows:

4 Eamonn T. Coughlan, Marco E. L¨ubbecke, and Jens Schulz

Job 1

Job 2

(a) (b)

SjSj

xjt xjt

0 4 8

008

Figure 1. Example for a schedule where the resource demands are not counted cor-

rectly regarding the start time variables. In (a) a resource capacity of 4 is needed

but the LP solution just yields a capacity bound of 1; the resource demand of job 2

is counted at points in time totally different from the start time S2. In (b) an opti-

mal schedule is given for the integer start time variables but the corresponding binary

variables pretend that there is an optimality gap.

min X

ck·¯

Rk(1)

s.t. X

xjt ≥1∀j∈ J (2)

t·xjt =Sj∀j∈ J (3)

Si+pi≤Sj∀ij ∈E(4)

τ=t−pj+1

rjk ·xjτ ≤¯

Rk∀k∀t(5)

xjt ∈ {0,1} ∀ j∀t(6)

Binary variables xjt model whether job jstarts at time tor not. Each job j

must start exactly once (2). This time is expressed via a variable Sj, linked to the

xjt in (3). Also precedence constraints (4), and resource capacity constraints (5)

are linear. The integer program decides on the resource capacities ¯

Rkfor each

resource k, such that the total weighted resource capacity cost is minimized.

Depending on several factors, as network complexity (the density of G) or

the time discretization considered, this formulation may yield good or poor lower

bounds. We show an example LP solution, where even an optimal assignment of

the start time variables Sjdoes not yield an optimum solution value.

Example. In Fig. 1 two jobs are given, each with processing time 2 and resource

demand 2. We observe that the resource demand is easily underestimated in an

A Branch-and-Price Algorithm for Multi-Mode Resource Leveling 5

arbitrary LP solution. In Fig. 1(a) the two jobs are running in parallel and need a

resource capacity of 4, but an arbitrary LP solution with start times S1=S2= 3

is not necessarily integral and obtains a resource capacity of 1 as lower bound.

This is achieved by setting the binary variables x1,2=x1,4=x2,0=x2,6= 0.5.

Even if we are given an optimal solution S1= 2 and S2= 4, as in Fig. 1(b), the

capacity is still underestimated. The convex combination (3) of far apart start

times of a job to form Sjgives us irrelevant information about the schedule and

we lose all structure in the model. Already the minimization of the makespan

for a given capacity cannot be solved efficiently for job sets of size 60 [PSP].

Branching on the binary variables leads to a confusing result. In Fig. 1(b),

when branching on x1,0, job 1 which starts at time S1= 2 now would be sched-

uled at t= 0 or not. Thus, a more sophisticated branching rule that is aware of

the linking of continuous variables Sjand binary variables xjt and that prefers

branching on the start time variables Sjis desirable.

3.2 Master Problem: A Model based on Shift Configurations

In order to reduce the effects of “losing the timing information” just described,

we propose a model which exploits the problem structure by decomposing the

time horizon. For each schedule, or configuration, of a single resource for a single

shift, we introduce a binary variable xξwhich indicates whether configuration ξ

is chosen. We abbreviate j∈ξto express that job jis executed in the shift cor-

responding to ξ. For each ξwe know its resource capacity Rξand start time Sjξ

and completion time Cjξ of each j∈ξ. Note that the mode of each job is

determined by the start and completion times.

min X

ck·¯

Rk(7)

s.t. Ci≤Sj∀ij ∈E(8)

Sj=X

ξ:j∈ξ

Sjξxξ∀j∈ J (9)

Cj=X

ξ:j∈ξ

Cjξxξ∀j∈ J (10)

ξ:ξ∈I

Rξxξ≤¯

Rk∀k∀I∈ Ik(11)

ξ:j∈ξ

xξ≥1∀j∈ J (12)

xξ∈ {0,1} ∀ξ(13)

Each job is executed in at least one configuration by (12). The start and

completion times for each job are computed from the chosen configurations via

the linking constraints (9) and (10). Constraints (8) model the precedences be-

tween jobs which could be directly expressed by substituting Sjand Cjfrom

the linking constraints, but (9) and (10) are helpful in the upcoming pricing

6 Eamonn T. Coughlan, Marco E. L¨ubbecke, and Jens Schulz

problem where they penalize or encourage certain start or completion times of

jobs. Constraints (11) link resource consumptions to the capacities.

3.3 Column Generation: Pricing Problem

There are too many configurations to explicitly include them in the master

problem, therefore we solve the relaxation by column generation embedded into a

branch-and-bound tree. By defining dual variables sj, cj, ρ, πjfor constraints (9),

(10), (11), and (12), respectively, we obtain a pricing problem for each shift I.

max X

πjXj−X

cjCj+X

sjSj−ρR

s.t. Xj=X

m,t

xjmt ∀j∈J(14)

Sj=X

m,t

txjmt ∀j∈J(15)

Cj=X

m,t

(t+pjm)xjmt ∀j∈J(16)

m,τ:t∈[xjmτ +pjm]

rjmxjmτ ≤R∀t∈I(17)

xjmt ∈ {0,1} ∀j∈J, m, t (18)

Xj∈ {0,1} ∀j∈J(19)

This is a scheduling problem with non-regular objective function where a

new configuration ξfor a specific shift Iis generated. It must be decided, see

constraint (14), whether a job corresponding to the binary decision variable Xj

is running in this shift or not, and if so, which mode m∈ Mjis used. Con-

straints (15) and (16) fix the start and completion times of jobs according to the

chosen mode assignment. Resource capacity constraints (17) have to be satisfied

such that the total profit is maximized. The objective value is increased by πj

if a job is taken into the configuration and by multiples of sjand cjif it has

late start times and early completion times. With each unit increase of resource

capacity the objective value decreases by a factor of ρ.

The pricing problem is NP-hard as it contains a leveling problem. This can

be seen when all πjare set to a value large enough to ensure that each job must

be scheduled, and by setting sjand cjto zero for all j.

4 Branch-and-price Algorithm

A solution to the original problem is given by the resource capacities Rk, and an

assignment of start times Sjand completion times Cjfor each job j. The mode

is given by the closest resource allocation, such that pjmj≤Cj−Sj. We refer

to Rk, Sj, Cjas original or problem variables.

A Branch-and-Price Algorithm for Multi-Mode Resource Leveling 7

The variables of the pricing problem xξthat symbolize configurations of

different shifts are generated during the branch-and-price loop and whenever a

heuristic finds a feasible solution. We refer to these variables as pricing variables.

4.1 Branching scheme

Experiments revealed as branching order Rk,Sj, and then Cj. First, variables Rk

are branched on until they are fixed even if they are integral, then the start time

variables Sjare branched on and lastly the completion time variables Cj. A

variable with largest domain is selected in each rule. Branching on configuration

variables is not an option since this interferes with the pricing problem and would

unduly complicate it.

4.2 Propagation

For scheduling problems a large variety of propagation algorithms is known from

constraint programming (CP). Edge-finding is a CP technique concerned with

deriving better bounds for earliest start and latest end times of jobs using energy

arguments. The first correct algorithm, proposed in [MVH08] can be adapted to

the multi-mode case, by using the minimum energy of all modes for each job.

While this naturally seems to give weaker bounds, the fact that jobs are not

preemptive and may not cross shift-bounds, makes this a powerful propagator

during branch-and-bound.

Propagation also serves the technical purpose to communicate the branch-

ing decisions to the pricing problem in the beginning of node processing and

whenever local bounds of the problem variables change during node processing.

4.3 Primal bounds

For the master problem rounding heuristics for LP solutions are not promising,

since values of binary variables may be smeared over the time horizon and there-

fore solution values of the start and completion time variables are very unlikely

to fit to any configuration variable priced so far. It could happen, that a start-

ing time falls between two availability periods but the non-zero configuration

variables use completely different shifts, see Fig. 1.

To improve upper bounds we extended a leveling heuristic from [MMS09]

and implemented a generic list scheduling algorithm which is used as a stand

alone heuristic during the branching process as well as in the leveling procedure.

Ready scheduling heuristic. The general idea of ready scheduling is similar

to that of list scheduling with jobs sorted by earliest start times. Jobs are divided

according to the resource they need, and scheduled as soon as their predeces-

sors are completed, if possible, thus increasing the chance to meet a given time

horizon. We say a job is “ready” if all its predecessors are scheduled.

8 Eamonn T. Coughlan, Marco E. L¨ubbecke, and Jens Schulz

For each resource kwe maintain a set of jobs Jk= (jk1, .., jk|Jk|) that use this

resource and have no unscheduled predecessors, together with a lower bound tk

on the next feasible start FSjof any job j∈Jk. If Jkis empty, we set tkto ∞.

The heuristic loops over t, which increases to the minimal tkin each iteration.

A subset I⊂Jkof constant size s(we chose s= 6 in our computational studies)

is scheduled so that the overall completion time is kept small (line 8). This is

accomplished by trying all mode combinations for Irecursively, and bounding

recursion using the currently shortest feasible solution found in this way. If s

is small, this can be done quickly. Finally, for each scheduled job in I, those

successors which become ready, are added to the corresponding set Jk, each tk

is updated, and the next iteration begins. This process continues until all jobs

are scheduled, or a makespan violation occurs.

Algorithm 1: Ready Scheduling

Input: Set of jobs Jto be scheduled and max. total duration T

Output: Job start times and modes, or that no solution was found.

for k∈ R do1

Let Jk⊂ J be the set of jobs that use resource k, and are ready.2

Set tkto minj∈JkFSj.3

Set t:= 04

while t<T do5

`:= argminktk, and t:= tl

m:= min(s, |J`|) with sa small constant and I:= {j`1, .., j`m}7

Schedule jobs in Isuch that maxi∈ICiis minimal.8

Add all successors of jobs in Ithat become ready to their respective Jk.9

J`:= J`\I10

Update tkfor all changed Jkas in Step 311

Resource Leveling heuristic. We now describe the resource leveling heuristic

by [MMS09], and how the ready scheduler ties into the framework of the lev-

eling procedure. This heuristic uses a binary search on the capacity bounds of

the resources, while greedily selecting the resource whose upper bound is to be

improved in each iteration. This selection is based on a parameter µk, measuring

how badly a resource kis leveled.

One iteration of the binary search consists of trying to find a feasible schedule

for the current bounds. These bounds for the selected resource k?are set to

(UBk?+ LBk?)/2, UBk?and LBk?being the upper and lower bounds on the

capacity of resource k?, while all other resource bounds remain fixed. We try

list scheduling, and on failure fall back to ready scheduling to prove the bounds

feasible. If neither ready scheduling nor list scheduling yield a feasible schedule,

we consider the current upper bound for the selected resource as a new lower

bound, and the next iteration begins.

A Branch-and-Price Algorithm for Multi-Mode Resource Leveling 9

Algorithm 2: Resource Leveling

Input: Set Rof resource types to be leveled, project duration T.

Output: Leveled resource utilization Rkfor each resource type k∈ R.

Set LBkand UBkto initial values for each resource type k∈ R.1

while ∃k∈ R : LBk<UBkdo2

Choose resource type k?∈ R with LBk?<UBk?and µk?maximum.3

Perform binary search using list scheduling and ready scheduling in4

order to decrease the capacity bounds of k?.

LP solution and ready scheduling heuristics. In each node of the branch-

and-bound tree these heuristics set the maximal capacity of each resource to

the LP solution value rounded up, and fix the earliest and latest start and com-

pletion times for each job to the global bounds of the corresponding variables.

We perform list scheduling with jobs sorted by start completion times in the

LP solution, and each job’s mode is chosen as the one matching Ci−Sibest.

If no feasible solution is obtained we try ready scheduling. Both of these heuris-

tics produce solutions that are not necessarily feasible w.r.t. the current primal

bound, since resource capacities are rounded up. Regardless of this, if a feasi-

ble schedule is found new columns representing that schedule are added to the

master problem, in order to reduce the total number of pricing steps.

5 Computational Study

5.1 Experimental Setup

As there is no set of instances which really suits our problem, we needed to

compile our own. It is composed of three sets of job scenarios, with 10 instances

each. Each job can run in 3 different modes, using 1 to 3 resources, with durations

ranging from 5 to 12. In the first scenario instances have 30 jobs and 60 edges,

and in the second and third scenario instances contain 50 jobs with 70 and 100

edges respectively. The maximal precedence graph width is 5 for scenario one,

and 6 for the other two. These width bounds are achieved by constructing W

chains of length |J |/N, and randomly choosing the remaining edges.

There are two different resources which come in 5 calendar configurations,

called C1 to C5. These calendars are described schematically in Fig. 2. In the

Figure 2. Calendar configurations C1–C3 (top) and C4 and C5 (bottom) used in our

test set. Black bars symbolize the temporal location of shifts.

10 Eamonn T. Coughlan, Marco E. L¨ubbecke, and Jens Schulz

Table 1. Comparison of the BP approach with the standard MIP (|J | = 30).

Branch-and-Price B&P w/o heur. CPLEX RL

Calendar time LB UB †time LB UB †time LB UB †UB

C1 446 9 9 1 435 10 10 0 1350 6 3 7 6

C2 326 9 10 1 360 9 9 1 435 9 9 2 5

C3 9 10 10 0 11 10 10 0 1 10 10 0 9

C4 81 10 10 0 81 10 10 0 494 9 10 1 8

C5 72 10 10 0 146 10 10 0 1631 3 4 7 6

Total 187 48 49 2 207 49 49 1 782 37 36 17 34

Table 2. Comparison of the BP approach with the standard MIP (|J | = 50).

|J | = 50,|E|= 70

Branch-and-Price CPLEX RL

Calendar time LB UB †time LB UB †UB

C1 1660 10 9 7 1800 6 1 10 7

C2 1662 4 7 8 1361 7 6 7 5

C3 27 10 10 0 4 10 10 0 10

C4 719 10 10 2 1800 6 0 10 5

C5 1293 8 8 5 1335 7 6 7 5

Total 1072 42 44 22 1260 36 23 34 32

|J | = 50,|E|= 100

Calendar time LB UB †time LB UB †UB

C1 1137 9 10 3 1800 3 0 10 7

C2 1224 6 9 5 1622 5 4 9 6

C3 9 10 10 0 2 10 10 0 9

C4 254 10 10 0 1800 1 0 10 8

C5 365 10 10 0 1451 5 5 6 6

Total 598 45 49 8 1335 24 19 35 36

top row, calendars C1 to C3 are shown. In each of these, the length of the

shifts is 60. In C1 and C3 shift breaks are 60 units long, in C2 only 20. Both

resources are available at the same time in C1, while in C3 availability periods

are complementary. In C2 the second resource is offset at 40 units, and shift

breaks have length 20. Calendars C4 and C5 show shifts with length 20 and

breaks having length 5. In C5 one of the resources is offset by 10. All scenarios

are tested with each of the 5 different calendars. Time horizons were chosen

by computing a minimal and maximal makespan heuristically using simple list

scheduling, and averaging these.

Our algorithm was tested on an Intel 2.66 GHz processor, and each test run

had a time-limit of 30 minutes. The implementation uses SCIP 1.2.0.6 [SCI], to

perform the branch-and-bound process, with custom plug-ins for the heuristics,

branching rules, and the pricer. For the standard MIP (1)–(6) we used CPLEX

12 with quad-core parallelization on a stronger machine.

Our empirical results can be seen in Tabs. 1 and 2. These tables show four

columns per algorithm. The first column contains the average time in seconds to

solve the instance with a limit of 1800. The second and third columns represent

the number of times the algorithm reached the best known lower and upper

bounds over all algorithms, denoted by “LB” and “UB.” The fourth column is

A Branch-and-Price Algorithm for Multi-Mode Resource Leveling 11

the number of timeouts, marked by “†.” An additional last column “RL” per

table shows the number of times the resource leveling heuristic reached the best

known upper bound for each set of instances. The rows in each table represent

the calendar configurations used.

In the first table, three different algorithms are compared on the first scenario.

“Branch-and-price” refers to the general scheme presented here, while “B&P w/o

heur.” does not use the LP solution or ready scheduling heuristics during the

branch-and-bound process. However, it does start with the solution found by the

resource leveling heuristic. The “CPLEX” columns correspond to the results of

the standard MIP (1)–(6). The “Branch-and-price” algorithm, as well as CPLEX

and the resource leveling heuristic, are tested on the second and third scenarios

in Tab. 2 respectively.

Impact of calendars. Obviously, the calendar choice has a big influence on

running time. For 30 jobs we observe that with the one hour shifts the makespan

generally increases as the resources overlap less. Interestingly, for the short shifts

the makespan increases with more overlap (C4 instances generally have larger

makespan than those in C5), yet these instances can nevertheless be solved faster.

The “hardness” of a problem does not solely depend on the makespan though,

as CPLEX shows the worst behavior on instances with 50 jobs and calendars C1

and C4, where the shifts are overlapping completely. This is not the case for the

branch-and-price algorithm, which actually performs much better on C4 and C1,

see also Tab. 2. All approaches easily solve instances using C3, because many

jobs have a successor of a different resource, introducing long waiting times.

Usefulness of the heuristics. Our heuristics exploit problem specific knowl-

edge during the branch-and-bound process, however, this does not appear to

have a big impact on the number of problems solved, as can be seen in Tab. 1.

Still, the average solving time decreases noticeably across all instances with the

heuristics enabled. The running times of all our heuristics are negligible, and in

contrast to the exact methods, the resource leveling heuristic is able to handle

instances of practically relevant size, while still achieving the best found upper

bound in 68% of all instances.

Influence of the network complexity. When the number |E|of edges in G

is increased, the makespan typically increases as well, so that the time-indexed

MIP formulation grows fairly large and CPLEX generally fares better on the

instances with less edges. For 50 jobs and 70 edges CPLEX finds the best lower

bound 36 times and the best upper bound 23 times, in contrast to 24 best lower

and 19 best upper bounds for 100 edges (Tab. 2). In contrast the branch-and-

price does not suffer from this, and the computation times actually decrease on

the instances with more edges.

As expected, CPLEX has considerable problems as the instances get larger.

One of the main features of the turnaround scheduling problem is the presence of

availability periods, which motivated this branch-and-price approach. It achieves

the best results across all shift configurations, in the worst case 88% of the best

upper bounds are found. In most cases lower bounds computed by CPLEX are

of poor quality. Proving optimality succeeded in 80% of cases for Branch-and-

12 Eamonn T. Coughlan, Marco E. L¨ubbecke, and Jens Schulz

Price, whereas CPLEX only manages 43%. Summarizing, our branch-and-price

algorithm significantly outperforms the standard time-indexed MIP formulation

solved by the state-of-the-art solver CPLEX on large instances.

6 Summary

Our own experiments and instance sizes as reported e.g., in [DK01] or [PSP]

for scheduling problems of comparable complexity give good reasons to believe

that even today instances with only 30 jobs are hard to solve to optimality. We

are encouraged to further investigate branch-and-price algorithms for this type

of problem, as we do not only report better results on similarly sized instances,

but are also able to optimally solve some instances with up to 50 jobs.

References

[BDM+99] P. Brucker, A. Drexl, R. M¨ohring, K. Neumann, and E. Pesch. Resource-

constrained project scheduling: Notation, classification, models, and meth-

ods. European J. Oper. Res., 112:3–41, 1999.

[Dem95] E. Demeulemeester. Minimizing resource availability costs in time-limited

project networks. Management Sci., 41:1590–1598, 1995.

[DH02] E.L. Demeulemeester and W.S. Herroelen. Project Scheduling: A Research

Handbook. Kluwer, 2002.

[DK01] A. Drexl and A. Kimms. Optimization guided lower and upper bounds for

the resource investment problem. The Journal of the Operational Research

Society, 52(3):340–351, 2001.

[FNS01] B. Franck, K. Neumann, and C. Schwindt. Project scheduling with calen-

dars. OR Spektrum, 23:325–334, 2001.

[Har01] S. Hartmann. Project scheduling with multiple modes: A genetic algorithm.

Ann. Oper. Res., 102(1-4):111–135, 2001.

[HB09] S. Hartmann and D. Briskorn. A survey of variants and extensions of the

resource-constrained project scheduling problem. European J. Oper. Res.,

In Press, 2009.

[MMS09] N. Megow, R.H. M¨ohring, and J. Schulz. Decision support and optimization

in shutdown and turnaround scheduling. Preprint 009-2009, Institut f¨ur

Mathematik, Technische Universit¨at Berlin, 2009.

[M¨oh84] R.H. M¨ohring. Minimizing costs of resource requirements in project net-

works subject to a fixed completion time. Oper. Res., 32(1):89–120, 1984.

[MVH08] L. Mercier and P. Van Hentenryck. Edge finding for cumulative scheduling.

INFORMS J. Computing, 20(1):143–153, 2008.

[NSZ03] K. Neumann, C. Schwindt, and J. Zimmermann. Project scheduling with

time windows and scarce resources. Springer, 2003.

[PSP] PSPLib. Project Scheduling Problem LIBrary. http://129.187.106.231/

psplib/. Last accessed 2010/02/01.

[PWW69] A.A.B. Pritsker, L.J. Watters, and P.M. Wolfe. Multi project scheduling

with limited resources: A zero-one programming approach. Management

Sci., 16:93–108, 1969.

[SCI] SCIP. Solving Constraint Integer Programs. http://scip.zib.de/.

[Zha92] J. Zhan. Calendarization of time planning in MPM networks. ZOR –

Methods and Models for Oper. Res., 36(5):423–438, 1992.