An iterative time‐bucket refinement algorithm for a high‐resolution resource‐constrained project scheduling problem

• Author: Martin Riedler,Johannes Maschler,Thomas Jatschka,Günther R. Raidl
• Date: 01 January 2020
• Published date: 01 January 2020
• DOI: http://doi.org/10.1111/itor.12445

Intl. Trans. in Op. Res. 27 (2020) 573–613

DOI: 10.1111/itor.12445

INTERNATIONAL

TRANSACTIONS

IN OPERATIONAL

RESEARCH

An iterative time-bucket refinement algorithm for a

high-resolution resource-constrained project scheduling

problem

Martin Riedler, Thomas Jatschka, Johannes Maschler and G¨

unther R. Raidl

Institute of Computer Graphics and Algorithms, TU Wien, Favoritenstraße 9-11/186-1, 1040 Vienna, Austria

E-mail: riedler@ac.tuwien.ac.at [Riedler]; jatschka.thomas@gmail.com[Jatschka];

maschler@ac.tuwien.ac.at [Maschler];raidl@ac.tuwien.ac.at [Raidl]

Received 15 October 2016; receivedin revised form 11 July 2017; accepted 12 July 2017

Abstract

We consider a resource-constrained project scheduling problem originating in particle therapy for cancer

treatment, in which the scheduling has to be done in high resolution. Traditional mixed integer linear

programming techniques such as time-indexedformulations or discrete-event formulations areknown to have

severe limitations in such cases, that is, growing too fast or having weak linear programming relaxations. We

suggest a relaxation based on partitioning time into so-called time-buckets. This relaxationis iteratively solved

and serves as basis for deriving feasible solutions using heuristics. Based on these primal and dual solutions

and bounds, the time-buckets are successively refined. Combining these parts, we obtain an algorithm that

provides good approximate solutions soon and eventuallyconverges to an optimal solution. Diverse strategies

for performing the time-bucket refinement are investigated. The approach shows excellent performance in

comparison to the traditional formulations and a metaheuristic.

Keywords: resource-constrained project scheduling; time-bucket relaxation; mixed integer linear programming;

matheuristics; particle therapy

1. Introduction

Scheduling problems arise in a variety of practical applications. Prominentexamples are job shop or

project scheduling problems that require a set of activities to be scheduled over time. The execution

of the activities typically depends on certain resources of limited availability and diverse other

restrictions such as precedence constraints. The goal is to find a feasible schedule that minimizes

some objective function like the makespan. In certain cases, scheduling has to be done in a very fine

grained way, that is, in high resolution, using, for example, seconds or even milliseconds as unit of

time.

C

2017 The Authors.

International Transactionsin Operational Research C

2017 International Federation ofOperational Research Societies

Published by John Wiley & Sons Ltd, 9600 Garsington Road, Oxford OX4 2DQ, UK and 350 Main St, Malden, MA02148,

USA.

574 M. Riedler et al. / Intl. Trans. in Op. Res. 27 (2020) 573–613

Classical mixed integer linear programming (MILP) formulations are known to struggle under

these conditions. On the one hand, time-discretized models provide strong linear programming(LP)

bounds but grow too quickly with the instance size due to the fine time discretization. Event- and

sequencing-based models, on the other hand, typically have trouble as a result of their weak LP

bounds.

In the following, we focus on problems with a large, very fine grained scheduling horizon and

consider a simplified scheduling problem arising in the context of modern particle therapy used

for cancer treatment. The problem is motivated by a real world patient scheduling scenario at the

recently founded cancer treatment center MedAustron located in Wiener Neustadt, Austria.1The

tasks involved in providing a given set of patients with their individual particle treatments shall be

scheduled in such a way that given precedence constraints with minimum and maximum time lags

are respected. Each task needs certain resources forits execution. One of the resources is the particle

beam, which is particularly scarce as it is required by every treatment and shared between several

treatment rooms. The motivation therefore is to exploit in particular the availability of the beam

as good as possible by suitably scheduling all activities in high time resolution. Ideally, the beam is

switched immediately after an irradiation has taken place in one room to another room where the

next irradiation session starts without delay.

Our goal is to minimize the makespan. This objective emerges from the practical scenario as

tasks need to be executed as densely as possible to avoid idle time within the day as well as to allow

treating as many patients as possible within the operating hours. However, makespan minimization

is clearly an abstraction from the real world scenario where more specific considerations need to

be taken into account. In the terminology of the scientific literature in scheduling, the considered

problem corresponds to a resource-constrainedproject scheduling problem (RCPSP)with minimum

and maximum time lags.

In this work, we introduce the simplified intraday particle therapy patient scheduling problem

