An Approximative Criterion for the Potential of Energetic Reasoning [original]

An Approximative Criterion for the Potential of

Energetic Reasoning?

Timo Berthold1, Stefan Heinz1, and Jens Schulz2

1Zuse Institute Berlin, Takustr. 7, 14195 Berlin, Germany

{berthold,heinz}@zib.de

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

10623 Berlin, Germany

[email protected]

Abstract. Energetic reasoning is one of the most powerful propagation

algorithms in cumulative scheduling. In practice, however, it is commonly

not used because it has a high running time and its success highly de-

pends on the tightness of the variable bounds. In order to speed up ener-

getic reasoning, we provide a necessary condition to detect infeasibilities,

which can be tested efficiently.

We present an implementation of energetic reasoning that employs this

condition and that can be parametrically adjusted to handle the trade-off

between solving time and propagation overhead. Computational results

on instances from the PSPLib are provided. They show that using the

condition decreases the running time by more than a half, although more

search nodes need to be explored.

1 Introduction

Many real-world scheduling problems rely on cumulative restrictions.

In this paper, we consider a cumulative scheduling problem with non-

preemptable jobs and fix resource demands. Such a problem is determined

by earliest start and latest completion times to all jobs, the resource de-

mands, and a resource capacity for each resource. Besides that precedence

constraints between different jobs might be present. The goal is to find

start times for each job, a schedule, such that the cumulative demands do

not exceed the capacities and the precedence requirements are satisfied.

Computing such a schedule is known to be strongly NP-hard [3].

Several exact approaches were developed that solve the problem by

branch-and-bound, using techniques from constraint programming, inte-

ger programming, or satisfiability testing. In constraint programming, the

?Supported by the DFG Research Center Matheon Mathematics for key technologies

in Berlin.

2 Timo Berthold, Stefan Heinz, Jens Schulz

main task is to design efficient propagation algorithms that adjust vari-

able bounds or detect infeasibility of a search node, in order to keep the

search tree small. Such algorithms are usually executed more than once

per search node. The most powerful and widely used algorithms in cumu-

lative scheduling are time-tabling, edge-finding, and energetic reasoning.

This paper concentrates on the evaluation of the energetic reasoning

algorithm. Its merit lies in a drastic reduction of the number of search

nodes by detecting infeasible nodes early. It has, however, a cubic running

time in the number of jobs and is only capable to find variable bound

adjustments for rather tight variable bounds.

Related work. Baptiste et.al. [1] provide a detailed overview on the main

constraint programming techniques for cumulative scheduling. Therein,

several theoretical properties of energetic reasoning are proven. A more

general idea of interval capacity consistency tests is given by Dorndorf

et.al. [4]. In the same paper, unit-size intervals are considered as a spe-

cial case, which leads to the time-tabling algorithm [6]. Recently, Kooli

et.al. [7] used integer programming techniques in order to improve the

energetic reasoning algorithm. This approach extends the method pre-

sented by Hidri et.al. [5], where the parallel machine scheduling problem

has been considered. In both works only infeasibility of a subproblem is

checked; variable bound adjustments are not performed.

Contribution. We derive a necessary condition for energetic reasoning

to detect infeasibilities. The condition is based on a relative energy his-

togram, which can be computed efficiently. We show that this histogram

underestimates the true energy requirement of an interval by a factor of

at most 1

/3. We embed this approximative result in a parametrically ad-

justable propagation algorithm which detects variable bound adjustments

and infeasibilities in the same run.

As our computational results reveal, the presented algorithm drasti-

cally reduces the total computation time for solving instances from the

PSPLib [8] in contrast to the pure energetic reasoning algorithm.

Outline. We introduce the resource-constrained project scheduling prob-

lem (RCPSP) and the general idea of energetic reasoning in Section 2. In

Section 3 we derive a necessary condition for energetic reasoning to be

successful and embed it into a competitive propagation algorithm. Exper-

imental results on instances from PSPLib [8] are presented in Section 4.

An Approximative Criterion for the Potential of Energetic Reasoning 3

2 Problem description and Energetic Reasoning

