Wohle , Lena Sophie; Zimme mann, Jü gen
A icle — Published Ve sion
Resou ce o e load p oblems wi h a diness penal y:
s uc u al p ope ies and solu ion app oaches
Annals o Ope a ions Resea ch
P o ided in Coope a ion wi h:
Sp inge Na u e
Sugges ed Ci a ion: Wohle , Lena Sophie; Zimme mann, Jü gen (2024) : Resou ce o e load p oblems
wi h a diness penal y: s uc u al p ope ies and solu ion app oaches, Annals o Ope a ions
Resea ch, ISSN 1572-9338, Sp inge US, New Yo k, NY, Vol. 338, Iss. 1, pp. 151-172,
h ps://doi.o g/10.1007/s10479-023-05789-2
This Ve sion is a ailable a :
h ps://hdl.handle.ne /10419/315291
S anda d-Nu zungsbedingungen:
Die Dokumen e au EconS o dü en zu eigenen wissenscha lichen
Zwecken und zum P i a geb auch gespeiche und kopie we den.
Sie dü en die Dokumen e nich ü ö en liche ode komme zielle
Zwecke e iel äl igen, ö en lich auss ellen, ö en lich zugänglich
machen, e eiben ode ande wei ig nu zen.
So e n die Ve asse die Dokumen e un e Open-Con en -Lizenzen
(insbesonde e CC-Lizenzen) zu Ve ügung ges ell haben soll en,
gel en abweichend on diesen Nu zungsbedingungen die in de do
genann en Lizenz gewäh en Nu zungs ech e.
Te ms o use:
Documen s in EconS o may be sa ed and copied o you pe sonal
and schola ly pu poses.
You a e no o copy documen s o public o comme cial pu poses, o
exhibi he documen s publicly, o make hem publicly a ailable on he
in e ne , o o dis ibu e o o he wise use he documen s in public.
I he documen s ha e been made a ailable unde an Open Con en
Licence (especially C ea i e Commons Licences), you may exe cise
u he usage igh s as speci ied in he indica ed licence.
h p://c ea i ecommons.o g/licenses/by/4.0/
Annals o Ope a ions Resea ch (2024) 338:151–172
h ps://doi.o g/10.1007/s10479-023-05789-2
ORIGINAL RESEARCH
Resou ce o e load p oblems wi h a diness penal y:
s uc u al p ope ies and solu ion app oaches
Lena Sophie Wohle 1·Jü gen Zimme mann1
Recei ed: 7 Decembe 2022 / Accep ed: 11 Decembe 2023 / Published online: 16 Janua y 2024
© The Au ho (s) 2024
Abs ac
In his pape , we conside a esou ce o e load p oblem and add a a diness penal y o he
objec i e unc ion when a p esc ibed p ojec makespan is exceeded, which enables a ade-
o be ween a balanced esou ce u iliza ion and a p ojec delay. Fo he a diness penal y,
we dis inguish be ween a cons an and a iable delay cos a ian . Based on he s uc u al
p ope ies o he esou ce o e load p oblem, we show ha he sea ch space o he esou ce
o e load p oblem wi h a diness penal y can also be educed u ilizing quasis able schedules.
In addi ion, we discuss he applica ion o hese indings o u he p oblems, which include
objec i es composed o a locally conca e and a conca e unc ion o a ewa d s uc u e o an
ea ly p ojec comple ion ins ead o a a diness penal y. As solu ion app oaches, we p esen
mixed-in ege linea model o mula ions as well as a no el gene ic algo i hm wi h a decoding
p ocedu e, which exploi s he de ised s uc u al p ope ies. The pe o mance o he gene ic
algo i hm is imp o ed by implemen ing lea ning me hods and u ilizing lowe bounds. Finally,
we p esen esul s om expe imen s on small o medium sized p oblem ins ances.
Keywo ds P ojec scheduling ·Resou ce o e load ·Ta diness penal y ·Quasis able
schedules ·Gene ic algo i hm
1 In oduc ion
Ins ances o he esou ce o e load p oblems o en a ise when cos ly luc ua ions in esou ce
u iliza ion a e o be minimized and a maximum p ojec du a ion is gi en. Howe e , as he
scheduling o p ojec s is an inhe en mul i-objec i e op imiza ion p oblem, he exceeding o
he p esc ibed p ojec makespan can be allowed a addi ional cos . This enables a ade-o
be ween a mo e balanced esou ce u iliza ion and a p ojec comple ion delay o achie e a
mo e cos and esou ce e icien ou come. These addi ional cos may ep esen oppo uni y
BLena Sophie Wohle
[email p o ec ed]
Jü gen Zimme mann
[email p o ec ed]
1Ins i u e o Managemen and Economics, Claus hal Uni e si y o Technology, Julius-Albe -S . 2,
38678 Claus hal-Zelle eld, Ge many
123
152 Annals o Ope a ions Resea ch (2024) 338:151–172
cos o u he o de s, an ea lie ma ke en y, o al e na i ely a diness penal ies o missed
deadlines (Schnabel e al., 2018).
Fo he esou ce o e load p oblem and o he esou ce le elling p oblems se e al mixed-
in ege linea models a e p esen ed in Rieck e al. (2012) and Rieck and Zimme mann
(2015). To sol e he esou ce o e load p oblem heu is ically, Balles in e al. (2007) p opose
a popula ion-based g eedy algo i hm ha cons uc s quasis able schedules, among which
he e is a leas one op imum. Schnabel e al. (2018) conside a esou ce-cons ained p ojec
scheduling p oblem whe e he objec i e includes e enues, which dec ease wi h an inc eas-
ing makespan, as well as esou ce o e load cos . They obse e ha o his p oblem, unlike
he esou ce o e load p oblem, he e is no always an op imum among he quasis able sched-
ules, which would allow o a sea ch space educ ion. To sol e he p oposed p oblem, hey
p esen a gene ic algo i hm wi h di e en ep esen a ions based on an ac i i y lis and ei he
a maximum allowable o e load pe esou ce o pe ac i i y. A an and E en (2018) discuss he
impac o elaxing a p esc ibed p ojec makespan a no addi ional cos o di e en esou ce
le elling p oblems o iden i y he minimum p ojec du a ion o he bes le elled schedule.
As an heu is ic, he au ho s use he popula ion-based app oach o Balles in e al. (2007)bu
do no es o e he quasis ableness o he schedules. In Kim e al. (2005), he p ojec du a ion
is ex ended s epwise in inc emen s o one ime uni o de e mine di e en schedules o a
p ojec manage o decide om. Hegazy (1999) p esen objec i es ha conside he sum o
he p ojec du a ion and a esou ce le elling me ic, which can be weigh ed. Koulinas and
Anagnos opoulos (2012) o malize he app oach o Hegazy (1999) u he by in oducing
a ade-o coe icien o weigh he cos ac o s in he objec i e unc ion. Ponz-Tienda e
al. (2013) p esen an adap i e gene ic algo i hm o a esou ce le elling p oblem in which
exceeding he p esc ibed p ojec makespan is allowed wi h a a diness penal y ha inc eases
linea ly wi h he p ojec ex ension. In Ha mann and B isko n (2022), an o e iew o u -
he inco po a ions o makespan-dependen cos and espec i ely he minimiza ion o he
p ojec makespan in o a ious p ojec scheduling p oblems is gi en. Fo ins ance, Shad okh
and Kian a (2007) and Ge ha ds and S ü ck (2018) conside a esou ce in es men p oblem
wi h a diness penal y. An o e iew o he discussed li e a u e ela ed o esou ce le elling
isgi eninTable1, ocusing on he u ilized objec i e unc ion and solu ion app oach.
In his pape , we discuss he esou ce o e load p oblem wi h di e en a ian s o a -
diness penal ies. The la e applies i a p esc ibed p ojec makespan is exceeded, whe eby
a dis inc ion is made be ween cons an and a iable cos o each ime uni o delay. We
close he esea ch gap ou lined in Schnabel e al. (2018) by p oo ing ha he p oblem can
be di ided in o subp oblems o which he e is a leas one op imum among he quasis able
schedules. As a esul , he sea ch space can be educed, and in mos cases only a conside ably
smalle subse o schedules needs o be in es iga ed in o de o ob ain an op imal solu ion.
The indings ob ained a e o pa icula impo ance since hey also apply o o he bi-objec i e
p oblems whose objec i e unc ion is a weigh ed sum o a locally conca e unc ion and
a conca e unc ion. Besides mixed-in ege linea model o mula ions, we p esen a no el
gene ic algo i hm wi h a decoding p ocedu e, which cons uc s only solu ions wi hin he
de i ed se o quasis able schedules o di e en p ojec du a ions. In addi ion, he solu ion
ep esen a ion indica es a s a ime selec ion ule o each ac i i y and wo lea ning me hods
a e inco po a ed in he algo i hm. We con ibu e a pa ame iza ion o he esou ce o e load
p oblem wi h a diness penal y and es he wo solu ion app oaches on small o medium
sized p oblem ins ances.
This pape is o ganized as ollows: Sec . 2is de o ed o he p oblem desc ip ion o he
esou ce o e load p oblem wi h a diness penal y. Some s uc u al p ope ies o he basic
esou ce o e load p oblem a e p esen ed in Sec .3and a e adap ed o conside a diness
123
Annals o Ope a ions Resea ch (2024) 338:151–172 153
Table 1 O e iew o ele an li e a u e
Fi s au ho Yea Objec i e Solu ion app oaches
RL RL + TP RV – ROP MIP GA POP w. QS
Hegazy 1999
Kim 2005 *
Balles in 2007
Koulinas 2012
Rieck 2012
Ponz-Tienda 2013
Rieck 2015
A an 2018 *
Schnabel 2018
RL: Resou ce le elling (including esou ce o e load), TP: Ta diness penal y, RV: Re enue
MIP: Mixed-in ege linea p og am, GA: Gene ic algo i hm, POP w. QS: Popula ion based app oach wi h
quasis able schedules
* di e en p ojec makespans a e in es iga ed
penal y, oo. The applica ion o hese indings o o he (bi-objec i e) p oblems is discussed in
Subsec ion 3.4. In Sec .4, ma hema ical model o mula ions a e p esen ed. Sec ion5in o-
duces ou no el gene ic algo i hm. We es he solu ion app oaches in expe imen s, which
a e desc ibed in Sec .6and he pape is concluded in Sec . 7.
2 P oblem desc ip ion
We assume ha a p ojec consis s o a se o ac i i ies V, whe e each ac i i y i∈Vis assigned
a p ocessing ime pi≥0 ha canno be in e up ed. Among he ac i i ies, he e a e n eal
ac i i ies and wo ic i ious ac i i ies 0 and n+1 wi h p0=pn+1=0 co esponding o he
p ojec s a and comple ion. The s a ime o ac i i y iis gi en by Si≥0, whe e he p ojec
s a is assumed o be scheduled a ime ze o (S0=0). Mo eo e , he comple ion ime o
an ac i i y iis de ined as Ci:= Si+pi. Be ween he s a imes o wo ac i i ies iand j,
gene al empo al cons ain s Sj−Si≥δij a e assumed wi h δij ∈R. A minimum ime lag
be ween he s a o ac i i y iand japplies i δij ≥0, whe eas δij <0 deno es a maximum
ime lag. Among he maximum ime lags, he maximum p ojec du a ion d(speci ying he
unde lying planning ho izon) is desc ibed by a empo al cons ain om p ojec comple ion
o p ojec s a S0−Sn+1≥−d. Fo each ac i i y ian ea lies s a ime ES
iand la es
s a ime LS
ican be compu ed by means o some longes pa h algo i hm (Ahuja e al.,
1993), om which he o al loa TF
i:= LS
i−ES
io each ac i i y ican be de i ed.
A schedule S=(S0,S1,...,Sn+1)con ains a sequence o s a imes, which a e o de ed
acco ding o he numbe ing o he ac i i ies. To isualize he p ojec , we use an ac i i y-on-
node ne wo k N=(V,E,δ), whe e he p ocessing ime piis gi en abo e each node i∈V
and an a c i,j∈Edepic s a minimum o maximum ime lag δij.
A schedule ha sa is ies all he empo al cons ain s is e med ime- easible and he se o
hose schedules is deno ed as ST. The se o enewable esou ces, which a e u ilized o ca y
ou he ac i i ies, is ep esen ed by R. Each ac i i y iis assigned a esou ce u iliza ion ik ≥0
o each esou ce k∈R, which a e lis ed below he espec i e ac i i y in he p ojec ne wo k
N. The esou ce unc ion k(S,·)o a schedule Sand a esou ce kis a s epwise unc ion,
123
154 Annals o Ope a ions Resea ch (2024) 338:151–172
Fig. 1 Ac i i y-on-node p ojec ne wo k
which compu es he sum o he esou ce u iliza ion o e e y ac i e ac i i y a poin in ime
∈R≥0. An ac i i y iis ac i e i he cu en ime is g ea e o equal o he s a ime Siand
less han Ci. A esou ce p o ile isualizes he esou ce unc ion k(S,·) o a gi en esou ce
k∈Rand schedule Sin dependence o . The esou ces a e assumed o be uncapaci a ed.
Howe e , a esou ce h eshold Ykis de ined o each esou ce k∈R om which posi i e
de ia ions in he esou ce u iliza ion k(S, )a any poin in ime a e penalized.
Example 1 Figu e1depic s an ac i i y-on-node ne wo k which con ains h ee eal ac i i ies
and one enewable esou ce. The ea lies p ojec comple ion is 10 and he maximum p ojec
du a ion dis limi ed o 14. Ac i i y 2 has only one easible s a ime S2=1 and ac i i y 3
has o be scheduled a S3=6. Only ac i i ies 1 and 4 ha e a o al loa g ea e han ze o.
The objec i e o he basic esou ce o e load p oblem coincides wi h he cumula i e cos o
posi i e de ia ions om he esou ce h esholds Yk. The posi i e de ia ions o each esou ce
can be weigh ed di e en ly by cos ac o s ck∈R>0.
ROP(S)=
k∈R
ck
∈[0,d]
( k(S, )−Yk)+d
The esou ce o e load p oblem is o de e mine an op imal schedule ha minimizes he objec-
i e unc ion ROP while sa is ying he empo al cons ain s. I can be o mula ed as ollows:
Minimize ROP(S)
subjec o Sj−Si≥δij i,j∈E
S0=0
Si≥0i∈V
As he e a e no o he cons ain s such as esou ce capaci ies, he se o ime- easible
schedules equals he se o easible schedules i.e. S=ST.
Fo he esou ce o e load p oblem wi h a diness penal y, we assume ha besides a max-
imum p ojec du a ion da p esc ibed p ojec makespan T∈[ES
n+1,d]is gi en. Tcan be
exceeded a addi ional cos TP, which is added o he objec i e unc ion (Ponz-Tienda e
al., 2013; Shad okh & Kian a , 2007).
(S)= ROP(S)+ TP(S)
He e, we assume ha he p esc ibed p ojec makespan Tand he maximum p ojec du a ion
da e posi i e in ege s. Addi ionally, we suppose ha an inc ease in a diness penal y only
occu s wi h each whole uni o ime and no wi h each a bi a ily small delay. Fi s , he delay
123
Annals o Ope a ions Resea ch (2024) 338:151–172 155
Fig. 2 Ta diness penal y unc ion
wi h a cons an delay cos ac o
ρ=1
Fig. 3 Ta diness penal y unc ion
wi h a a iable delay cos ac o
ρ13 =0.5andρ14 =1.25
cos ac o ρ∈R≥0is assumed o be cons an , wi h he alue o TP inc easing linea ly
wi h an addi ional ime uni o be penalized. The esul ing a diness penal y unc ion TP is
piecewise de ined depending on he p ojec comple ion Sn+1and has jump poin s a e e y
in ege ime poin g ea e o equal o T. Mo eo e , TP is lowe semi-con inuous on all
schedules.
TP(S)=0,Sn+1∈ES
n+1,T;
ρ·(a+1), Sn+1∈T+a,T+a+1,a∈0,...,d−T−1.
In ypical eal-wo ld examples, di e en addi ional cos ρ ≥0, ∈{T+1,...,d}
may apply o e e y addi ional ime uni o delay. The esul ing unc ion TP is also lowe
semi-con inuous and mono onically inc easing.
TP(S)=⎧
⎪
⎨
⎪
⎩
0,Sn+1∈ES
n+1;T;
Sn+1
=T+1
ρ ,Sn+1∈T+a;T+a+1,a∈0,...,d−T−1.
Example 2 In he ollowing, an example is gi en o each a diness penal y unc ion a ian .
As in he p ojec ne wo k in Fig.1, a maximum p ojec du a ion o 14 is assumed. Le T=12
be he p esc ibed p ojec makespan. In Fig.2, a a diness penal y unc ion wi h a cons an
delay cos ac o ρ=1 is shown. Figu e 3depic s a a diness penal y cos unc ion wi h
a iable, inc easing, delay cos ac o s.
Rema k 1 The o mula ion o TP can be u he gene alized o cons an and a iable delay
cos . Ins ead o no cos ( TP =0) o Sn+1∈ES
n+1;T, any cons an ρ0∈Rcan be
u ilized. Ob iously, o wo schedules S1and S2wi h TP(S1)< TP(S2), he same holds
e en i he cons an ρ0is conside ed. The gene aliza ion can be used o ep esen a ewa d
s uc u e o an ea ly p ojec comple ion which may only dec ease wi h an inc ease o he
p ojec du a ion like in Schnabel e al. (2018). Howe e , such a unc ion mus be mul iplied
by −1 o sa is y he minimiza ion objec i e.
As shown in Neumann e al. (2003), he basic esou ce o e load p oblem is al eady NP-
ha d in he s ong sense. Thus, he same applies o he esou ce o e load p oblem wi h
a diness penal y. Howe e , inding a easible solu ion is easy, because he ES-schedule is
always easible.
123
156 Annals o Ope a ions Resea ch (2024) 338:151–172
Fig. 4 Resou ce p o ile o
ES =(0,0,1,6,10)
3 S uc u al p ope ies
In his sec ion, we discuss o de -based s uc u al p ope ies and p ope ies o he esou ce
o e load objec i e unc ion. These can be u ilized o educe he sea ch space o he basic
esou ce o e load p oblem, and hen simila ly o a ian s wi h a diness penal y. As
desc ibed in Neumann e al. (2003), a s ic o de ela ion is implica ed i an ac i i y js a s
a e an ac i i y iis comple ed (Sj≥Si+pi). A schedule induced o de O(S)is in oduced o
e e o all s ic o de ela ions be ween pai s o eal ac i i ies (i,j)∈{1,...,n}×{1,...,n}
ha a e me by he schedule S.Le
ST(O(S)) := {S∈ST|Sj≥Si+pi o all (i,j)∈O(S)}
deno e he se o all ime- easible schedules ha sa is y he s ic o de gi en by O(S).A
se o schedules ha induces an iden ical s ic o de as schedule Sis e med equal o de se
S=
T(O(S)). I he s a ime Sio a leas one ac i i y iis shi ed o wa d o backwa d om
a ime easible schedule S, esul ing in a non-iden ical and ime- easible schedule S, his
mo emen is e e ed o as a shi . An o de p ese ing shi desc ibes a shi om a schedule
S o ano he easible schedule Ssuch ha he o de o he ini ial schedule is p ese ed
(O(S)⊇O(S)). Two shi s ha ans o m a schedule Sin o a schedule Sand a schedule
S a e called a pai o opposi e shi s i S −S=λ(S−S)wi h λ<0 holds. A easible
schedule Sis said o be quasis able i he e is no pai o opposi e o de p ese ing shi s.
3.1 Resou ce o e load p oblem
The unc ion ROP is con inuous and hus also lowe semi-con inuous. Mo eo e , he unc ion
is conca e on each equal o de se , deno ed as locally conca e. Neumann e al. (2003)
p oo ha he e is always a quasis able schedule among he op ima o unc ions ha a e
locally conca e. A quasis able schedule Shas use ul s uc u al p ope ies: Fo he s a ime
o each ac i i y i∈V, he e is always an ac i i y j∈V o which ei he a p ecedence
ela ionship Sj=Si+pio Sj=Si−pjo a empo al cons ain Sj=Si+δij o
Sj=Si−δji is binding (Neumann e al., 2003). I δij ∈Z(including d), pi∈N0and
ST=∅, quasis able schedules con ain only in ege s a imes. Since he e is always an
op imum among quasis able schedules, he e is also always an in ege op imum solu ion.
The e o e, he ime ho izon can be disc e ized o he esou ce o e load p oblem wi hou
loss o solu ion quali y. In he ollowing, we assume ha he empo al inpu ul ills he abo e
men ioned condi ions. In addi ion, i only one enewable esou ce is used in an example, he
co esponding indices a e omi ed.
Example 3 We conside again he p ojec depic ed in Fig.1. The esou ce p o ile o he ES-
schedule is displayed in Fig.4.TheES-schedule induces he o de O(ES)={(1,3), (2,3)}.
In Fig.5, ROP is depic ed in dependence o he s a ime S1o ac i i y 1 whe e he cos pe
esou ce o e load uni is assumed o be c=1 and he esou ce h eshold is se o be Y=1.
I is ob ious ha he minimum o ROP(S1)is a S1=10. In he same igu e, he di e en
123
Annals o Ope a ions Resea ch (2024) 338:151–172 157
Fig. 5 Resou ce o e load
unc ion, schedule induced
o de s, equal o de se s and
quasis able schedules
Fig. 6 Resou ce o e load
unc ion wi h a cons an delay
cos ac o
induced o de s a e highligh ed in di e en shades depending on he s a ime o ac i i y 1.
Since iden ical schedule induced o de s belong o he same shade o g ay, hei espec i e
equal o de se s a e he union o all schedules ma ked wi h he same shade. I can be seen
ha he esou ce o e load unc ion is conca e on equal o de se s. The quasis able schedules
a e ma ked wi h do s, which include he minimum o he unc ion ROP.
3.2 Cons an delay cos ac o
In his subsec ion, we discuss s uc u al p ope ies o he esou ce o e load p oblem wi h a
cons an delay cos ac o .
Example 4 We conside again he p ojec depic ed in Fig. 1.Fo TP, a cons an delay cos
ac o ρ=c=1 is assumed o e e y addi ional ime uni o delay when he p esc ibed
p ojec makespan o T=12 is exceeded (see Fig.2). In con as o he esou ce o e load
unc ion in Fig.5, ROP can also be isualized as a unc ion o he comple ion C1o ac i i y
1. This is use ul he e because he comple ion o ac i i y 1 and he p ojec comple ion Sn+1
coincide i ac i i y 1 comple es a ime 6 o la e . Mo eo e , ac i i y 1 is he only eal ac i i y
ha can be shi ed. As a esul , TP and hus can also be ep esen ed as a unc ion o
C1in his speci ic example. In Fig.6, he cou se o unc ion is depic ed. The quasis able
schedules a e ma ked in ligh g ay. I can be seen ha he minimum o he combined objec i e
unc ion is eached when ac i i y 1 ends a 12, which is he p esc ibed p ojec makespan
T. Howe e , his schedule is no a quasis able schedule.
In he ollowing, we p o ide an ex ension o he se o quasis able schedules ha con ains
a leas one op imum o esou ce o e load p oblems wi h a cons an delay cos ac o . This
se is ob ained by di iding he p oblem in o wo subp oblems based on di e en minimum
and maximum p ojec du a ions and de e mining he se o quasis able schedules o bo h
subp oblems.
Theo em 1 Gi en a esou ce o e load p oblem wi h a cons an delay cos ac o P, wo
subp oblems Pand P can be cons uc ed. The se o easible schedules o subp oblem P
123
158 Annals o Ope a ions Resea ch (2024) 338:151–172
is u he limi ed by an adjus ed maximum p ojec du a ion o T . The se o easible schedules
o he second subp oblem P is u he limi ed by a minimum p ojec du a ion o T . Among
he quasis able schedules o he wo subp oblems Pand P, he e is a leas one op imal
solu ion o P.
P oo A esou ce o e load p oblem wi h a cons an delay cos ac o can be di ided in o
wo subp oblems. Fo he i s subp oblem, a maximum p ojec du a ion o Tapplies. This
subp oblem has a se o easible schedules ST,≤T, all o which ha e no a diness penal y.
The e o e, his subp oblem is a basic esou ce o e load p oblem and among he se o i s
quasis able schedules, he e is a leas one o i s op ima. The second subp oblem has a
minimum p ojec du a ion o Tand a maximum p ojec du a ion o d. The connec ed se
o ime- easible schedules ST,≥Tcon ains schedules S∈STwi h a p ojec du a ion o
T≤Sn+1≤d. The equal o de se s o his subp oblem a e deno ed as
S=
T(O(S))≥T:= S=
T(O(S)) ∩S∈ST:S
n+1≥T.
On he equal o de se s S=
T(O(S))≥T, he esou ce o e load unc ion ROP is s ill conca e.
Howe e , o his subp oblem he combined objec i e unc ion is no equal o ROP because
he alues o he a diness penal y unc ion TP can be g ea e han ze o. To ne e heless
de e mine schedules ha minimize in his subp oblem, he auxilia y unc ion his de ined
o S∈STwi h Sn+1≥T.
h(S)=ρ·Sn+1−T
The unc ion TP is he ceiling unc ion o hwi hin he discussed subp oblem. The e o e,
hunde es ima es he alue o TP a e e y poin in ime ∈[T,d]by a alue wi hin he
in e al [0,1). Mo eo e , unc ions hand TP ha e he same objec i e unc ion alues i he
p ojec makespan Sn+1is an in ege and hus ROP + TP = ROP + h o all schedules
wi h Sn+1∈N. The auxilia y unc ion his conca e and he e o e also locally conca e.
The sum o locally conca e unc ions, he e ROP and h, is again locally conca e. Since
ROP + hunde es ima es and hey ha e he same alue o each schedule wi h only
in ege s a imes, among he quasis able schedules ha sa is y T≤Sn+1≤dis a leas
one op imum o his subp oblem.
Rema k 2 Le Ibe an ins ance o he esou ce o e load p oblem wi h a cons an delay cos
ac o . The p ojec ne wo k No Ican be modi ied o ep esen he empo al cons ain s
o ei he o he wo subp oblems desc ibed. By adding an a c n+1,0wi h he weigh
δn+1,0=−T, he p ojec ne wo k Nis adap ed o he i s subp oblem. Fo he second
subp oblem an a c 0,n+1wi h a weigh o δ0,n+1=Tis added, which indica es a
minimum ime lag and he e o e a minimum p ojec du a ion.
3.3 Va iable delay cos ac o
We now assume ha o e e y addi ional ime uni o delay di e en addi ional a diness
penal y cos ρ ≥0, wi h ∈T+1,...,dapply, which esul s in a mono onically
inc easing penal y unc ion. This unc ion canno be necessa ily unde es ima ed by a linea
unc ion. Mo eo e , i can be seen in Fig. 7 ha he minimum is no among he schedules
desc ibed in Theo em 1. The p oblem is he e o e di ided in o u he subp oblems.
Theo em 2 Gi en a esou ce o e load p oblem wi h a a iable delay cos ac o , he ollowing
subp oblems can be cons uc ed. The subp oblem Phas a se o easible schedules ha is
123
Annals o Ope a ions Resea ch (2024) 338:151–172 165
p ocess o an ac i i y iis comple ed when i is emo ed om he se o unscheduled ac i i ies
Cand inse ed in o he se o comple ed ac i i ies C.I Cis emp y, he algo i hm e mina es.
The esul ing schedule is always easible.
Algo i hm 1 Decoding p ocedu e
1: Se S
0:= 0, ini ialize C:= {0}and C:= V {0}
2: Compu e ES
i:= d0iand LS
i:= −di0,∀i∈C
3: while C=∅do
4: Ini ialize i:= −1and k1,max := −1
5: o h∈Cdo
6: i k1,h> k1,max hen
7: o j∈Cdo
8: i (h,j∈Eand ES
h≤S
j−δhj ≤LS
h)
9: o (j,h∈Eand ES
h≤S
j+δjh ≤LS
h)
10: o (ES
h≤S
j−ph≤LS
h)
11: o (ES
h≤S
j+pj≤LS
h) hen
12: i:= h, k1,max := k1,h.
13: b eak
14: Ini ialize Di:= ∅
15: o j∈Cdo
16: i i,j∈Eand ES
i≤S
j−δij ≤LS
i hen Di:= D∪{S
j−δij}.
17: i j,i∈Eand ES
i≤S
j+δji ≤LS
i hen Di:= D∪{S
j+δji}.
18: i ES
i≤S
j−pi≤LS
i hen Di:= D∪{S
j−pi}.
19: i ES
i≤S
j+pj≤LS
i hen Di:= D∪{S
j+pj}.
20: i i=n+1and cons an delay cos hen
21: Di:= Di∪({ES
n+1,...,LS
n+1}∩{T}).
22: else i i=n+1and a iable delay cos hen
23: Di:= Di∪({ES
n+1,...,LS
n+1}∩{T,...,d−1}).
24: i b2,i=1 hen choose S
i:= a gmin
τ∈Di
( ROP(τ ))
25: else choose τ∈Diacco ding o k3,iand se S
i:= τ
26: Remo e ac i i y i om C, inse ac i i y iin o C
27: o h∈Cdo
28: ES
h:= max(ES
h,S
i+dih),LS
h:= min(LS
h,S
i−dhi)
5.5 Lowe bound o he op imal objec i e unc ion alue
The lowe bound (LB) o he objec i e unc ion alue o he esou ce o e load p oblem
wi h a diness penal y desc ibed in his subsec ion can be used as a e mina ion c i e ion o
he gene ic algo i hm o o he wise as an es ima e o i s solu ion quali y. To compu e LB,
a lowe bound o he cos o esou ce o e load k∈Rckomin
kSn+1can be es ima ed i s o
e e y easible p ojec makespan Sn+1∈{ES
n+1,...,d}, o which he applicable a diness
penal y TP(Sn+1)mus hen be added. O hese alues, he minimum is hen used as he
lowe bound o he op imal objec i e unc ion alue.
LB := min
Sn+1∈{ES
n+1,...,d}
k∈R
ckomin
kSn+1+ TP(Sn+1)
123
166 Annals o Ope a ions Resea ch (2024) 338:151–172
Fig. 8 Resou ce u iliza ion o all
eal ac i i ies a hei easible
execu ion imes o a p ojec
makespan o 12
The e a e se e al ways o de e mine he a iables omin
kSn+1 o each k∈R,o which he
maximum is selec ed. An op ion is o calcula e he o al esou ce u iliza ion o esou ce k
and educe i by he p oduc o he p ojec du a ion Sn+1and he esou ce h eshold Yk.This
lowe bound can be igh ened by de e mining o each ime pe iod ∈{0,...,Sn+1−1} he
sum o esou ce uni s max
k( )u ilized by all eal ac i i ies ha can possibly be in execu ion.
I max
kis below he h eshold Ykin one o mo e pe iods, his may inc ease he esou ce
o e load ha mus occu in he emaining pe iods. A second way o de e mine he minimum
esou ce o e load omin
kSn+1can be o look a he esou ce u iliza ion ik o each ac i i y and
e alua e whe he and how much i exceeds Ykalone du ing i s execu ion.
Example 5 We adjus he p ojec ne wo k shown in Fig. 1by adap ing he minimum ime lag
be ween he p ojec s a 0 and ac i i y 1 o δ01 =1, esul ing in an ea lies s a ES
1=1.
Mo eo e , he minimum and maximum ime lag be ween he s a o ac i i y 2 and he s a
o ac i i y 3 is inc eased o exac ly 6. In his p ojec , he h ee eal ac i i ies ha e a o al
esou ce u ilisa ion o 12 esou ce uni s. Le us conside a p ojec makespan o Sn+1=11.
Calcula ing he minimum esou ce o e load omin
11 by educing he o al esou ce usage by he
esou ce h eshold Y=1 mul iplied by he p ojec du a ion 11 yields in a alue o 1. I we
depic he maximum esou ce uni s max possibly u ilized in each ime pe iod (see Fig. 8),
we see ha in pe iod 0 he maximum esou ce u iliza ion is 0 and hus below he h eshold
Y=1. The minimum esou ce o e load omin
11 he e o e can be adjus ed o 2. This is a igh
lowe bound o a p ojec du a ion o 11 as he op imal esou ce o e load unc ion alue
equals 2 esul ing, o example, om he schedule S=(0,5,1,7,11). The o he a ian
o de e mining omin
k is no ele an he e because none o he ac i i ies alone exceeds he
esou ce h eshold.
6 Expe imen s
In he ollowing sec ion, he pe o mance o he MIP- o mula ion as well as he no el gene ic
algo i hm is in es iga ed. We i s desc ibe how we ex end well-known ins ance se s o inco -
po a e a diness penal y. Then, he pa ame iza ion o he solu ion app oaches is desc ibed.
Finally, we p esen and discuss he esul s o expe imen al esul s o cons an and a iable
delay cos , dis inguishing be ween di e en p esc ibed p ojec makespans and maximum
p ojec du a ions.
6.1 Tes design
The compu a ional es s a e based on he es se s UBO o he RCPSP/max, which we e
ob ained by he p oblem gene a o P oGen/max (Schwind , 1998), c ). E e y es se inco -
po a es 90 ins ances wi h ei he 10, 20, 50 o 100 eal ac i i ies and 5 enewable esou ces.
In addi ion, he es ic i eness o Thesen (RT) is gi en o he ins ances ha measu es he
deg ee o which he o al numbe o easible ac i i y sequences is es ic ed by he p ecedence
123
Annals o Ope a ions Resea ch (2024) 338:151–172 167
ela ionships. I RT = 0, he eal ac i i ies a e all pa allel o each o he . RT = 1 occu s only
o a se ial p ojec ne wo k. Fo he es ins ances, RTs in {0.25,0.5,0.75}a e a ge ed.
In o de o pe o m ou expe imen s, u he pa ame iza ions o he ins ances a e equi ed.
The maximum p ojec du a ion is se wi h a coe icien α>1 od:= αES
n+1. Mo eo e ,
he p esc ibed p ojec makespan Tis ini ialized as T:= βES
n+1whe e 1 ≤β<α.The
esou ce h esholds Yk o all k∈Ra e chosen acco ding o he o al esou ce u iliza ion
and he p esc ibed p ojec makespan Tins ead o he maximum p ojec du a ion used in
Neumann e al. (2003)(Yk:= i∈V ik ·pi/T,k∈R). We assume ha he cos ac o
ck o each o e load uni o esou ce kis 1. To calcula e he a diness penal y, a ac o γ
is in oduced. The cons an delay cos ac o ρis hen calcula ed as ρ:= γk∈RYk.To
es he solu ion app oaches wi h a iable delay cos ac o s, mono onically inc easing cos
ac o s ρ a e chosen.
ρ := ⎧
⎨
⎩
γ·
k∈R
Yk·(1+γ)
( −T), >T;
0, ≤T.
We use C++ in he Mic oso Visual S udios 2022 de elopmen en i onmen o implemen
he mixed-in ege linea models and he gene ic algo i hm. Fo he MILPs he sol e IBM
ILOG CPLEX 20.1 is u ilized. Fo CPLEX, he ime limi is se o be 1800s o all ins ances.
P elimina y esul s ha e shown ha p o iding he p e iously desc ibed lowe bound o he
sol e does no imp o e he un ime o he bes objec i e unc ion alue o e all. The pa am-
e e s o he gene ic algo i hm a e chosen as ollows: he popula ion size is se acco ding o
he numbe o eal ac i i ies in he ins ance o be 2n. The p opo ion o eli is indi iduals
is de ined as 0.35 o he popula ion size. The c osso e p obabili y is se o be 0.7 and he
mu a ion p obabili y as 0.1. Fo small ins ances wi h n=10, he gene ic algo i hm uns un il
K-i e a ions wi hou an imp o emen o he bes objec i e unc ion alue a e pe o med.
We choose K:= 500. Fo la ge ins ances, a ime limi is se . Fo ins ances wi h n=20,
he un ime is limi ed o 30s, o n=50 and n=100 o 300s. The gene ic algo i hm
is e mina ed ea ly i he bes objec i e unc ion alue equals he calcula ed lowe bound.
P elimina y uns ha e shown ha he wo lea ning me hods (opposi ion-based lea ning and
adap ing mu a ion p obabili ies) lead o a be e o e all esul o ins ances wi h 50 o mo e
ac i i ies. The e o e, he lea ning me hods a e only applied o hese ins ances. To c ea e an
ini ial popula ion o smalle ins ances, only he i s s ep desc ibed in Sec .5.2 is pe o med.
To adjus he mu a ion p obabili ies in case o n=50 and n=100, he numbe o analysed
solu ions is se o l:= 3 and he scaling ac o o s:= 4.
Fo he i s expe imen s, he maximum p ojec du a ion is se using α:= 1.25. In o de
o examine he in luence o di e en p esc ibed p ojec makespans, we sol e he ins ances
wi h β∈{1.0,1.1}. To de e mine γ, p elimina y CPLEX uns a e pe o med o ins ances
wi h 10 ac i i ies, whe e op imali y can always be p o en in a sho ime o each ins ance
solu ion. Howe e , uns wi h γ=0.3 o he esou ce o e load p oblem wi h a cons an delay
ac o and γ=0.1 o a iable delay cos ac o s ha e a sligh ly highe a e age un ime
in con as o o he pa ame iza ions. Mo eo e , i is obse ed ha he p ojec du a ions o
he op imal schedules a e compa a i ely widely sca e ed ac oss ins ances compa ed o o he
pa ame iza ions. The e o e, γ. =0.3 o he esou ce o e load p oblem wi h a cons an
delay ac o and γ:= 0.1 o a iable delay cos ac o s is in es iga ed o all ins ance sizes.
123
168 Annals o Ope a ions Resea ch (2024) 338:151–172
Table 2 Resou ce o e load p oblem wi h a cons an delay cos ac o wi h α=1.25
Ins ances CPLEX Gene ic algo i hm
αβγn#op ∅gap ∅ op [s]∅gap ∅ ga[s]∅ss
1.25 1.0 0.3 10 90 0 0.92 0.35 0.59 23.36
20 79 1.17 149.71 0.76 30.00 19.90
50 0 44.22 −− −6.68 300.02 20.72
100 0 60.92 −− −13.42 300.14 17.55
1.25 1.1 0.3 10 90 0 1.00 0.14 0.81 23.61
20 82 0.82 160.86 0.51 29.15 20.39
50 0 38.62 −− −4.34 300.02 21.25
100 0 60.16 −− −21.25 300.12 17.51
6.2 Resul s
All o he es s we e conduc ed on compu e s wi h 64 GB RAM and an In el(R) Co e(TM)
i7-7700K wi h 4x4.20 GHz and 8 h eads. The esul s p o ide he numbe o ins ances pe
es se which a e sol ed o op imali y and i s op imali y is p o en (#op ) and he a e age
gap o e all ins ances (∅gap) achie ed by CPLEX. The a e age un ime o he ins ances
coun ed in #op is deno ed as ∅ op and is measu ed in seconds. To in es iga e he quali y
o he gene ic algo i hm, he a e age ela i e gap (∅gap ), which is calcula ed in ega ds
o he bes objec i e unc ion alue ob ained by CPLEX, is depic ed. The a e age un ime
in seconds o he gene ic algo i hm is deno ed as ∅ ga. To ob ain an es ima e o he sea ch
space educ ion, he numbe o s a imes wi hin he decision se |Di|is compa ed o he
numbe o easible s a imes LS
i−ES
i+1 o each ac i i y i∈V {0}and he a e age
o e all solu ions in all gene a ions wi hin a es se is deno ed as ∅ss.
6.2.1 Cons an delay cos
Table 2summa izes he esul s o he esou ce o e load p oblem wi h a cons an delay
cos ac o , whe e we di e en ia e be ween wo men ioned p esc ibed p ojec makespan
pa ame iza ions, which also lead o di e en esou ce h esholds. Fo all o he ins ances
wi h 10 ac i i ies, an op imal solu ion is ound and i s op imali y is p o en by CPLEX in
unde 11s. Mo eo e , o he majo i y o ins ances wi h 20 ac i i ies (90 %) he sol e
de e mines an op imum wi hin hal an hou and ∅ op is o bo h di e en p esc ibed p ojec
makespan pa ame iza ions ela i ely equal. As we expec ed, he solu ion quali y o he sol e
dec eases wi h an inc easing numbe o ac i i ies. CPLEX could no p o e he op imali y
o any o he ins ances wi h 50 o 100 ac i i ies and he a e age gap is app oxima ely 40%
o n=50 and 60% o n=100 a e hal an hou o un ime o bo h β.Howe e , he
gap a ies signi ican ly ac oss he ins ances. The gap is conside ably la ge han he a e age
o ins ances wi h a a he pa allel ne wo k (RT ≈0.25), whe eby o mo e se ial ne wo ks
wi h RT ≈0.75 he gap is signi ican ly smalle . Fo he es se s wi h 50 o 100 ac i i ies,
he co ela ion coe icien s o RT and he sol e gap lie in he ange o −0.8 o −0.7.
The las columns o Table 2 e eal he pe o mance esul s o he gene ic algo i hm. On
ins ances wi h n=10 and n=20, he gene ic algo i hm pe o ms simila ly well as CPLEX.
Bu especially o ins ances wi h 20 ac i i ies, he a e age un ime ∅ ga is signi ican ly
sho e . An ea ly e mina ion due o eaching he calcula ed lowe bound ne e occu s o
123
Annals o Ope a ions Resea ch (2024) 338:151–172 169
ins ances wi h a igh p esc ibed p ojec makespan (β=1.0). When se ing β=1.1,
conside ing he calcula ed lowe bound leads o he e mina ion o he gene ic algo i hm 5
imes wi h 10 ac i i ies and 3 imes wi h 20 ac i i ies. All o he a ec ed ins ances ha e a
p ojec du a ion ha does no exceed he p esc ibed p ojec makespan Tand he e o e no
a diness penal y applies. On la ge ins ances wi h 50 ac i i ies, he gene ic algo i hm ob ains
an a e age ela i e gap o −6.68% and −4.34%. Compa ing he solu ion quali y o ins ances
wi h 100 ac i i ies, he gene ic algo i hm ob ains on a e age signi ican ly be e esul s han
CPLEX wi hin a signi ican ly sho e un ime. Wi h a igh p esc ibed p ojec makespan
(β=1.0), CPLEX only ob ains a be e solu ion o 5 ou o 90 ins ances. Wi h β=1.1 his
is only he case o one ins ance.
Conside ing he a e age sea ch space size ∅ss, i is e iden ha he gene ic algo i hm
only conside s a small subse o easible s a imes and hus a sea ch space educ ion is in
place. The alues o ∅ss o bo h p esc ibed p ojec makespan pa ame iza ions a e simila ,
al hough no sepa a e conside a ion o Tas he p ojec makespan is necessa y o β=1.0in
con as o β=1.1. In addi ion, we in es iga e he a e age o he bina y alues b2,i o all
i∈V {0} o he bes solu ion ob ained o each ins ance, in o de o d aw conclusions abou
he s a ime selec ion ules. The a e age a ies widely o ins ances wi h 10 ac i i ies (0.25
o 1.0) and he leas o ins ances wi h 50 and 100 ac i i ies (0.51 o 0.88). In ega ds o he
good pe o mance o he gene ic algo i hm, an objec i e unc ion alue-o ien ed s a ime
selec ion, indica ed by b2,i=1, seems o be app op ia e o he esou ce o e load p oblem
wi h a diness penal y. This is especially he case wi h medium-sized ins ances.
To es he use ulness o opposi ion-based lea ning and mu a ion p obabili y adjus men ,
we conduc uns wi h 50 and 100 ac i i ies whe e we excluded he lea ning me hods. The
esul s show ha o all ou uns he gap is a leas 0.9% highe wi hou hem, wi h he
di e ence being g ea e o ins ance se s wi h 100 ac i i ies, being as high as 3.4%. Wi h
addi ional uns, we obse ed ha he bene i o adap ing mu a ion p obabili ies is a g ea e
han he impac o opposi ion-based lea ning. We ega d his as easonable, since he la e
a ec s only one gene a ion.
6.2.2 Va iable delay cos
In Table 3, he esul s o he expe imen s o he esou ce o e load p oblem wi h a iable delay
cos ac o s pa ame ized wi h γ=0.1, α=1.25 and β∈{1.0,1.1}a e p o ided. Gene ally,
he esul s shown a e simila o he p e ious ones wi h a cons an delay cos ac o . Rega ding
small ins ances, he gene ic algo i hm e mina es ea ly o he same ins ances and he same β
as be o e. As he numbe o ac i i ies inc eases, he supe io i y o gene ic algo i hm is e iden
again. Rega ding he es se wi h 100 ac i i ies and β=1.1, he gene ic algo i hm ob ains
a be e esul han CPLEX o each o he 90 ins ances. Fo a igh e p esc ibed p ojec
makespan (β=1.0), he gene ic algo i hm yields a be e solu ion o 80 ins ances wi hin
300s. As expec ed, he a e age sea ch space is la ge han o he es se s wi h a cons an
delay cos ac o . Howe e , inc easing β om 1.0 o 1.1 esul s in a educ ion o he numbe
o p ojec du a ions, which addi ionally need o be conside ed in he gene ic algo i hm. This
sea ch space educ ion is also e iden om ∅ss. The lowes a e age bina y alue o he bes
solu ion o he ins ances he e is 33%, ob ained o an ins ance wi h n=10 and β=1.1.
Inc easing he numbe o ac i i ies, leads also o an inc ease o he lowes a e age bina y
alue ound in he bes solu ions in bo h es se s up o 0.57. To us, his once again unde lines
he e ec i eness o he wo s a ime selec ion ules conside ed.
123
170 Annals o Ope a ions Resea ch (2024) 338:151–172
Table 3 Resou ce o e load p oblem wi h a a iable delay cos ac o wi h α=1.25
Ins ances CPLEX Gene ic algo i hm
αβγn#op ∅gap ∅ op [s]∅gap ∅ ga[s]∅ss
1.25 1.0 0.1 10 90 0 1.36 0.34 0.60 27.21
20 82 0.98 155.70 0.67 30.00 23.42
50 0 43.57 −− −6.18 300.02 21.79
100 0 59.49 −− −13.54 300.12 21.65
1.25 1.1 0.1 10 90 0 0.85 0.16 0.81 26.68
20 80 0.98 93.88 0.80 29.01 22.23
50 0 39.42 −− −6.20 300.02 21.62
100 0 62.76 −− −28.75 300.13 18.94
Table 4 Resou ce o e load p oblem wi h a cons an delay cos ac o wi h α=1.5
Ins ances CPLEX Gene ic algo i hm
αβγn#op ∅gap ∅ op [s]∅gap ∅ ga[s]∅ss
1.5 1.2 0.1 10 90 0 3.13 0.46 0.46 17.57
20 63 2.57 349.73 1.09 26.03 14.93
50 0 34.52 −− −11.34 300.02 15.57
100 0 59.36 −− −32.82 300.14 12.62
6.2.3 Cons an delay cos wi h a longe ime ho izon
We es he obus ness o he solu ion app oaches by inc easing α:= 1.5 o ins ances wi h
a cons an delay cos ac o (Table 4). We assume ha wi h a longe planning ho izon, he
p esc ibed p ojec makespan al eady allows mo e loa . The e o e, we choose β:= 1.2. To
main ain a sca e ing o op imal p ojec du a ions, γis educed o 0.1. Wi h he inc eased
planning ho izon, bo h app oaches de e io a e on ins ances wi h 10 and 20 ac i i ies, wi h
CPLEX being mo e a ec ed especially ega ding he numbe o op imal solu ions ound
and i s op imali y p o en as well as ∅ op .Fo n=10, he gene ic algo i hm e mina es
16 imes due o eaching he calcula ed lowe bound, which explains he lowes a e age
un ime o n=10 o e all expe imen s. Fo n=20, he gene ic algo i hm e mina es
9 imes ea ly. The espec i e ins ances o bo h numbe s o ac i i ies ha e again a p ojec
du a ion equal o less han T. Ac oss all expe imen s, he bes a e age ela i e gaps (∅gap )
a e ob ained o p oblem ins ances wi h 50 and 100 ac i i ies. Since he numbe o s a
imes conside ed in he gene ic algo i hm depend p ima ily on he numbe o o he ac i i ies
and no on he planning ho izon in con as o he ma hema ical model o mula ion, his
pe o mance imp o emen seems easonable o us. In addi ion, o 83 ins ances con aining
100 eal ac i i ies he calcula ed lowe bound is be e ha he one p o ided by CPLEX. I
his lowe bound is conside ed, he a e age gap o he gene ic algo i hm is 40.46% and hus
nea ly 20% lowe han he a e age gap o CPLEX.
123
Annals o Ope a ions Resea ch (2024) 338:151–172 171
7 Conclusion
In his pape , we ha e shown ha he se o quasis able schedules can be adap ed o educe
he sea ch space o he esou ce o e load p oblem wi h a diness penal y. Besides a mixed-
in ege linea model, we p esen a gene ic algo i hm wi h a decoding p ocedu e ha ensu es
ha only solu ions wi hin he educed sea ch space a e examined. The expe imen s show ha
small ins ances a e sol ed e icien ly by CPLEX. Ou gene ic algo i hm pe o ms simila ly
well as he sol e on hese ins ances, howe e on a e age i is sligh ly as e . On he majo i y
o he medium sized ins ances, he de ised gene ic algo i hm ou pe o ms he mixed-in ege
linea models implemen ed in CPLEX. An a ea o u u e esea ch could be he de elopmen o
an exac algo i hm o he esou ce o e load p oblem wi h a diness penal y. To u he enable
a ade-o be ween esou ce le elling and he p ojec makespan, a mul i-mode esou ce
o e load p oblem wi h a diness penal y can be in es iga ed. O pa icula in e es a e ac i i y
execu ion modes ha lead o di e en p ocessing imes (We˛gla z e al., 2011). Bo h cons an
esou ce u iliza ions o each execu ion mode and a ying execu ion in ensi ies in e ms o
a wo kload pe spec i e can be conside ed (Bianco e al., 2016; Ta aso e al., 2021). Fu u e
esea ch could add ess, o wha ex en he sea ch space can be educed o hese ex ensions
and which p e equisi es ha ha e o be sa is ied o ha .
Funding Open Access unding enabled and o ganized by P ojek DEAL. No unding was ecei ed o assis
wi h he p epa a ion o his a icle
Decla a ions
Con lic s o in e es The e a e no in e es s o decla e.
E hical app o al This a icle does no con ain any s udies wi h human pa icipan s o animals pe o med by
any o he au ho s.
Open Access This a icle is licensed unde a C ea i e Commons A ibu ion 4.0 In e na ional License, which
pe mi s use, sha ing, adap a ion, dis ibu ion and ep oduc ion in any medium o o ma , as long as you gi e
app op ia e c edi o he o iginal au ho (s) and he sou ce, p o ide a link o he C ea i e Commons licence,
and indica e i changes we e made. The images o o he hi d pa y ma e ial in his a icle a e included in he
a icle’s C ea i e Commons licence, unless indica ed o he wise in a c edi line o he ma e ial. I ma e ial is
no included in he a icle’s C ea i e Commons licence and you in ended use is no pe mi ed by s a u o y
egula ion o exceeds he pe mi ed use, you will need o ob ain pe mission di ec ly om he copy igh holde .
To iew a copy o his licence, isi h p://c ea i ecommons.o g/licenses/by/4.0/.
Re e ences
Abbasi I anagh, M. (2015). De elopmen o high pe o mance heu is ic and me a-heu is ic me hods o
esou ce op imiza ion o la ge scale cons uc ion p ojec s. Ph.D. hesis, Middle Eas Technical Uni-
e si y.
Ahuja, R. K., Magnan i, T. L., & O lin, J. B. (1993). Ne wo k lows. P en ice Hall.
A an, T., & E en, E. (2018). Op imal p ojec du a ion o esou ce le eling. Eu opean Jou nal o Ope a ional
Resea ch, 266(2), 508–520.
Balles in, F., Schwind , C., & Zimme mann, J. (2007). Resou ce le eling in make- o-o de p oduc ion: Mod-
eling and heu is ic solu ion me hod. In e na ional Jou nal o Ope a ions Resea ch, 4(1), 50–62.
Bianco, L., Ca amia, M., & Gio dani, S. (2016). Resou ce le elling in p ojec scheduling wi h gene alized
p ecedence ela ionships and a iable execu ion in ensi ies. OR Spec um, 38, 405–425.
Ge ha ds, P., & S ü ck, C. (2018). A hyb id me aheu is ic o he mul i-mode esou ce in es men p oblem wi h
a diness penal y. In A. Fink, A. Fügenschuh, & M. J. Geige (Eds.), Ope a ions Resea ch P oceedings
2016 (pp. 515–520). Cham: Sp inge .
123
172 Annals o Ope a ions Resea ch (2024) 338:151–172
Ha mann, S., & B isko n, D. (2022). An upda ed su ey o a ian s and ex ensions o he esou ce-cons ained
p ojec scheduling p oblem. Eu opean Jou nal o Ope a ional Resea ch, 297(1), 1–14.
Hegazy, T. (1999). Op imiza ion o esou ce alloca ion and le eling using gene ic algo i hms. Jou nal o
Cons uc ion Enginee ing and Managemen , 125(3), 167–175.
Kim, J., Kim, K., Jee, N., & Yoon, Y. (2005). Enhanced esou ce le eling echnique o p ojec scheduling.
Jou nal o Asian A chi ec u e and Building Enginee ing, 4(2), 461–466.
Kolisch, R., & Ha mann, S. (1999). Heu is ic algo i hms o he esou ce-cons ained p ojec scheduling
p oblem: Classi ica ion and compu a ional analysis. In J. Wégla z (Ed.), P ojec scheduling (pp. 147–
178). Kluwe .
Koulinas, G. K., & Anagnos opoulos, K. P. (2012). Cons uc ion esou ce alloca ion and le eling using a h esh-
old accep ing-based hype heu is ic algo i hm. Jou nal o Cons uc ion Enginee ing and Managemen ,
138(7), 854–863.
K e e , S., Rieck, J., & Zimme mann, J. (2014). The o al adjus men cos p oblem: Applica ions, models, and
solu ion algo i hms. Jou nal o Scheduling, 17(2), 145–160.
Neumann, K., Schwind , C., & Zimme mann, J. (2003). P ojec scheduling wi h ime windows and sca ce
esou ces (2nd ed.). Sp inge .
Neumann, K., & Zimme mann, J. (1999). Resou ce le elling o p ojec s wi h schedule-dependen ime win-
dows. Eu opean Jou nal o Ope a ional Resea ch, 117(3), 591–605.
Ponz-Tienda, J. L., Yepes, V., Pellice , E., & Mo eno-Flo es, J. (2013). The esou ce le eling p oblem wi h
mul iple esou ces using an adap i e gene ic algo i hm. Au oma ion in Cons uc ion, 29(2), 161–172.
P i ske , A. A. B., Wai e s, L. J., & Wol e, P. M. (1969). Mul ip ojec scheduling wi h limi ed esou ces: A
ze o-one p og amming app oach. Managemen Science, 16(1), 93–108.
Rahnamayan, S., Tizhoosh, H. R., & Salama, M. M. A. (2008). Opposi ion-based di e en ial e olu ion. IEEE
T ansac ions on E olu iona y compu a ion, 12(1), 64–79.
Rieck, J., & Zimme mann, J. (2015). Exac me hods o esou ce le eling p oblems, In C. Schwind & J. Zim-
me mann (Eds.), Handbook on P ojec Managemen and Scheduling (Vol. 4, pp. 361–387). Sp inge .
Rieck, J., Zimme mann, J., & Ga he , T. (2012). Mixed-in ege linea p og amming o esou ce le eling
p oblems. Eu opean Jou nal o Ope a ional Resea ch, 221(1), 27–37.
Schnabel, A., Kellenb ink, C., & Helbe , S. (2018). P o i -o ien ed scheduling o esou ce-cons ained p ojec s
wi h lexible capaci y cons ain s. Business Resea ch, 11(2), 329–356.
Schwind , C. (1998). Gene a ion o esou ce-cons ained p ojec scheduling p oblems subjec o empo al
cons ain s. Technical Repo WIOR-543, Ins i u e o Economic Theo y and Ope a ions Resea ch, Uni-
e si y Ka ls uhe.
Shad okh, S., & Kian a , F. (2007). A gene ic algo i hm o esou ce in es men p ojec scheduling p oblem,
a diness pe mi ed wi h penal y. Eu opean Jou nal o Ope a ional Resea ch, 181(1), 86–101.
Ta aso , I., Hai , A., & Ba aia, O. (2021). Bende s decomposi ion o a pe iod-agg ega ed esou ce le eling
p oblem wi h a iable job du a ion. Compu e s & Ope a ions Resea ch, 132, 105258.
We˛gla z, J., Józe owska, J., Mika, M., & Waligó a, G. (2011). P ojec scheduling wi h ini e o in ini e numbe
o ac i i y p ocessing modes-a su ey. Eu opean Jou nal o Ope a ional Resea ch, 208(3), 177–205.
Publishe ’s No e Sp inge Na u e emains neu al wi h ega d o ju isdic ional claims in published maps and
ins i u ional a ilia ions.
123