(SI-PTPSP) and present for it a discrete-event formulation (DEF) and a time-indexed formulation

(TIF) as reference models. We propose a time-bucket relaxation (TBR) and prove some theoretical

properties. In the main part, we deal with the iterative time-bucket refinement algorithm (ITBRA)

that aims atclosing the gap between dual solutions obtained by solving time-bucket relaxation(TBR)

based on iteratively refined bucket partitionings and heuristically determined primal solutions

exploiting dual solutions. Various strategies for refining the bucket partitioning are suggested.

Experimental results clearly indicate the superiority of the new matheuristic approach over the

reference MILP models as well as a basic greedy randomized adaptive search procedure (GRASP).

The remainder of the article is organized as follows. In Section 2, we provide a formal definition

of the simplified intraday particle therapy patient scheduling problem (SI-PTPSP). Then, we review

the related literature. In the following section, we provide two reference MILP formulations. The

main part consists of the description of TBR and its properties in Section 5 and the presentation

of iterative time-bucket refinement algorithm (ITBRA) in Section 6. We provide the fundamental

iterativeframework with its specifically used subalgorithms that are the gap closing heuristic (GCH),

the activity block construction heuristic (ABCH), a GRASP metaheuristic, and the investigated

bucket refinement strategies. Further implementation details such as preprocessing procedures are

covered in Section 7. Finally, we discuss computational experiments conducted on two sets of

1https://www.medaustron.at

C

2017 The Authors.

International Transactionsin Operational Research C

2017 International Federation ofOperational Research Societies

M. Riedler et al. / Intl. Trans. in Op. Res. 27 (2020) 573–613 575

benchmark instances in Section 8, before concluding and giving an outlook on promising future

research directions in Section 9.

2. Simplified intraday particle therapy patient scheduling problem

The SI-PTPSP is defined on a set of activities A={1,...,α}and a set of unit-capacity resources

R={1,...,ρ}. Each activity a∈Ais associated with a processing time pa∈N>0, a release time

tr

a∈N≥0, and a deadline td

a∈N≥0with tr

a≤td

a. For its execution, an activity a∈Arequires a

subset Qa⊆Rof the resources. Activities need to be executed without preemption. The considered

set of time slots T={Tmin,...,Tmax}is derived from the properties of the activities as follows:

Tmin =mina∈Atr

aand Tmax =maxa∈Atd

a−1. We denote by Ya(t)the set of time points during

which activity a∈Aexecutes when starting at time t,thatis,Ya(t)={t,...,t+pa−1}. To model

dependencies among the activities, we consider a directed acyclic precedence graph G=(A,P)

with P⊂A×A.Eacharc(a,a)∈Pis associated with a minimum and a maximum time lag

Lmin

a,a,Lmax

a,a∈N≥0with Lmin

a,a≤Lmax

a,a. For each resource r∈Ra set of availability time windows

Wr=w=1,...,ωrWr,wwith Wr,w={Wstart

r,w,...,Wend

r,w}⊆Tis given. Resource availability windows

are nonoverlapping and ordered according to starting time Wstart

r,w. In accordance with the resource

availabilities and the precedence relations among the activities, we can deduce for each activity a set

of feasible starting times, denoted by Ta⊆{tr

a,...,td

a−pa}; for details on the computation of this

set see Section 7.1.

A feasible solution S(also called schedule) to SI-PTPSP is a vector of values Sa∈Taassigning

each activity a∈Aa starting time within its release time and deadline subject to the availabilities

of the required resources and all precedence relations are respected. The goal is to find a feasible

solution having minimum makespan.

Using the notation introduced in Brucker et al. (1999), our problem can be classified as

PSm,·,1|rj,dj,temp|Cmax.

Computational complexity. Lawler and Lenstra (1982) have shown that finding a solution for

the non-preemptive single machine scheduling problem with deadlines and release times (1|rj|Cmax

according to the notation by Graham et al. (1979)) is NP-hard. We can easily reduce an instance of

1|rj|Cmax to an instance of SI-PTPSP byassigning the same resource to each activity of the 1|rj|Cmax

instance. Processing times, release times, and deadlines of the activities remain unchanged. Since

there are no precedence constraints in 1|rj|Cmax, the set of precedence arcs is empty. Consequently,

SI-PTPSP is NP-hard.

3. Related work

In this section, we discuss the related work relevant for our contribution. We start with a brief

overview of RCPSP. Afterwards, we review the derivation of dual bounds for such scheduling

problems. Then, we give a short introduction on matheuristics applied in this domain. Finally, we

C

2017 The Authors.

International Transactionsin Operational Research C

2017 International Federation of OperationalResearch Societies