In resource-constrained project scheduling (RCPSP) we are given a set J

of non-preemptable jobs and a set Rof renewable resources. Each re-

source k∈ R has bounded capacity Ck∈N. Every job j∈ J has

a processing time pj∈Nand resource demands rjk ∈Nfor each re-

source k∈ R. The start time Sjof job jis constrained by its prede-

cessors that are given by a precedence graph D= (V, A) with V=J.

An arc (i, j)∈Arepresents a precedence relationship, i.e., job imust be

finished before job jstarts. The goal is to schedule all jobs with respect

to resource and precedence constraints, such that the makespan, i.e., the

latest completion time of all jobs, is minimized.

The RCPSP can be modeled as a constraint integer program as follows:

min max

j∈J Sj+pj

subject to Si+pi≤Sjfor all (i, j)∈A(1)

cumulative(S,p,r.k, Ck)∀k∈ R (2)

The constraints (1) represent the precedence conditions. The cumula-

tive constraints (2) enforce that at each point in time t, the cumulated

demand of the set of jobs running at that point, does not exceed the given

capacities, i.e.,

j∈J :t∈[Sj,Sj+pj[

rjk ≤Ckfor all k∈ R.

Energetic reasoning is a technique to detect infeasibility or to ad-

just variable bounds for one cumulative constraint k∈ R, based on

the amount of work that must be executed in a specified time in-

terval. The term energetic reasoning has been defined for partially or

fully elastic scheduling problems [1]. This procedure is also known as

Left-Shift/Right-Shift technique in case of cumulative scheduling with

non-interruptible jobs. Given an upper bound on the latest completion

time of all jobs, we obtain earliest start times estj, earliest completion

times ectj, latest start times lstj, and latest completion times lctjfor

each job j∈ J . The required energy E(a, b) of all jobs in interval [a, b[ is

given by E(a, b) := Pj∈J ej(a, b), with

ej(a, b) := max{0,min{b−a, pj,ectj−a, b −lstj}} · rj.

Hence, ej(a, b) is the non-negative minimum of (i) the volume in the

interval [a, b[, (ii) the energy of job j, (iii) the left shifted energy, and (iv)

4 Timo Berthold, Stefan Heinz, Jens Schulz

job 1

job 2

job 3

job 4

0 1 2 3 4

Fig. 1. Problem setup of Example 1.

the right shifted energy. With respect to ej(a, b), a problem is infeasible

if more energy is required than available, so for a < b and a resource

capacity Cwe can deduce:

Corollary 1 ([1]). If E(a, b)>(b−a)·C, then the problem is infeasible.

Example 1. Consider a cumulative resource of capacity 2 and four jobs

each with a resource demand of 1, an earliest start time of 0 and a latest

completion time of 4. Three of these jobs have a processing time of 2.

The fourth job instead has a processing time of 3. Figure 1 illustrates this

setup. For the interval [1,3[, the available energy is (3 −1) ·2 = 4 . The

first three jobs contribute 1 units each where as the fourth jobs adds 2 to

the required energy. This sums up to E(1,3) = 5. This shows that that

these jobs cannot be scheduled.

In order to detect infeasibility, O(n2) time-intervals need to be con-

sidered [1]. Those intervals are determined in the following way:

O1:= [

j{estj}∪{estj+pj}∪{lctj−pj},

O2:= [

j{lctj}∪{estj+pj}∪{lctj−pj}and

O(t) := [

{estj+ lctj−t}.

The relevant intervals to be checked for energetic tests are given by (a, b)∈

O1×O2and for fixed a∈O1: (a, b)∈O1×O(a) and for fixed b∈O2:

(a, b)∈O(b)×O2. These are O(n2) many.

Besides detecting infeasibilities, variable bounds can be adjusted by

energetic reasoning. Due to symmetry reasons, we just consider the ad-

An Approximative Criterion for the Potential of Energetic Reasoning 5

justments of lower bounds. Let

eleft

j(a, b) := rj·max{0,min{pj, b −a, min{b, ectj} − max{a, estj}}}

be the required energy in the interval [a, b[ of job jif it is left-shifted, i.e.,

it starts as early as possible. If [a, b[ intersects with [estj,ectj[ and the

required energy E(a, b)−ej(a, b) + eleft

j(a, b) exceeds the available energy

in [a, b[, then jcannot start at its earliest start time and the lower bound

can be updated according to Theorem 1.

Theorem 1 ([1]). Let [a, b[, a < b and j∈ J with [estj,ectj[∩[a, b[6=∅.

If E(a, b)−ej(a, b) + eleft

j(a, b)>(b−a)·Cholds, then the earliest start

time of job jcan be updated to

estj=a+1

(E(a, b)−ej(a, b)−(b−a)·(C−rj)) .

In case of feasibility tests, we are able to restrict the set of intervals that

need to be considered. Whether such restrictions can also be made for

variable bound adjustments is an open problem. The currently fastest

energetic reasoning propagation algorithm runs in O(n3).

3 Restricted Energetic Reasoning

Energetic reasoning only finds variable bound adjustments when the

bounds of the start time variables are tight, since it compares the available

energy to the requested energy for some intervals. If the bounds are loose

and small intervals are considered, a job may contribute almost no energy

to that interval or in case of large intervals not enough energy is required

in order to derive any adjustments. This is a clear drawback as we are

faced with a very time-consuming algorithm. In order to come up with

a practical competitive propagation algorithm, we identify intervals that

seem promising to detect infeasibilities and variable bound adjustments.

3.1 Estimation of relevant intervals

Let us consider one resource with capacity C, and cumulative demands rj

for each job j. The total energy requirement of job jis given by ej=pj·rj.

We measure the relative energy consumption ˜ej:= ej

lctj−estj.

We define the relative energy histogram ˜

E:N→Rand the relative

energy ˜

E(a, b) of an interval [a, b[ by:

E(t) := X

j:estj≤t<lctj

lctj−estj

and ˜

E(a, b) :=

b−1

t=a

E(t).

6 Timo Berthold, Stefan Heinz, Jens Schulz

This histogram approximates the required energy E(a, b) computed by

energetic reasoning for each point in time, as we prove in Theorem 2.

Theorem 2. Given an arbitrary non-empty interval [a, b[. Then

α·E(a, b)≤˜

E(a, b)

with α > 1

/3.

Proof. We show the approximation factor αfor each job separately. By

linearity of summation, the theorem follows.

First, we restrict the study to the case where estj≤a<b≤lctj. Let

˜ej(a, b) = pj·rj

lctj−estj

·(min{lctj, b} − max{estj, a}).

If the energy is underestimated in [a, b[, then it follows that estj< a

or lctj> b, since otherwise ˜ej(a, b) = ej(a, b). Assume estj≤a < lctj< b.

By definition, ej(a, b) = ej(a, lctj) and ˜ej(a, b) = ˜ej(a, lctj). Applying a

symmetrical argument to a < estj< b ≤lctj, we can restrict the setting

to estj≤a<b≤lctj, such that ˜ej(a, b) = pjrr(b−a)/(lctj−estj).

Note that in this case the energy gets underestimated, i.e., 0 <˜ej(a, b)<

ej(a, b).

Case 1. Consider the case ej(a, b) = pj·rj. That means the job is fully

contained in [a, b[. This is a contradiction to ˜ej(a, b)< ej(a, b).

Case 2. Assume the following two properties:

(i) 1 ≤min{ectj−a, b −lstj}<min{b−a, pj}

(ii) ej(a, b) = min{ectj−a, b −lstj} · rj.

Thus, α0:= ˜ej(a, b)/ej(a, b) yields:

α0=pj(b−a)

(lctj−estj)·min{ectj−a, b −lstj}>max{pj, b −a}

lctj−estj

Minimizing α0with respect to 1 ≤min{ectj−a, b −lstj}yields b−a=k

and pj:= k+ 1 for some k∈N, such that α0= max{k+ 1, k}/(3k)>1

/3.

Case 3. Finally, consider the case b−a < min{pj,ectj−a, b −lstj}. Thus,

ej(a, b)=(b−a)rj. That means, the job is completely executed in [a, b[,

i.e., [a, b[⊆[lstj,ectj[. This yields the condition ectj≥lstj+(b−a), which

is equivalent to 2pj−(b−a)≥lctj−estj. Thus,

˜ej(a, b) = pj·rj

lctj−estj

(b−a)≥pj

2pj−(b−a)rj·(b−a) = 1

2−b−a

| {z }

=:α00

ej(a, b).

We obtain α:= min{α0, α00}>1

/3.ut

An Approximative Criterion for the Potential of Energetic Reasoning 7

The proof shows that an underestimation of E(a, b) happens if the

core of a job, i.e., [lstj,ectj[, overlaps that interval or if a job is associ-

ated with a large interval [estj,lctj[ and intersects just slightly with [a, b[.

The following corollary states the necessary condition that we use in our

propagation algorithm.

Corollary 2. Energetic reasoning cannot detect any infeasibility, if ei-

ther of the following conditions hold

(i) for all [a, b[, a < b, ˜

E(a, b)≤1

3(b−a)C

(ii) for all t:˜

E(t)≤1

3C.

The histogram ˜

Ecan be computed in O(nlog n) by first sorting the ear-

liest start times and latest completion times of all jobs and then creating

the histogram chronologically from earliest event to latest event. Since

there are O(n) event points (the start and completion times of the jobs)

only O(n) changes in the histogram need to be stored.

3.2 Restricted Energetic Reasoning Propagation Algorithm

We now present a restricted version of energetic reasoning which is based

on the results of the previous section. Due to Theorem 2, only inter-

vals [a, b[ containing points in time twith ˜

E(t)>1

/3Cneed to be checked.

Note that the cardinality of this set may still be cubic in the number of

jobs. We introduce an approach, in which we only execute the energetic

reasoning algorithm on interval [t1, t2[ if

∀t∈[t1, t2[: ˜

E(t)> α ·C

holds. For given ˜

E, this condition can be checked in O(n). If it holds, we

check each pair (a, b)∈O1×O2with [a, b[⊆[t1, t2[ in order to detect

infeasibility or to find variable bound adjustments.

The procedure is captured in Algorithm 1. Here only the propagation

of lower bounds is shown, upper bound adjustments work analogously.

As mentioned before, the relative energy histogram ˜

E(t) can be com-

puted in O(nlog n) and needs O(n) space. The sets O1and O2also

need O(n) space and are sorted in O(nlog n). Loops 5 and 10 together

consider at most all O(n2) intervals O1×O2. Loop 13 will consider at

most O(n) jobs. Since E(a, b) is precomputed in line 11 and all other

calculations can be done in constant time, we are able to bound the total

running time.

Corollary 3. Algorithm 1 can be implemented in O(n3).

8 Timo Berthold, Stefan Heinz, Jens Schulz

Algorithm 1: Restricted Energetic Reasoning propagation algo-

rithm for lower bounds.

Input: Resource capacity C, set Jof jobs, and a scaling factor α.

Output: Earliest start times est0

jfor each job jor an infeasibility is detected.

Create relative energy histogram ˜

E.1

Compute and sort sets O1and O2.2

if ˜

E(t)≤α·Cfor all tthen3

stop.4

forall event points tin increasing order do5

if ˜

E(t)≤α·Cthen6

continue.7

t1:= t.8

Let t2be the first event point after twith ˜

E(τ)≤α·C.9

forall (a, b)∈O1×O2: [a, b[⊆[t1, t2[do10

if E(a, b)>(b−a)·Cthen11

stop: infeasible.12

forall jobs jwith [a, b[∩[estj,ectj[6=∅do13

if E(a, b)−ej(a, b) + eleft

j(a, b)>(b−a)·Cthen14

rest := E(a, b)−ej(a, b)−(b−a)·(C−rj).15

est0

j:= a+drest /rje.16

if est0

j>lstjthen17

stop: infeasible.18

t:= t2.19

Asymptotically, it has the same running time as pure energetic reason-

ing, but the constants are much smaller. Compared to the pure energetic

reasoning algorithm we only consider large intervals if the relative energy

consumption is huge over a long period. The savings in running time and

further influences on the solving process will be discussed in the following

Section.

4 Computational results

We performed our computational results on the RCPSP test sets j30

and j60 from the PSPLib [8]. Each test set contains 480 instances with 30

or 60 jobs per instance. We use the default settings of our implementation

of the cumulative constraint as presented in [2] with scip version 1.2.1.5

and integrated cplex release version 12.10 as underlying LP solver. The

only scheduling specific propagation algorithm used is energetic reason-

ing and its parametric variants using the necessary condition from Corol-

An Approximative Criterion for the Potential of Energetic Reasoning 9

lary (2). A time limit of one hour was enforced for each instance. All

computations were obtained on Dual QuadCore Xeon X5550 2.67 GHz

computers (in 64 bit mode), running Linux, and 24 GB of main memory.

Parameter settings. According to Theorem 2, it suffices to check

for α > 1

/3, whereas αclose to 1

/3would end up in checking most of

the intervals as energetic reasoning does. Due to the outcome we show

results for α∈ {0.5,0.6,0.7,0.8,0.9,1.0,1.1,1.2}. Starting with an initial

setting ‘0.0’, i.e., the pure energetic reasoning, we evaluate the different

parameter settings of α, yielding settings from ‘0.5’ to ‘1.2’.

Evaluation of all instances. Table 1 shows aggregated computational re-

sults for all instances from the test sets j30 and j60 that are solved by at

least one algorithm. The pure energetic reasoning algorithm, which cor-

responds to a factor α= 0.0 serves as reference solver, ‘0.0’. For j30, 473

instances can be solved by at least one solver, pure energetic reasoning has

eight timeouts on these, see column ‘limit’. Choosing α= 0.8 or 0.9 solves

all 473 instances, whereas a smaller or larger value decreases the number

of solved instances. Column ‘better’ tells how many instances are solved

more than 10% faster than by the reference solver. Respectively, ‘worse’

expresses how often a solver is more than 10% slower than the reference

setting ‘0.0’. Here, α= 0.9 performs best. Since some instances timed

out, we show how often better (‘bobj’) or worse (‘wobj’) primal bounds

are found. Using a weak propagation (α= 1.2) yields worst results since

30 instances are not solved, 110 are more than 10% slower and for 13

instances a worse primal bound is found.

For test set j60, best results are gained for α= 0.9. Though, there is

one more timeout than by the reference solver, in twice as many cases the

restricted version is at least 10% faster than pure energetic reasoning.

Evaluation of all optimal solved instances. Since many instances are un-

solved or trivial, Table 2 presents the results only on those instances that

(i) could be solved to optimality by all solvers, (ii) at least one solver

needed more that one search node, and (iii) at least one solver needed

more that one second of computation time. That means, we exclude all

easy instances and those which none of the solver was able to solve. In

case of the test sets j30 and j60 we are left with 112 and 32 instances,

respectively.

Columns ‘better’ and ‘worse’ reveal that values α= 0.9 and 1.0 are

dominating. Column ‘shnodes’ and ‘shtime’ state the shifted geomet-

10 Timo Berthold, Stefan Heinz, Jens Schulz

Table 1. Overview for 473 instances from j30 and 397 instances from j60. Only those

instances are considered that are solved by at least one solver.

j30 j60

αsolved limit better worse bobj wobj solved limit better worse bobj wobj

0.0 465 8 – – – – 393 4 – – – –

0.5 467 6 69 77 3 1 387 10 43 45 1 6

0.6 471 2 81 64 3 0 388 9 45 43 1 5

0.7 472 1 89 53 3 0 388 9 49 37 1 4

0.8 473 0 94 51 3 0 391 6 55 34 1 3

0.9 473 0 105 40 3 0 392 5 59 30 1 4

1.0 472 1 102 40 3 1 392 5 57 31 1 3

1.1 465 8 72 84 3 4 375 22 45 39 1 19

1.2 443 30 52 110 3 13 358 39 38 56 1 35

Table 2. Overview on those instances (i) which are solved with all settings, (ii) where

at least one solver needed more than one search node, and (iii) at least one solver

needed more than one second. This results in 112 instances for the j30 test set and 32

for the j60 test set.

j30 j60

αbetter worse shnodes shtime better worse shnodes shtime

0.0 – – 314 12.7 – – 171 8.5

0.5 49 54 1664 16.1 8 17 1098 16.4

0.6 54 45 1676 10.8 10 15 1005 11.0

0.7 59 33 1679 7.6 11 13 1102 9.0

0.8 60 35 1883 6.3 14 11 1237 6.8

0.9 66 28 2174 5.1 17 9 1240 4.9

1.0 66 24 2895 5.3 16 9 1274 3.4

1.1 47 56 10336 14.4 15 9 2271 6.6

1.2 34 74 52194 54.4 10 20 18050 30.9

ric mean3of all nodes and of the running time, respectively. Table 2

shows that the pure energetic reasoning needs by far the fewest number

of nodes. For each instance of the parametric algorithm the number of

nodes increases by at least a factor of 5. The more we relax the value of α

from 0.5 to 1.2, the more nodes are needed. Besides that, a weak prop-

agation (α= 1.2) behaves worst in all columns. The best running times

are gained with values 0.9 and 1.0 for α. In these cases the restricted

energetic reasoning was more than twice as fast as the pure energetic

reasoning algorithm. This is illustrated in Figure 2, which shows how the

shifted geometric running times vary with different values of α.

3The shifted geometric mean of values t1,...,tnis defined as `Q(ti+s)´1/n −swith

shift s. We use a shift s= 10 for time and s= 100 for nodes in order to decrease

the strong influence of the very easy instances in the mean values.

An Approximative Criterion for the Potential of Energetic Reasoning 11

settings

shifted time [sec]

0.0 0.5 0.6 0.7 0.8 0.9 1.0 1.1 1.2

(a) Running times of test set j30.

settings

shifted time [sec]

0.0 0.5 0.6 0.7 0.8 0.9 1.0 1.1 1.2

(b) Running times of test set j60.

Fig. 2. Comparison of running times from Table 2.

5 Conclusions

We presented a necessary condition for energetic reasoning to detect in-

feasibilities or to derive variable bound adjustments. This result was in-

corporated into a parametrical adjustable version of energetic reasoning.

By checking this condition, we only apply this powerful but expensive

algorithm, when the estimated energy is above a certain threshold α.

Computational results revealed that choosing αclose to 1.0 can speed

up the search by a factor of two though the number of nodes drastically

increases.

References

1. P. Baptiste, C. Le Pape, and W. Nuijten,Constraint-based scheduling: applying

constraint programming to scheduling problems, International Series in Operations

Research & Management Science, 39, Kluwer Academic Publishers, Boston, MA,

2001.

2. T. Berthold, S. Heinz, M. E. L¨

ubbecke, R. H. M¨

ohring, and J. Schulz,A

constraint integer programming approach for resource-constrained project scheduling,

in Integration of AI and OR Techniques in Constraint Programming for Combina-

torial Optimization Problems, A. Lodi, M. Milano, and P. Toth, eds., vol. 6140 of

Lecture Notes in Computer Science, Springer Berlin / Heidelberg, 2010, pp. 313–

317.

3. J. Blazewicz, J. K. Lenstra, and A. H. G. R. Kan,Scheduling subject to

resource constraints: classification and complexity, Discrete Applied Mathematics,

5 (1983), pp. 11 – 24.

4. U. Dorndorf, T. Phan-Huy, and E. Pesch,A survey of interval capacity con-

sistency tests for time- and resource-constrained scheduling, J. Weglarz, Kluwer

Academic, Boston, MA, 1999, ch. 10, pp. 213–238.

5. L. Hidri, A. Gharbi, and M. Haouari,Energetic reasoning revisited: application

to parallel machine scheduling, Journal of Scheduling, 11 (2008), pp. 239–252.