Integrated pallet retrieval and processing in warehouses under uncertainty

Buckow, Jan-Niklas; Goe igk, Ma c; Knus , Sig id
A icle — Published Ve sion
In eg a ed palle e ie al and p ocessing in wa ehouses
unde unce ain y
OR Spec um
P o ided in Coope a ion wi h:
Sp inge Na u e
Sugges ed Ci a ion: Buckow, Jan-Niklas; Goe igk, Ma c; Knus , Sig id (2025) : In eg a ed palle
e ie al and p ocessing in wa ehouses unde unce ain y, OR Spec um, ISSN 1436-6304, Sp inge ,
Be lin, Heidelbe g, Vol. 47, Iss. 3, pp. 817-855,
h ps://doi.o g/10.1007/s00291-024-00806-7
This Ve sion is a ailable a :
h ps://hdl.handle.ne /10419/330561
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 ps://c ea i ecommons.o g/licenses/by/4.0/
Vol.:(0123456789)
OR Spec um (2025) 47:817–855
h ps://doi.o g/10.1007/s00291-024-00806-7
ORIGINAL ARTICLE
In eg a ed palle e ie al andp ocessing inwa ehouses
unde unce ain y
Jan‑NiklasBuckow1· Ma cGoe igk2· Sig idKnus 1
Recei ed: 20 Augus 2024 / Accep ed: 12 Decembe 2024 / Published online: 17 Feb ua y 2025
© The Au ho (s) 2025
Abs ac
We s udy he p oblem o in eg a ed palle e ie al and successi e p ocessing in
wa ehouses mo i a ed by a p ac ical company se ing. A se o palle s has o be
e ie ed in a wa ehouse ha ing a single s acke c ane and mul iple inpu /ou pu -
poin s, and he goal is o minimize he makespan. P e ious esea ch ocuses on
minimizing s acke c ane a el imes, while subsequen palle p ocessing imes
a he inpu /ou pu -poin s a e neglec ed. A dis inc ion is made be ween a blocking
and bu e ing a ian , in which ei he no o su icien bu e space is a ailable a
he inpu /ou pu -poin s o empo a ily s o e palle s he e be o e hey a e p ocessed.
To hedge agains unce ain ies in he palle p ocessing imes, we addi ionally apply
obus op imiza ion wi h budge ed unce ain y se s. We de elop dynamic p og am-
ming algo i hms o he wo s -case e alua ion, iden i y polynomially sol able cases
when he e is only a single inpu /ou pu -poin , and p esen ma hema ical models o
he gene al case wi h an a bi a y numbe o inpu /ou pu -poin s. Ou ex ensi e com-
pu a ional s udy e eals ha he in eg a ed models yield conside able bene i s com-
pa ed o ei he igno ing he s acke c ane a el imes o he palle p ocessing imes.
We p opose heu is ic algo i hms ha p o ide good solu ions o la ge ins ances in a
sho amoun o compu a ional ime.
Keywo ds Wa ehouse· S acke c ane scheduling· Mul iple inpu /ou pu -poin s·
In eg a ed palle e ie al and p ocessing· Robus op imiza ion· Budge ed
unce ain y
* Jan-Niklas Buckow
jabuckow@uni-osnab ueck.de
Ma c Goe igk
[email p o ec ed]
Sig id Knus
[email p o ec ed]
1 Ins i u e o Compu e Science, Osnab ück Uni e si y, Wachsbleiche27, 49090Osnab ück,
Ge many
2 Business Decisions andDa a Science, Uni e si y o Passau, D .-Hans-Kap inge -S aße 30,
94032Passau, Ge many
818
J.-N.Buckow e al.
1 In oduc ion
In mode n wa ehouses, au oma ed s o age/ e ie al sys ems (AS/RS) a e popula
o inc ease he e iciency, whe e all i ems a e packed in o uni -load palle s ha a e
s o ed and e ie ed om he wa ehouse by an au oma ed s acke c ane ia speci ic
inpu /ou pu -poin s (I/O-poin s). To ob ain an o e iew o wa ehouses wi h AS/RS
and di e en s acke c ane scheduling p oblems he ein, we e e o Roodbe gen and
Vis (2009) and Boysen and S ephan (2016).
1.1 Mo i a ion
Op imizing s o age and e ie al ope a ions in wa ehouses wi h AS/RS is impo an
o minimize cos s and ensu e a smoo h i em low in supply chains. While mos pub-
lica ions in ha ield only deal wi h wa ehouses ha ing a single I/O-poin , Buckow
e al (2024) s udied a new s acke c ane scheduling p oblem mo i a ed by a p ac ical
se ing in a company, whe e palle s a e e ie ed in a wa ehouse wi h mul iple I/O-
poin s, and employees emo e speci ic i ems om he palle s o a u he p oduc-
ion p ocess. In hei basic p oblem a ian , bo h he palle e ie al sequence and
he assignmen o palle s o I/O-poin s ha e o be de e mined, and he goal is o
minimize he o al a el ime o he s acke c ane o pe o m all e ie als.
We ex end he p oblem s udied byBuckow e al (2024) by addi ionally aking
palle p ocessing imes a he I/O-poin s in o accoun . Ou se ing is mo i a ed by
he same indus ial company, whe e a gi en se o palle e ie al eques s has o
be pe o med o p epa e he nex p oduc ion shi . Thei s acke c ane s a s a a
speci ic depo I/O-poin , and each e ie ed palle is allowed o be b ough o an
a bi a y I/O-poin . A he I/O-poin s, he e incu palle p ocessing imes, mainly
because emo ing i ems om he palle s by he employees akes some ime. In addi-
ion, some i ems ha e o be sawn in hal , wi h one hal emaining in he palle and
he o he hal being needed in he nex p oduc ion shi . These palle p ocessing
imes hus a y be ween di e en e ie al eques s, depending on he i em ype and
quan i y emo ed. To s a he nex p oduc ion shi in ime, he p ocessing o he
las palle should be comple ed as ea ly as possible.
When he s acke c ane eaches an I/O-poin , i d ops he palle o be e ie ed
he e and hen picks up ano he palle o be s o ed. This is possible because a each
I/O-poin , he palle p e iously p ocessed he e is a ailable as a s o age eques
( he e usually emain i ems in he palle s a e hei p ocessing and hey a e hus
e u ned o he s o age). A e eaching an I/O-poin , he s acke c ane mo es o he
nex palle o be e ie ed and swaps i wi h ha cu en ly held on he s acke c ane.
No e ha he company’s s acke c ane can pe o m such palle swaps as i has an
addi ional bu e loca ion. Due o hese palle swaps, he s o age o he palle s ha
a e e u ned o he wa ehouse is pe o med implici ly and does no need o be con-
side ed explici ly.
Figu e 1 exempli ies he p ocesses in he wa ehouse o he men ioned com-
pany. On he one hand, an example s o age layou wi h h ee I/O-poin s and
819
In eg a ed palle e ie al andp ocessing inwa ehouses…
possible s acke c ane mo emen s o e ie ing wo palle s a e shown in Fig.1a.
The le mos I/O-poin co esponds o he depo a which he s acke c ane is ini-
ially loca ed, and he numbe s indica e he o de o he s acke c ane mo emen s.
Each cell ep esen s a s o age loca ion and accommoda es exac ly one palle . On he
o he hand, he p ocess o e ie ing and s o ing palle s is illus a ed in Fig.1b. A e
a palle is e ie ed om i s ini ial s o age loca ion, he s acke c ane b ings i o an
I/O-poin o emo e i ems om i . No e ha he I/O-poin s a e placed a he bo de
be ween he s o age and p oduc ion a ea. When he i em emo al is inished, he
palle is e u ned o he wa ehouse (bu possibly o a di e en s o age loca ion han
i s ini ial one) as soon as he s acke c ane nex eaches he I/O-poin a e e ie ing
ano he palle .
The a o emen ioned company uns a la ge high-bay wa ehouse equipped wi h a
single s acke c ane ha has an addi ional bu e loca ion and is hus designed o
pe o m palle swaps. Acco ding o he s acke c ane’s manu ac u e , he e a e o he
indus ial i ms ope a ing simila wa ehouses, wi h mainly me al p ocesso s as well
as p oduce s o windows and doo s being among hese i ms. All hese i ms a e
p ocessing long and hea y i ems, including ods and me al p o iles. Hence, he e
also seem o be o he companies acing a simila p oblem se ing o ou s in hei
dis ibu ion cen e s. Fu he mo e, no e ha due o he hea iness o hei palle s, he
s acke c ane’s heigh ened capaci y canno be used o anspo wo palle s a once,
meaning ha palle swaps a e he p e e ed ope a ing mode.
The p ocessing o a palle a an I/O-poin makes i empo a ily una ailable and
hus impac s he choices o he e ie al I/O-poin s. We add ess his se ing mo e
accu a ely by p oposing an in eg a ed p oblem conside ing bo h he s acke c ane
a el imes as well as he palle p ocessing imes. Al hough he app oaches p e-
sen ed by Buckow e  al (2024) p o ide easible solu ions o ou new in eg a ed
p oblem, hey comple ely neglec he palle p ocessing imes, equi ing mo e com-
plex solu ion app oaches o ully exploi he whole op imiza ion po en ial.
F om discussions wi h planne s a he a o emen ioned company, we know ha
he p ocessing o some palle s may ac ually consume mo e ime han o iginally
expec ed, as unp edic able dis up ions occasionally occu when emo ing i ems
om he palle s a he I/O-poin s. Fo ins ance, he wo king speeds o he employ-
ees di e , and hey occasionally ake a sho b eak. Mo eo e , a ehicle equi ed
Fig. 1 Exempla y wa ehouse o e iew and he p ocesses he ein
820
J.-N.Buckow e al.
o u he anspo he emo ed i ems may no be a ailable in ime. The e o e, we
addi ionally ake unce ain ies in he palle p ocessing imes in o accoun , handling
hem by applying obus op imiza ion.
Ou in eg a ed p oblem can be iewed as a pa allel machine scheduling p oblem
wi h anspo a ion conside a ions and unce ain ies. The I/O-poin s co espond o
he machines, he palle s a e he jobs o be p ocessed, and he s acke c ane a el
imes a e se up imes needed o p epa e he I/O-poin s be o e p ocessing he palle s.
Ou p oblem is also ela ed o hyb id/ lexible low-shop scheduling p oblems, whe e
he s acke c ane o ms a i s s age wi h a single machine, and he I/O-poin s co -
espond o a second s age wi h mul iplemachines.
1.2 Li e a u e
O e all, ou in eg a ed p oblem is ela ed o he h ee esea ch ields o machine
scheduling, wa ehousing p oblems, and obus op imiza ion. In he ollowing, we
delimi ou p oblem in ela ion o hese h ee esea ch ields, which in e sec .
The e a e se e al s udies esea ching scheduling p oblems wi h se up imes o
anspo a ion conside a ions (see he su eys by Allah e di e  al (1999, 2008),
Allah e di (2015) andHosseini e al (2024)). Howe e , in con as o he exis ing li -
e a u e, ou p oblem in ol es a single s acke c ane wi h a anspo a ion capaci y o
one. The e o e, he se up o anspo a ion ime o p epa e he p ocessing o a palle
depends no only on he palle i sel , i s chosen e ie al I/O-poin and i s immedi-
a e p edecesso he e, bu also on he scheduling decisions o all palle s p e iously
e ie ed, making ou p oblem mo e di icul .
In ecen decades, supply chain scheduling has eme ged as a new esea ch ield
ha links machine scheduling p oblems wi h supply chain managemen decisions
(see he book by Chen and Hall (2022)). Se e al such p oblems also deal wi h
anspo a ion conside a ions, and i is usually assumed ha goods a e p oduced on
machines in a ac o y and hen anspo ed o cus ome s o wa ehouses. Ne e he-
less, hese s eps a e e e sed in ou p oblem, since he anspo o a palle akes
place be o e i is p ocessed a an I/O-poin . Fu he mo e, in hese supply chain
scheduling p oblems wi h anspo a ion conside a ions, all machines wi hin a ac-
o y a e ypically modeled as one loca ion, while we assume ha bo h he palle s and
he I/O-poin s can ake di e en a bi a y loca ions wi hin he wa ehouse.
In low-shop scheduling p oblems, a dis inc ion is made be ween blocking and
bu e ing a ian s, depending on whe he he e is su icien bu e space o empo a -
ily s o e jobs when hei nex p ocessing machine is busy (see he su ey byMiya a
and Nagano (2019)). In many wa ehouses wi h AS/RS, he e is no bu e space a
all a he I/O-poin s, meaning ha he s acke c ane mus wai un il he I/O-poin is
ee again be o e i can d op o a palle he e (in his case, we call he s acke c ane
being blocked). Al hough he e appea s o be li le esea ch dealing wi h such bu e
spaces in wa ehouses, de Kos e e al (2012) and Jiang e al (2022) s udy manual
pick-and-so wa ehouses, whe e picked ba ches a e bu e ed be o e hey a e so ed.
While de Kos e e al (2012) assume unlimi ed bu e space, Jiang e al (2022) sup-
pose ha he bu e capaci y is limi ed and picke s a e blocked i he bu e is ull.

821
In eg a ed palle e ie al andp ocessing inwa ehouses…
Teck e al (2024) s udied a wa ehouse scheduling p oblem wi h p ocessing ime
a iabili y, whe e mul iple obo s a e li ing pods om he s o age o wo ks a ions
and s ochas ic op imiza ion is used in o de o p o ec agains he unce ain p ocess-
ing imes. Gong and de Kos e (2011) conduc ed a su ey on s ochas ic op imiza ion
in wa ehouse ope a ions in gene al, and desc ibed di e en sou ces o unce ain y,
which can be bo h wi hin and ex e nal o he wa ehouse sys em o he supply chain.
Fo example, he unce ain ies wi hin he wa ehouse include human ac o s such as
labo absence o luc ua ions in he wo king speed. Unce ain ies in he supply chain
may a ise om ailu es in he shipping equipmen like ucks o palle jacks.
As al eady no ed by Gong and de Kos e (2011), he e emain academic blanks
in he ield o obus app oaches o wa ehouse ope a ions. Unlike s ochas ic op i-
miza ion, he o me does no equi e a p obabili y dis ibu ion o he scena ios in
he unce ain y se , making i applicable e en wi hou such knowledge. Fo in-dep h
discussions o he obus op imiza ion pa adigm, we e e o he books by Ben-Tal
e al (2009), Be simas and den He og (2022), and Goe igk and Ha isch (2024).
Ben-Tal e al (2004) in oduced he concep o adjus able obus op imiza ion and
applied i o an in en o y managemen p oblem wi h demand unce ain y, whe e
some decisions mus be made be o e he ealiza ion o he unce ain da a, while
o he decisions can be made a e he ealiza ion (see also he su ey by Yanıkoğlu
e al (2019)).
Since he su ey o Gong and de Kos e (2011), he e a e some u he s udies
on obus op imiza ion in wa ehouses. Ang e al (2012) examined a obus s o age
assignmen p oblem wi h a iable supply and unce ain demand. Mos pape s deal-
ing wi h obus wa ehouse ope a ions conside ed in en o y managemen p oblems
wi h demand o lead ime unce ain y ( o ins ance, see Tho sen and Yao (2015),
Jiu (2022), Qiu e al (2022) andSun e al (2024)). Ne e heless, ins ead o schedul-
ing palle e ie als, o he decisions a e op imized in hese obus p oblems, mainly
de e mining pe iodic in en o y e iew policies. The e seem o be no s udies on
obus op imiza ion in wa ehouse ope a ions ha conside palle e ie al op imiza-
ion o unce ain p ocessing imes a he I/O-poin s.
The ype o obus p oblem we conside has some simila i y o B uni e al (2017)
andBold and Goe igk (2021), who s udy a esou ce-cons ained p ojec scheduling
p oblem, whe e he ac i i y du a ions a e subjec o budge ed unce ain y. Handling
he p oblem as a obus wo-s age app oach, he esou ce alloca ion decisions ha e
o be made be o e he unce ain ac i i y du a ions become known, bu he ac i i y
s a imes can be ixed a e he ealiza ion o he ac i i y du a ions.
1.3 Con ibu ions
In his pape , we s udy he palle e ie al and p ocessing p oblem (
PRPP
), whe e a
gi en se o palle s has o be e ie ed and p ocessed in a wa ehouse equipped wi h
a single s acke c ane and mul iple I/O-poin s. The
PRPP
can be conside ed as an
in eg a ed p oblem, gene alizing bo h exis ing palle e ie al op imiza ion as well
as machine scheduling p oblems om he li e a u e. Ou goal is o minimize he
makespan, which is de ined as he comple ion ime o he las palle p ocessed.
822
J.-N.Buckow e al.
We also in es iga e he gain o ha ing bu e spaces a he I/O-poin s o em-
po a ily s o e palle s he e be o e hey a e p ocessed, and dis inguish be ween wo
p oblem a ian s. In he i s a ian , he s acke c ane empo a ily blocks when
app oaching an occupied I/O-poin (blocking a ian ), while in he second a ian ,
su icien bu e space always allows palle s o be d opped o e en a occupied I/O-
poin s (bu e ing a ian ).
To p o ec agains unce ain ies in he palle p ocessing imes, we addi ionally
inco po a e obus op imiza ion in o ou p oblem. We assume ha nominal alues
and uppe bounds on he possible p ocessing ime delays a e known by he decision
make . As i seems unlikely ha he p ocessing imes o all palle s ake hei wo s -
case alues a he same ime, we assume budge ed unce ain y se s, which limi he
o al numbe o de ia ing p ocessing imes.
We iden i y special cases o he
PRPP
wi h only a single I/O-poin , whe e he
in eg a ed p oblem becomes polynomially sol able (in he blocking case e en he
obus a ian ). Fo he gene al case wi h an a bi a y numbe o I/O-poin s, we
de elop ma hema ical models o he blocking and bu e ing a ian wi h and wi h-
ou obus ness, and p esen dynamic p og amming algo i hms o he wo s -case
e alua ion, i.e., inding he wo s possible objec i e alue unde all conside ed sce-
na ios. Ou esul s show ha he in eg a ed conside a ion o palle e ie al and
p ocessing is c ucial o ob ain good solu ions. Mo eo e , schedules ob ained by ou
obus models a e conside ably less ulne able o delays in he palle p ocessing
imes. Ha ing bu e s a he I/O-poin s leads o clea educ ions in he makespan.
This pape is o ganized as ollows. Fi s , he
PRPP
and i s a ian s a e in oduced
and o mally de ined in Sec .2. A e wa ds, in Sec .3, we heo e ically s udy he
special case wi h a single I/O-poin o bo h he blocking and he bu e ing a i-
an , and e eal a ian s ha a e sol able in polynomial ime. In addi ion, he gen-
e al mul iple I/O-poin case is ackled in Sec .4, o which we de elop ma hema i-
cal models and dynamic p og amming algo i hms o he wo s -case e alua ion. In
Sec .5, i ollows a de ailed compu a ional s udy, in which we i s in es iga e he
bene i s o he newly de eloped in eg a ed ma hema ical models in bo h he nominal
and obus cases. Besides, he bene i s o ha ing a bu e as well as some heu is ics
a e e alua ed. E en ually, Sec .6 concludes hepape .
2 P oblem de ini ion
The
PRPP
can be ega ded as an in eg a ed wo-s age p oblem, whe e he i s s age
in ol es e ie ing each palle om i s s o age loca ion and hen mo ing i o one o
he di e en I/O-poin s. Once he s acke c ane has anspo ed a palle o an I/O-
poin , he palle is p ocessed he e in a second s age wi h a palle dependen p ocess-
ing ime. No e ha he esul ing makespan is impac ed by bo h he s acke c ane
a el imes o e ie e he palle s du ing he i s s age, and he palle p ocessing
imes du ing he seconds age.
Due o i s s ages, he
PRPP
is ela ed o hyb id o lexible low-shop scheduling
p oblems, whe e a se o jobs mus be p ocessed successi ely in a se ies o s ages, each
s age consis ing o one o mo e machines. In he
PRPP
, he s acke c ane ha e ie es
823
In eg a ed palle e ie al andp ocessing inwa ehouses…
he palle s o ms he i s s age wi h a single machine, while he I/O-poin s whe e he
palle s a e p ocessed co espond o he second s age wi h mul iple machines. Howe e ,
he key dis inc ion o he
PRPP
o adi ional hyb id low-shop scheduling p oblems is
ha we also ackle anspo a ion conside a ions: he s acke c ane a el imes (co -
esponding o he p ocessing imes in he i s s age) a e no cons an pe palle (co e-
sponding o a job), bu depend on bo h he palle e ie al sequence and he assignmen
o palle s o I/O-poin s.
As in he case o low-shop scheduling p oblems, we conside wo di e en a ian s
o he
PRPP
. In he blocking a ian (
PRPPBl
), he I/O-poin s ha e no bu e space,
blocking he s acke c ane when b inging a palle o an I/O-poin un il he p ocessing o
he palle s p e iously b ough o he same I/O-poin is comple ed. The s acke c ane can
hen d op o he new palle and con inue o e ie e he nex palle in he wa ehouse.
On he o he hand, in he bu e ing a ian (
PRPPBu
), he e is su icien bu e space
a ailable a he I/O-poin s whe e palle s can be s o ed empo a ily, a oiding idle imes
o he s acke c ane, i.e., i is always possible o d op o a palle immedia ely when he
s acke c ane a i es. Fu he mo e, he special cases wi h only a single I/O-poin o
hese p oblem a ian s we examine in Sec .3 a e deno ed by
1PRPPBl
and
1PRPPBu
,
espec i ely.
Mo e o mally, he
PRPP
can be s a ed as ollows. We a e gi en a wa ehouse
wi hn palle s
P={p1,…,pn}
,m di e en I/O-poin s
Θ={𝜃1,…,𝜃m}
, and a s acke
c ane which is ini ially loca ed a he depo I/O-poin 
𝜃Depo ∈Θ
(no e ha ou solu-
ion app oaches can easily be adap ed o handle he case o an a bi a y ini ial loca-
ion). Mo eo e , each palle 
p∈P
is associa ed wi h a p ocessing ime (p), whe e
we la e assume ha hese p ocessing imes a e subjec o unce ain y. In o al, we
ha e
𝜇=n+m
loca ions
L={𝓁1,…,𝓁𝜇}
, i.e., a loca ion
𝓁(p)
o each palle 
p∈P
as
well as a loca ion
𝓁(𝜃)
o each I/O-poin 
𝜃∈Θ
. No e ha each s o age loca ion co e-
sponding o a palle can accommoda e only a single palle . Fo all loca ions
𝓁i,𝓁j∈L
,
he e a e s acke c ane a el imes
𝜏[𝓁i,𝓁j]
. In eal wa ehouses, hese s acke c ane
a el imes ypically esul om a me ic, i.e., hey a e symme ic and sa is y he ian-
gle inequali y. Howe e , we do no impose any es ic ions on hese a el imes, esul -
ing in a mo e gene al p oblem se ing.
We deno e by
Π
he se o all pe mu a ions o palle sP, and
𝜋=(𝜋1,…,𝜋n)∈Π
co esponds o a speci ic sequence in which he palle s a e e ie ed. In addi-
ion, le 
𝛼(p)∈Θ
desc ibe he selec ed I/O-poin o which palle 
p∈P
is b ough
and hen p ocessed, and
𝛼=(𝛼(p1),…,𝛼(pn))∈Θ
n
ep esen s an assignmen
o palle s o I/O-poin s. The goal o he
PRPP
is o ind bo h a palle e ie al
sequence
𝜋∈Π
and an assignmen 
𝛼∈Θ
n
o palle s o I/O-poin s such ha he
makespan
Cmax∶Π×Θ
n
→
ℝ+
is minimized, i.e.,
wi h being he possibly unce ain p ocessing imes pa ame e s and he objec i e
unc ion
Cmax
being de inedas
(1)
min
(𝜋,𝛼)∈Π×Θ
n
C
max
(𝜋,𝛼, ),
(2)
C
max(𝜋,𝛼, )=
n
max
k=1
{sk(𝜋,𝛼, )+ (𝜋k)}
,
824
J.-N.Buckow e al.
whe e o 
k=1, …,n
he alue
sk(𝜋,𝛼, )
deno es he s a ime o p ocessing
hek h palle e ie ed by he s acke c ane. The s a ime o p ocessing he i s pal-
le e ie ed is gi enby
meaning he s acke c ane has o mo e om i s ini ial loca ion
𝓁(𝜃Depo )
o
𝓁(𝜋1)
,
whe e he i s palle is ini ially posi ioned, and b ing i o he chosen a ge I/O-
poin 
𝛼(𝜋1)
. In he ollowing, o 
k=1, …,n
, we use
p ed(k)∈{0, …,k−1}
o
deno e he posi ion in
𝜋
o he palle p e iously p ocessed a he same I/O-poin
as palle
𝜋k
, wi h
p ed(k)=0
i he palle a posi ionk is he i s one p ocessed a
i s I/O-poin , and we de ine
s0(𝜋,𝛼, )=0
and
(𝜋0)=0
. Then, o 
k=2, …,n
, he
s a ime alues can be ecu si ely calcula edby
whe e he le e m conside s he comple ion ime o he palle p e iously p ocessed
a he same I/O-poin , and
k(𝜋,𝛼, )
is he ime when he s acke c ane has e ie ed
hek h palle and b ough i o he chosen a ge I/O-poin . Due o he missing bu e
space in he case o 
PRPPBl
, he s acke c ane mus wai a he chosen I/O-poin
when e ie ing a palle un il he p ocessing o he p eceding palle a he same
I/O-poin is comple ed. In his scena io, we call he s acke c ane blocking, and o
k=2, …,n
, weha e
Howe e , in he case o 
PRPPBu
, a su icien numbe o palle s can be bu e ed a
each I/O-poin . Hence, he s acke c ane can mo e wi hou any in e up ions un il all
palle s a e e ie ed, and we ha e o eplace(5)by
Example 1 Conside he example ins ance o he
PRPP
wi h
n=6
palle s,
m=2
di -
e en I/O-poin s and he depo I/O-poin 
𝜃Depo =𝜃1
as shown in Table1. The pal-
le p ocessing imes a e displayed in Table1a, and he s acke c ane a el imes
in Table1b. Assuming he palle e ie al sequence
𝜋=(p1,p2,p3,p4,p5,p6)
and
he assignmen o palle s o I/O-poin s
𝛼=(𝜃1,𝜃2,𝜃2,𝜃1,𝜃2,𝜃1)
, he co esponding
schedules o 
PRPPBl
and
PRPPBu
a e shown in Fig.2 and3. The e, he ac i i ies o
he s acke c ane and he I/O-poin s a e isualized, whe e idle imes a e ep esen ed
as ha ched a ea, and blocking imes o he s acke c ane a e d awn as do ed a ea. In
he case o 
PRPPBl
, he s acke c ane blocks and has idle imes a e he p ocessing
o he palle s
p3
and
p5
, since hei a ge I/O-poin keeps busy o a while, esul ing
in a makespan o 
Cmax =30
. In con as , he e a e no s acke c ane idle imes in he
case o 
PRPPBu
, leading o a smalle makespan o 
Cmax =27
.
(3)
s1(𝜋,𝛼, )=𝜏[𝓁(𝜃Depo ),𝓁(𝜋1)] + 𝜏[𝓁(𝜋1),𝓁(𝛼(𝜋1))],
(4)
sk(𝜋,𝛼, )=max{sp ed(k)(𝜋,𝛼, )+ (𝜋p ed(k)), k(𝜋,𝛼, )},
(5)
k(𝜋,𝛼, )=sk−1(𝜋,𝛼, )+𝜏[𝓁(𝛼(𝜋k−1)),𝓁(𝜋k)] + 𝜏[𝓁(𝜋k),𝓁(𝛼(𝜋k))].
(6)
k(𝜋,𝛼, )=s1(𝜋,𝛼, )+
k
∑
k
�
=2
(𝜏[𝓁(𝛼(𝜋k�−1)),𝓁(𝜋k�)] + 𝜏[𝓁(𝜋k�),𝓁(𝛼(𝜋k�))])
.
831
In eg a ed palle e ie al andp ocessing inwa ehouses…
a a i s glance. In Lemma2, we demons a e ha o each o hese esul ing
TSP
ins ances, he e exis s an equi alen 
LTSP
ins ance ha can be sol ed e icien ly.
Lemma 2 Le 
I�
TSP
be a
TSP
ins ance wi h he speci ic a c cos s
o all
( ,w)∈A
and a cons an 
𝜆≥0
. Then, he
LTSP
ins ance
I��
LTSP
wi h
a��( )=a( )+max{0, a( )−𝜆}
and
b��( )=b( )
o all
∈V
is equi alen o
he
TSP
ins ance
I�
TSP
.
P oo In he
LTSP
ins ance
I��
LTSP
, each a c
( ,w)∈A
has he cos s
I he e o e emains o show ha he a c cos s
c�( ,w)
o 
I�
TSP
a e he same as he a c
cos s
c��( ,w)
o 
I��
LTSP
o all
,w∈V
, which we do using a case dis inc ion.
• I 
b(w)<a( )
, we ha e
• I 
b(w)≥a( )
and
b(w)<a( )+a( )
, we ha e
whe e
a( )−𝜆
is equal o
max{0, a( )−𝜆}
i 
a( )
≥
𝜆
, and
bo h
max{b(w),a( )+a( )−𝜆}
as well as
max{b(w),a( )+max{0, a( )−𝜆}}
a e equal ob(w) i 
a( )<𝜆
.
• I 
b(w)
≥
a( )+a( )
, we ha e
◻
Recall ha he nominal
LTSP
wi h
𝜂
nodes is sol able in
O(𝜂⋅log 𝜂)
, and hus
Theo em1 ollows by combining Lemmas1 and2.
c�
( ,w)=c( ,w)+max{0, c( ,w)−𝜆}
=max{a( ),b(w)} + max{0, max{a( )+a( ),b(w)} − max{a( ),b(w)} − 𝜆}
c��( ,w)=max{a( )+max{0, a( )−𝜆},b(w)}.
c�
( ,w)=a( )+max{0, a( )+a( )−a( )−𝜆
}
=a( )+max{0, a( )−𝜆}
=c
��
( ,w).
c�
( ,w)=b(w)+max{0, a( )+a( )−b(w)−𝜆}
=max{b(w),b(w)+a( )+a( )−b(w)−𝜆
}
=max{b(w),a( )+a( )−𝜆}
=max{b(w),a( )+max{0, a( )−𝜆}}
=c
��
( ,w),
c�
( ,w)=b(w)+max{0, b(w)−b(w)−𝜆}
=b(w)
=max{b(w),a( )+max{0, a( )−𝜆
}}
=c
��
( ,w).

832
J.-N.Buckow e al.
Theo em1 The
LTSPR
wi h
𝜂
nodes is sol able in
O(
𝜂
3
⋅
log
𝜂
)
.
P oo Acco ding o Lemma1, an op imal solu ion o an
LTSPR
ins ance wi h
𝜂
nodes can be compu ed by sol ing a mos 
𝜂2+1
di e en nominal
TSP
ins ances
wi h a speci ic cos s uc u e, whe e acco ding o Lemma 2 each one can be
ans o med o an equi alen nominal
LTSP
ins ance. The nominal
LTSP
wi h
𝜂
nodes is sol able in
O(𝜂⋅log 𝜂)
, esul ing in an o e all un ime o 
O(𝜂3
⋅
log 𝜂)
o
sol e
LTSPR
.
◻
Gi en Theo em1, we immedia ely conclude Co olla y1 due o he equi a-
lence o 
LTSPR
and
1PRPPR
Bl
.
Co olla y 1
1PRPPR
Bl
is sol able in
O(n3
⋅
log n)
.
O e all, ou esul s o he single I/O-poin case om his sec ion a e summa-
ized in Table3 (bo h he equi alen p oblems and hei complexi ies), g ouped
by he blocking and bu e ing a ian as well as he nominal and obus case.
4 Mul iple I/O‑poin s
This sec ion deals wi h he wo gene al a ian s
PRPPR
Bl
and
PRPPR
Bu
wi h an
a bi a y numbe o I/O-poin s. The wo co esponding nominal a ian s
PRPPBl
and
PRPPBu
a e al eady NP-ha d as will be demons a ed nex , showing imme-
dia ely ha his is also he case o hei obus coun e pa s. Bo h
PRPPBl
and
PRPPBu
in ol e inding a easible s acke c ane ou as well as a pa i ion
o he palle s o he I/O-poin s (making i imp ac ical o enume a e all possible
solu ions e en on e y small ins ances as he e a e o ally
n!⋅mn
di e en solu-
ions). On he one hand, when igno ing he palle p ocessing imes (i.e.,
(p)=0
o all
p∈P
), we ob ain he Re ie al Op imiza ion P oblem (
ROP
) s udied
byBuckow e al (2024), which is a gene aliza ion o he
TSP
and hus al eady
NP-ha d. On he o he hand, when igno ing he s acke c ane a el imes
(i.e.,
𝜏[𝓁i,𝓁j]=0
o all
𝓁i,𝓁j∈L
), only he palle p ocessing imes on he
I/O-poin s a e ele an , esul ing in he NP-ha d scheduling p oblem
P||Cmax
.
This s esses he complexi y o e en he nominal a ian s wi h mul iple I/O-
poin s, gi en ha hey a e gene aliza ions o wo s ongly NP-ha d p oblems.
Table 3 Summa ized esul s o he single I/O-poin case
Va ian
Nominal Robus
Equi alen p oblem Complexi y Equi alen p oblem Complexi y
Blocking
F2|blocking|Cmax
O(nlog n)
LTSPR
O
(
n3log n)
Bu e ing
F2||Cmax
O(nlog n)
Open Open
833
In eg a ed palle e ie al andp ocessing inwa ehouses…
Subsec ions4.1 and4.2 deal wi h he blocking and bu e ing case when ha ing
mul iple I/O-poin s, espec i ely.
4.1 Blocking a ian
We i s e eal a ma hema ical model o he nominal blocking a ian 
PRPPBl
in
Sec . 4.1.1, be o e p esen ing a dynamic p og amming algo i hm o he wo s -case
e alua ion o i s obus coun e pa 
PRPPR
Bl
in Sec . 4.1.2. Finally, in Sec . 4.1.3, a
ma hema ical model o 
PRPPR
Bl
in eg a ing he dynamic p og amming app oach is
p esen ed.
4.1.1 Nominal case
Nex , we p esen a o mula ion o he nominal p oblem
PRPPBl
as mixed-in ege lin-
ea p og am (MIP), ex ending he o mula ion in oduced by Buckow e al (2024) o
he
ROP
by addi ionally inco po a ing he palle p ocessing imes. The way he s acke
c ane a el imes a e modeled is based on he MIP o mula ion p esen ed by Goe -
igk e al (2013) o a bus e acua ion p oblem. Ou model has ou di e en a iable
ypes. Fi s , he bina y posi ion a iables
xjki
ecei e he alue1 i palle 
pj∈P
is
e ie ed a posi ion
k∈{1, …,n}
a he I/O-poin
𝜃i∈Θ
, and0 o he wise. Second,
o 
k=1, …,n
, he a iables
dk
o
and
dk
om
ep esen he s acke c ane’s du a ions o
app oach hek h palle e ie ed, and b inging i om he e o i s assigned I/O-poin ,
espec i ely. Mo eo e , o 
k=0, …,n
, a iable
sk
indica es he s a ing ime o he
p ocessing o he palle a posi ionk a i s assigned I/O-poin , wi h
k=0
meaning ha
no palle is e ie ed a all. Finally, a iable
Cmax
co esponds o he makespan o he
esul ing schedule.
(
MIP-PRPP
R
Bl)
(21)
min Cmax
(22)
s. .
n
∑
j=1
m
∑
i=1
xjki =1k=1, …,
n
(23)
n
∑
k=1
m
∑
i=1
xjki =1j=1, …,
n
(24)
d
1
o =
n
∑
j=1
m
∑
i=1
(𝜏[𝓁(𝜃Depo ),𝓁(pj)] ⋅xj1i
)
834
J.-N.Buckow e al.
Gi en he ou a iable ypes p esen ed abo e, we ha e he MIP o mula ion(21)-
(33). The objec i e unc ion (21) minimizes he esul ing makespan. Fu he mo e,
cons ain s(22) and(23) ensu e ha he s acke c ane a el sequence is p ope ly
de ined, i.e., exac ly one palle is p ocessed a each posi ion and each palle has o
be p ocessed exac ly once. Cons ain  (24) de ines he s acke c ane a el du a-
ion o mo e om he depo I/O-poin 
𝜃Depo
o he ini ial loca ion o he i s palle
e ie ed. Cons ain s(25) desc ibe he s acke c ane a el du a ions o mo e om
he p e ious I/O-poin isi ed o he ini ial loca ion o each o he emaining palle s.
Analogously, cons ain s(26) de ine he s acke c ane a el du a ions o mo e om
each palle o i s assigned I/O-poin . Cons ain s(27) o ce he makespan o be la ge
han all palle comple ion imes. Addi ionally, cons ain s(28) and(29) ensu e ha
he palle s a ing imes a e de ined co ec ly by conside ing o each palle bo h he
comple ion ime o he p edecesso palle a he same I/O-poin and he s acke c ane
a el du a ion. Finally, he a iable domains a e de ined by(30)-(33).
The big-M condi ions ensu e ha cons ain s(28) a e only ac i e i bo h palle s
in ol ed a e p ocessed on he same I/O-poin . No e ha he eby all palle s p e iously
p ocessed on he same I/O-poin a e conside ed, ins ead o only using he di ec
(25)
d
k
o ≥𝜏[𝓁(𝜃i),𝓁(pj)] ⋅
(
n
∑
j�=1
xj�,k−1,i+
m
∑
i�=1
xjki�−1
)k=2, …,n;
j=1, …,n;
i=1, …,m
(26)
d
k
om =
n
∑
j=1
m
∑
i=1
(𝜏[𝓁(pj),𝓁(𝜃i)] ⋅xjki)k=1, …,
n
(27)
C
max ≥sk+
n
∑
j=1
m
∑
i=1
( (pj)⋅xjki)k=1, …,
n
(28)
s
k≥sk�+
n
∑
j=1
( (pj)⋅xjk�i)−M⋅
(
2−
n
∑
j=1
(xjki +xjk�i)
)k=2, …,n;
k�=1, …,k−
1;
i=1, …,m
(29)
sk
≥s
k−1
+d
k
o
+d
k
om
k=1, …,
n
(30)
x
jki ∈{0, 1}
j,k=1, …,n;
i=1, …,m
(31)
dk
o
,d
k
om
≥0k=1, …,
n
(32)
Cmax ≥0
(33)
sk
≥
0k=0, …,n
835
In eg a ed palle e ie al andp ocessing inwa ehouses…
p edecesso s. While his esul s in some edundan cons ain s, we need less big-M
condi ions. O e all, only cons ain s(28) con olling he objec i e alue con ain he
big-M pa ame e . The e o e, he objec i e alue o each easible solu ion is always
an uppe bound o pa ame e M, and i can be se o
4.1.2 Dynamic p og amming
Fo he wo s -case e alua ion o 
PRPPR
Bl
, we need o de e mine which palle s he
ad e sa y chooses o delay o a ixed s acke c ane ou cha ac e ized by a pal-
le e ie al sequence
𝜋
and an assignmen 
𝛼
o palle s o I/O-poin s. Fo his pu -
pose, we p esen a dynamic p og amming app oach, whe e he key obse a ion is
ha a palle p ocessing can only s a a e i is e ie ed by he s acke c ane and
he p ocessing o he p e ious palle a he same I/O-poin is comple ed. Due o he
blocking condi ion, he s acke c ane can only e ie e he cu en palle a e he
p ocessing o he palle p e iously e ie ed by he s acke c ane (a any I/O-poin )
is s a ed. F om he esul ing ne wo k wi hO(n) s a es, we hen c ea e
Γ
copies o
inco po a e he po en ial palle delays, leading o a dynamic p og amming app oach
wi h a un ime o 
O(n⋅Γ)
.
The dynamic p og am has s a es
z𝛾k∈ℝ+
co esponding o he p ocessing s a
ime o he palle e ie ed a posi ion
k∈{0, …,n}
(whe e
k=0
means ha no pal-
le is e ie ed a all) in he case ha a mos 
𝛾∈{0, …,Γ}
palle s can be delayed. In
addi ion, s a es
z𝛾,n+1
indica e he esul ing makespan
Cmax
i a mos 
𝛾∈{0, …,Γ}
palle s can ake hei wo s -case p ocessing imes. In he ollowing, le
se 
P ed(n+1)⊆{1, …,n}
con ain he posi ions o all palle s ha a e p ocessed
las on any I/O-poin . Mo eo e , o 
k=1, …,n
, we deno e by
d(𝜋k)
he s acke
c ane a el du a ion o e ie e palle 
𝜋k
(i.e., he ime o mo e om i s p e ious
loca ion o he ini ial loca ion o palle 
𝜋k
and hen o he assigned I/O-poin 
𝛼(𝜋k)
),
which is ixed o gi en
𝜋
and
𝛼
. We ini ialize
z𝛾0=0
o all
𝛾=0, …,Γ
, and he
ecu sion is gi en as ollows.
• Fo 
𝛾=0
and
k=1, …,n
, we ha e
z
0
k
=max{z0,
k
−1+d(𝜋
k
),z0,
p ed
(
k
)+ (𝜋
p ed
(
k
)
)}
,
because no palle is delayed, and he p ocessing o palle 
𝜋k
can only s a a e
i is e ie ed by he s acke c ane and i s I/O-poin p edecesso is comple ed,
espec i ely.
• Fo 
𝛾=1, …,Γ
and
k=1, …,n
, we addi ionally ha e o conside he case ha
he p edecesso palle 
𝜋p ed(k)
is delayed, leading o
(34)
M
=
∑
p∈P
(p)+
∑
𝓁
i
,𝓁
j
∈L
𝜏[𝓁i,𝓁j]
.
z
𝛾k
=max{z
𝛾,k−1
+d(𝜋
k
),
z𝛾,p ed(k)+ (𝜋p ed(k)),
z
𝛾−1, p ed(k)
+ (𝜋
p ed(k)
)+
(𝜋
p ed(k)
)}
.
836
J.-N.Buckow e al.
• Fo
𝛾=0
and
k=n+1
we ha e
z0, n+1
=max
k∈P ed(n+1)
{z
0k
+ (𝜋
k)}
, as he
makespan
Cmax
is de ined as he la ges comple ion ime o a palle p ocessing.
• Fo 
k=n+1
and
𝛾=1, …,Γ
, we ha e
z𝛾,n+1
=max
k∈P ed(n+1)
{z
𝛾k
+ (𝜋
k
)
,
z𝛾−1, k
+ (𝜋
k
)+
(𝜋
k)}
o addi ionally inco po a e he case ha a palle p ocessed
las on an I/O-poin is delayed.
Example 3 Recall he schedule displayed in Fig.2 o he
PRPPR
Bl
ins ance wi h
Γ=2
om Tables 1 and 2. The co esponding dynamic p og amming p ocess o he
wo s -case e alua ion is shown in Fig.7. The nodes ep esen he s a es, and he
a cs co espond o he di e en alues conside ed in he ecu sion. The s acke c ane
a el du a ions conside ed in he ecu sion a e ep esen ed by dashed a cs, while
he palle p ocessing imes a e illus a ed by solid a cs. The do ed a cs he eby co -
espond o he case ha he p ocessing o a palle is delayed. A longes pa h om
Fig. 7 Example o dynamic p og amming o 
PRPPR
Bl

837
In eg a ed palle e ie al andp ocessing inwa ehouses…
s a e
z00
o
z27
wi h a leng h o 38 is highligh ed in bold, and he ad e sa y would
delay palle s
p2
and
p4
.
4.1.3 Robus case
To o mula e he obus a ian 
PRPPR
Bl
as MIP, we need o in eg a e he dynamic p o-
g am o he wo s -case e alua ion as desc ibed in Subsec ion4.1.2 in o he MIP o
he co esponding nominal a ian 
PRPPBl
as speci ied in Subsec ion4.1.1. On he one
hand, o all
𝛾=0, …,Γ
and
k=0, …,n+1
, we inse a a iable
z𝛾k
ep esen ing
he co esponding s a e in he dynamic p og am. On he o he hand, we emo e a i-
able
Cmax
and he s a ing ime a iables
sk
o 
k=1, …,n
, as hese alues a e al eady
ep esen ed by he inse ed s a e a iables.
(
MIP-PRPP
R
Bl)
(35)
min zΓ,n+1
s. . (22)−(26)
(36)
z
𝛾k≥z𝛾,k−1+dk
o +dk
om
𝛾=0, …,Γ;
k=1, …,n
(37)
z
𝛾k≥z𝛾k�+
n
∑
j=1
( (pj)⋅xjk�i)−M⋅(2−
n
∑
j=1
(xjki +xjk�i))
𝛾=0, …,Γ;
k=2, …,n;
k�=1, …,k−
1;
i=1, …,m
(38)
z
𝛾k≥z𝛾−1,k�+
n
∑
j=1
(( (pj)+
(pj)) ⋅xjk�i)
−M⋅(2−
n
∑
j=1
(xjki +xjk�i))𝛾=1, …,Γ;
k=2, …,n;
k�=1, …,k−
1;
i=1, …,m
(39)
z
𝛾,n+1≥z𝛾k+
n
∑
j=1
m
∑
i=1
( (pj)⋅xjki)𝛾=0, …,Γ
;
k=1, …,n
(40)
z
𝛾,n+1≥z𝛾−1,k+
n
∑
j=1
m
∑
i=1
(( (pj)+
(pj)) ⋅xjki)𝛾=1, …,Γ
;
k=𝛾,…,n
838
J.-N.Buckow e al.
By he modi ica ions desc ibed abo e, he MIP o mula ion (35)-(43) esul s, whe e
cons ain s (22)-(26) a e copied om he nominal MIP. The objec i e(35) mini-
mizes he makespan by conside ing a iable
zΓ,n+1
co esponding o he inal s a e
in he dynamic p og am. The dynamic p og amming ecu sion is implemen ed by
cons ain s(36)-(40), whe e some cases o he maximum e ms a e summa ized as
hey exp ess he same. Cons ain s (36) ensu e ha he s acke c ane a el du a-
ions
d
(𝜋
k
)=d
k
o
+d
k
om
o e ie e palle 
𝜋k
o 
k=1, …,n
a e p ope ly conside ed
in he ecu sion.
The nominal and wo s -case palle p ocessing imes o he palle p edecesso s a
he I/O-poin s a e aken in o accoun by cons ain s(37) and(38), espec i ely. Due
o he big-M condi ions, hese cons ain s a e only ac i e i he wo conside ed jobs
a e p ocessed on he same I/O-poin . Simila o he nominal case, he objec i e alue
o each easible solu ion se es as an uppe bound o pa ame e M, since only con-
s ain s(37) and(38) which con ol he objec i e alue con ain big-M condi ions,
allowing i o be se o
Cons ain s(39) and(40) gua an ee ha he makespan o each alue
𝛾∈{1, …,Γ}
is de ined as he la ges comple ion ime o a palle . Finally, he a iable domains a e
de ined by cons ain s(41)-(43).
4.2 Bu e ing a ian
This subsec ion ackles he bu e ing case wi h mul iple I/O-poin s. S a ing wi h a
ma hema ical model o he nominal a ian 
PRPPBu
in Sec .4.2.1, he wo s -case
e alua ion o he obus coun e pa 
PRPPR
Bu
is sol ed by dynamic p og amming in
Sec .4.2.2. E en ually, Sec .4.2.3 inco po a es his dynamic p og amming app oach
in o he ma hema ical model o he nominal case.
4.2.1 Nominal case
By adap ing he MIP o mula ion (21)-(33) o 
PRPPBl
as desc ibed in Subsec-
ion4.1.1, we nex de i e he model(45)-(52) o 
PRPPBu
. In his model, we keep
he objec i e unc ion(45), he cons ain s (22)-(26), as well as all ou a iable
(41)
x
jki ∈{0, 1}
j,k=1, …,n;
i=1, …,m
(42)
dk
o
,d
k
om
≥0k=1, …,
n
(43)
z
𝛾k≥0𝛾
=0, …,Γ;
k=0, …,n+1
(44)
M
=
∑
p∈P
( (p)+
(p)) +
∑
𝓁
i
,𝓁
j
∈L
𝜏[𝓁i,𝓁j]
.
839
In eg a ed palle e ie al andp ocessing inwa ehouses…
ypes(49)-(52). No e ha we also keep cons ain s(27) and(28) ha a e ele an o
he makespan calcula ion and epea hem in(46) and(47) o be e eadabili y. Fu -
he mo e, we add cons ain s(48) o ensu e ha each palle is only p ocessed a e
he s acke c ane has b ough i o he assigned I/O-poin , whe e no idle imes a e
conside ed due o su icien bu e space. No e ha in cons ain s(52) de ining he
s a ing ime a iables, no a iable
s0
is needed compa ed o inequali ies(33), as we
ha e cons ain s(48) a he han cons ain s(29). Again, since only cons ain s(47)
con olling he objec i e alue con ain big-M condi ions, pa ame e M can also be
se acco ding o equa ion(34).
4.2.2 Dynamic p og amming
In he ollowing, we p esen a dynamic p og amming app oach o he wo s -case
e alua ion o 
PRPPR
Bl
, meaning o de e mine he palle s he ad e sa y chooses o
delay once he s acke c ane mo emen cha ac e ized by
𝜋
and
𝛼
is ixed. Due o
su icien bu e space in he case o 
PRPPR
Bl
, a palle 
p∈P
is eady o p ocessing
(MIP-PRPPBu)
(45)
min Cmax
s. . (22)−(26)
(46)
C
max ≥sk+
n
∑
j=1
m
∑
i=1
( (pj)⋅xjki)k=1, …,
n
(47)
s
k≥sk�+
n
∑
j=1
( (pj)⋅xjk�i)−M⋅
(
2−
n
∑
j=1
(xjki +xjk�i)
)k=2, …,n;
k�=1, …,k−
1;
i=1, …,m
(48)
s
k≥
k
∑
k
�
=1
(dk�
o +dk�
om)k=1, …,
n
(49)
x
jki ∈{0, 1}
j,k=1, …,n;
i=1, …,m
(50)
dk
o
,d
k
om
≥0k=1, …,
n
(51)
Cmax
≥
0
(52)
sk
≥
0k=1, …,n
840
J.-N.Buckow e al.
as soon as he s acke c ane has b ough i o i s assigned I/O-poin , and we deno e
his poin in ime as he palle ’s elease da e (p). Due o he elease da es and he
objec i e unc ion o minimizing he makespan
Cmax
ha is de e mined only by one
I/O-poin , he e always exis s an op imal solu ion in which he ad e sa y only delays
palle s p ocessed a one speci ic I/O-poin . The e o e, he p oblem o compu e he
delayed palle s o gi en
𝜋
and
𝛼
in
PRPPR
Bl
can be handled o each I/O-poin inde-
penden ly and by aking one wi h he la ges esul ing makespan
Cmax
.
Due o he discussion abo e, a dynamic p og amming app oach conside ing
only one I/O-poin a a ime is su icien o he wo s -case e alua ion. Recall
ha p oblem
PRPPBl
wi h a single I/O-poin is ela ed o he wo machine p ob-
lem
F2||Cmax
, whe e he s acke c ane o ms he i s machine, and he single I/O-
poin co esponds o he second machine. To deal wi h he wo s -case e alua ion
o p oblem
F2||Cmax
wi h budge ed unce ain y, Le o a o e al (2022) p esen a
dynamic p og amming app oach. Howe e , since hey assume ha he job p o-
cessing imes on bo h machines a e unce ain, hei app oach is no di ec ly appli-
cable o ou se ing. In ou case, he s acke c ane a el imes a e ce ain, and
only he palle p ocessing imes a he I/O-poin s a e subjec o unce ain y. We
he e o e p esen an adap ed a ian o hei dynamic p og amming app oach o
ackle ou se ing.
In ou app oach, we ha e s a es
z𝛾k∈ℝ+
ha indica e he wo s -case makes-
pan when a mos 
𝛾∈{0, …,Γ}
palle s can be delayed, and only he palle s p o-
cessed a posi ions
0, …,k
on he cu en machine a e aken in o accoun . No e ha
o a gi en
𝛾
, he numbe o s a es can be educed by conside ing only he alues
k∈{𝛾,…,n−Γ+𝛾}
because he emaining s a es a e ne e pa o a longes pa h
in he esul ing ne wo k. Ou ini ializa ion is simply
z00 =0
, since no palle is p o-
cessed o 
𝛾=0
and
k=0
. In he ecu sion, we dis inguish he ollowing h ee
cases.
• Fo 
𝛾=0
and
k=1, …,n−Γ
, we ha e
z0k
=max{ (𝜋
k
),z
0,k−1
}+ (𝜋
k)
, because
no palle can be delayed a all, and we need o conside bo h he elease da e
(𝜋k)
o he palle a hek h posi ion as well as he comple ion ime
z0,k−1
o he palle
a he p e ious posi ion
k−1
.
• Fo 
𝛾=1, …,Γ
and
k=𝛾
, hek h palle can always be assumed o be delayed,
and we hus ha e
z𝛾k
=max{ (𝜋
k
),z
𝛾−1,k−1
}+ (𝜋
k
)+

(𝜋
k)
.
• Fo 
𝛾=1, …,Γ
and
k=𝛾+1, …,n−Γ+𝛾
, we ha e o conside he wo cases
ha he cu en palle is delayed o no and ake he maximum, leading o
The p esen ed dynamic p og amming app oach has he o e all un ime
O(Γ ⋅n)
, as
we ha e s a es
z𝛾k
o 
𝛾=0, …,Γ
and
k=𝛾,…,n−Γ+𝛾
. Since we ha e o apply
he dynamic p og amming algo i hm o each I/O-poin independen ly and aking
he maximum, he wo s -case e alua ion o 
PRPPR
Bu
has he un ime
O(Γ ⋅n⋅m)
.
z
𝛾k=max{max{ (𝜋k),z𝛾,k−1}+ (𝜋k), max{ (𝜋k),z𝛾−1,k−1}+ (𝜋k)+

(𝜋k
)}
=max{ (𝜋
k
)+ (𝜋
k
)+
(𝜋
k
),z
𝛾,k−1
+ (𝜋
j
),z
𝛾−1,k−1
+ (𝜋
j
)+
(𝜋
k
)}.
847
In eg a ed palle e ie al andp ocessing inwa ehouses…
esul s. Fu he mo e, he makespan inc eases a e basically he same in he blocking
and bu e ing case, apa om a ew di e ences in some combina ions. Since he
esul s depic ed in Fig.10 disclose ha he obus models o he
PRPP
wi h budg-
e ed unce ain y lead o conside ably be e esul s han he nominal models, we con-
clude ha he obus case needs i s own speci ic models o be ackled app op ia ely.
To also in es iga e how sensi i e ou obus MIP models eac o changes in he
unce ain y budge 
Γ
, we conduc ed a sensi i i y analysis in ano he expe imen . In
ha expe imen , we dis inguish be ween wo ypes o 
Γ
o he sake o cla i y. On
he one hand, we ha e
Γal
which is ac ually used in he algo i hms o sol e he mod-
els, and on he o he hand, we ha e
Γe
o he wo s -case e alua ion o he esul ing
solu ions using he dynamic p og amming algo i hms. Fo all ins ances wi h
n≤10
palle s, we e alua ed he solu ions ob ained by bo h he nominal models (
Γal =0
)
and he obus models (
Γal =3
) o di e en alues o 
Γe ∈{0, 1, 2, 3, 4, 5}
. Fig-
u e11 depic s o bo h he blocking and bu e ing a ian s he a e age a ios o he
nominal o he obus objec i e alues, di e en ia ed by
Γe
. Ra ios smalle han1.0
mean ha he nominal models ob ained be e solu ions, while a ios la ge han1.0
indica e ha he obus models gene a ed supe io solu ions.
I can be seen in Fig.11 ha he a ios a e below1.0 only o 
Γe =0
, meaning
ha he solu ion quali y o he nominal models only exceeds he solu ion quali y o
he obus models i he e is no unce ain y a all. Mo eo e , he solu ion quali y o
he nominal and obus models is nea ly he same o 
Γe =1
, since he a ios a e
only a li le abo e1.0. The a ios each mo e han1.1 o 
Γe =2
, and con inue o
ise e en mo e wi h g owing
Γe
, wi h he a ios ising as e in he blocking case,
while he bu e ing case eaches sa u a ion ea lie . The bene i s o he blocking
model hus seem o be mode a ely la ge han hose o he bu e ing model, as he
a ios a e gene ally a bi la ge . Howe e , he bu e ing model seems o be sligh ly
mo e esilien o changes in
Γe
, as he inc ease in he a ios becomes a he small a
a ce ain poin . O e all, he obus models yield a s able gain compa ed o he nomi-
nal models o all di e en alues o 
Γe
excep 0, showing ha ou obus models
a e qui e insensi i e o changes in he unce ain y budge 
Γ
.
Fig. 11 A e age a ios o he
nominal (
Γal =0
) o he obus
(
Γal =3
) makespans, sepa a ed
by he blocking and bu e ing
a ian , and e alua ed o di -
e en 
Γe

848
J.-N.Buckow e al.
5.4 Bene i s o bu e s
In he nex expe imen , we examined he bene i s o ha ing a bu e a each I/O-
poin by compa ing he blocking a ian 
PRPPBl
wi h he bu e ing a ian 
PRPPBu
.
No e ha o any gi en ins ance, he op imal makespan in he bu e ing a ian is
a leas as good as in he blocking a ian , since he bu e ing a ian elaxes he
blocking cons ain . The bene i s o he bu e a e measu ed by he esul ing a e age
pe cen age makespan inc eases o he blocking compa ed o he bu e ing a ian ,
hus co esponding o he equi ed makespan inc eases when ha ing no bu e a all.
No e ha he highe he makespan inc eases, he la ge he bene i s o ha ing bu -
e s. To calcula e hese makespan inc eases, we used he esul s ob ained om bo h
he nominal models MIP-
PRPPBl
and MIP-
PRPPBu
(see Sec s.4.1.1 and4.2.1) as
well as he obus models MIP-
PRPPR
Bl
and MIP-
PRPPR
Bu
(see Sec s.4.1.3 and4.2.3).
Fo he nominal and obus case, he a e age pe cen age makespan inc eases a e
displayed in Fig.12 o all combina ions o pa ame e sn andm, sepa a ed by he
nominal and obus case. I can be seen ha mos makespan inc eases a e in he
single-digi pe cen age ange ( emembe ha he la ge he makespan inc eases,
he bigge he bene i s o he bu e s), showing ha ha ing a bu e conside able
educes he makespan. These makespan inc eases become e en la ge in he obus
case compa ed o he nominal case, caused by he ac ha solu ions o he block-
ing a ian a e mo e ulne able o inc eases in he palle p ocessing imes as hese
canno be bu e ed. Gene ally, he esul s show ha i is e y wo hwhile o use a
bu e , pa icula ly in he obus case. This shows p ac i ione s ha bu e s should be
ins alled a he I/O-poin s whene e possible.
In p elimina y expe imen s, we also analyzed he solu ion s uc u e in he
case o 
PRPPBu
, showing ha he bu e space is ac ually used egula ly. Fo he
smalle ins ances wi h
n≤10
palle s, one o wo palle s a e o en s o ed a one
Fig. 12 A e age pe cen age makespan inc eases o he blocking compa ed o he bu e ing a ian , sepa-
a ed by he nominal and obus case and by pa ame e sn andm
849
In eg a ed palle e ie al andp ocessing inwa ehouses…
I/O-poin simul aneously. Howe e , we also analyzed heu is ic solu ions o he
la ge ins ances wi h
n≥50
palle s, whe e some imes up o20 palle s a e s o ed
a one I/O-poin simul aneously. Mo eo e , he be e he solu ion quali y is, he
mo e o en he bu e ends o be used, explaining why he esul ing makespans
o 
PRPPBu
a e on a e age much lowe han o 
PRPPBl
.
5.5 Heu is ics
P elimina y es s ha e shown ha CPLEX wi hou wa m-s a akes up o a min-
u e o se up he ma hema ical models o he la ge ins ances wi h
n=100
pal-
le s, meaning i canno quickly ind e en easible solu ions. In o de o also sol e
la ge ins ances p ope ly in a easonable amoun o compu ing ime, we imple-
men ed some heu is ics in he las expe imen . These heu is ics can be used o
bo h
PRPPR
Bl
and
PRPPR
Bu
, as hey wo k wi h he same solu ion ep esen a ion con-
sis ing o bo h he palle e ie al sequence
𝜋
and he assignmen 
𝛼
o palle s o
I/O-poin s. Mo eo e , e en i hese heu is ics a e designed o handle he obus
case, no e ha hey can also be used o ackle he nominal case simply by se -
ing
Γ=0
. O e all, we implemen ed he ollowing ou heu is ics.
• G eedy heu is ic (GD). S a ing wi h an emp y solu ion, he palle s a e
g eedily appended o i by checking all pai s o I/O-poin s and emaining pal-
le s. In each s ep, a pai is chosen ha leads o he smalles makespan o he
esul ing pa ial solu ion. Such pa ial solu ions a e e alua ed by applying he
dynamic p og amming algo i hms p esen ed in Sec .4.
• Random heu is ic (RA). By andomly choosing bo h he palle e ie al
sequence
𝜋
and he assignmen 
𝛼
o palle s o I/O-poin s, solu ions a e sam-
pled un il a compu a ion ime limi is eached. Finally, he bes o all sampled
solu ions is e u ned.
• I e a i e imp o emen (II). Ini ially, a easible solu ion is de e mined using
he g eedy heu is ic p esen ed abo e. This ini ial solu ion is hen i e a i ely
imp o ed by sea ching wo neighbo hoods one a e he o he un il a local
op imum is eached. In he i s neighbo hood, wo palle s in he e ie al
sequence a e swapped, and new bes I/O-poin s a e assigned o bo h swapped
palle s by checking all possibili ies. In he second neighbo hood, h ee palle s
in he e ie al sequence a e eo de ed in a bes possible way by checking all
six pe mu a ions o hese h ee palle s and also assigning hem o bes I/O-
poin s. In each i e a ion, he second neighbo hood is sea ched only i he i s
neighbo hood yields no u he imp o emen s. This p ocedu e e mina es p e-
ma u ely e en i no local op imum has been eached a e a gi en compu a ion
imelimi .
• Tabu sea ch (TS). The abu sea ch also s a s wi h an ini ial solu ion gene a ed
by he g eedy heu is ic. This solu ion is g adually al e ed using he i s neigh-
bo hood desc ibed in he i e a i e imp o emen algo i hm, i.e., wo palle s a e
swapped in he e ie al sequence and new bes I/O-poin s a e chosen o hem.
850
J.-N.Buckow e al.
The i s imp o ing neighbo solu ion ound is always aken, and i no imp o ing
neighbo solu ion exis s, a bes neighbo solu ion is aken o which he ansi ion
o i is no ma ked as abu in he abu lis . The ansi ion o a neighbo solu ion
is conside ed as abu i he iple consis ing o he wo posi ions o bo h palle s
swapped and he objec i e alue o he gene a ed neighbo solu ion is al eady
con ained as an en y in he abu lis . New abu lis en ies a e appended o he
end o he abu lis , and i he eby he maximum abu lis size
𝜓=500
(a alue
ha appea ed e ec i e in p elimina y expe imen s) is exceeded, he i s en y
in he abu lis is emo ed. The abu sea ch e mina es a e a gi en compu a ion
ime limi and e u ns he bes solu ion ound so a .
Figu e13 depic s he esul s o all ou heu is ics o he obus p oblem a i-
an s
PRPPR
Bl
(le ) as well as
PRPPR
Bu
( igh ) and di e en numbe s o palle sn. These
esul s a e epo ed by a e age pe cen age gaps o bes known solu ions (BKS) o he
espec i e ins ances, which co espond o he bes solu ions ound du ing all expe i-
men s pe o med, including ou es s o he obus models MIP-
PRPPR
Bl
and MIP-
PRPPR
Bu
p esen ed in Sec s.4.1.3 and4.2.3. In pa icula , no e ha he BKS alues
o all ins ances wi h
n≤8
co espond o op imal objec i e alues. Fu he mo e, a
compu ing ime limi o one minu e pe un was imposed in his expe imen , e en i
heu is icsGH andII equi ed much smalle compu ing imes on mos ins ances.
O e all, Fig.13 e eals ha he di e ences in he heu is ic esul s be ween he
blocking and bu e ing case a e gene ally a he small. None heless, i is e iden ha
heu is icTS pe o ms bes , as i s a e age gaps a e well below
1%
in all es ed com-
bina ions. Wha is pa icula ly ema kable abou hese esul s is ha heu is icTS
eached gaps o almos 
0%
o all ins ances wi h
n≤10
, showing ha i sol ed hese
small ins ances nea ly op imally. Heu is ic II pe o ms second bes , ha ing a e -
age gaps unde 
3%
in all es ed combina ions. The esul s o heu is icRA a e less
Fig. 13 A e age pe cen age gaps o he heu is ics o BKS alues, di e en ia ed by he blocking and bu -
e ing a ian and by pa ame e n
851
In eg a ed palle e ie al andp ocessing inwa ehouses…
consis en , he e a e e y small gaps o ins ances wi h
n≤8
, while o he la ge
ins ances he e a e conside able gaps o up o
20%
. The cons uc ion heu is icGD
pe o ms wo s wi h mos ly double-digi pe cen age gaps e en o small ins ances.
Howe e , his is mainly because cons uc ion heu is ic GD equi ed much less
compu ing ime han he o he heu is ics, aking less han one second on any gi en
ins ance.
Since heu is ics II and TS ha e e y small gaps in all es ed combina ions,
he
PRPP
seems o be well sol able on ins ances o la ge , p ac ically ele an sizes
o up o
n=100
palle s as in he case o he a o emen ioned company. Al hough
knowing ha he palle p ocessing imes a e s ill ele an , he company concen a es
on he s acke c ane a el imes in hei cu en planning. Ne e heless, discussions
wi h p ac i ione s a he company e ealed ha hey unde es ima ed he op imiza ion
po en ial gained by addi ionally conside ing he palle p ocessing imes.
No e ha p elimina y es s showed ha heu is icsII andTS a e much supe io in
sol ing la ge ins ances compa ed o he MIP models p esen ed in Sec .4 and using
CPLEX wi hou wa m-s a . As al eady men ioned abo e, heu is icII is hence used
o wa m-s a he MIP models. Fo se e al la ge ins ances wi h
n≥50
palle s, heu-
is icII did no each a local op imum wi hin he one minu e ime limi . Ne e he-
less, o he smalle ins ances wi h
n≤10
palle s which we e also used o es he
MIP models, heu is icII equi ed e y li le compu ing ime o each a local op i-
mum, aking less han one second on any o hese ins ances. As heu is icII is able
o ind good solu ions on he smalle ins ances in a e y sho amoun o compu ing
ime, i appea s o be bes sui ed o MIP wa m-s a s.
While he MIP models we e only capable o sol ing some small ins ances wi h
a mos en palle s, p elimina y expe imen s also e ealed ha e en heu is ics II
andTS eached hei compu a ional limi s o ins ances wi h mo e han 100 pal-
le s. Fo such la ge ins ances, he sea ch o an imp o ing neighbo solu ion akes
conside able compu ing imes, esul ing in e y ew (i any a all) i e a ions being
comple ed in a easonable amoun o ime, highligh ing how di icul he
PRPP
is o
sol e.
6 Conclusions
In his pape , we s udied and e alua ed di e en a ian s o he
PRPP
, an in eg a ed
p oblem conside ing bo h he e ie al and p ocessing o palle s in wa ehouses wi h
mul iple I/O-poin s. We di e en ia e be ween he blocking and bu e ing p oblem
a ian , depending on whe he he e is su icien bu e space a he I/O-poin s o
empo a ily s o ing palle s o no . Addi ionally, o p o ec agains unce ain ies in
palle p ocessing imes, we apply obus op imiza ion wi h budge ed unce ain y
se s.
When ha ing jus a single I/O-poin , he blocking and he bu e ing a ian s a e
equi alen o well-known wo-machine low-shop scheduling p oblems, allowing
o sol e he single I/O-poin case o hese wo a ian s wi hou obus ness in poly-
nomial ime. Mo eo e , we p o ed ha e en he obus single I/O-poin blocking
852
J.-N.Buckow e al.
a ian can be sol ed in polynomial ime, while he complexi y o he obus bu e -
ing a ian wi h only one I/O-poin emains an open ques ion. Fo he gene al case
wi h an a bi a y numbe o I/O-poin s, ma hema ical models we e p esen ed o
bo h he blocking and he bu e ing a ian . Fu he mo e, dynamic p og amming
algo i hms o he wo s -case e alua ion o he a ian s wi h unce ain y we e de el-
oped, which we e hen in eg a ed in o he nominal ma hema ical models o ob ain
obus models.
The compu a ional s udy disclosed ha ou new in eg a ed models o he
PRPP
achie ed much be e esul s han exis ing models o palle e ie al op imiza ion
o pa allel machine scheduling p oblems. This shows ha bo h he s acke c ane
a el imes as well as he palle p ocessing imes mus be aken in o accoun o
sol e he
PRPP
adequa ely. Compa ed o he nominal in eg a ed models, ou obus
models u ned ou o be conside ably be e a hedging agains unce ain ies in he
palle p ocessing imes. The compa ison be ween he blocking and bu e ing a i-
an s shows ha in bo h he nominal and obus case he makespan can be educed
subs an ially by se ing up bu e space a he I/O-poin s. To sol e la ge ins ances
app op ia ely in a sho amoun o compu ing ime, an i e a i e imp o emen p oce-
du e and a abu sea ch pe o med well.
Finally, ou in eg a ed models ha e shown o be sui able o add essing he
new complex p oblem in ol ing bo h palle e ie al and p ocessing. The addi-
ional in eg a ion o obus op imiza ion leads o mo e esilien schedules, hedging
agains unce ain ies. In some solu ions ob ained in he bu e ing case on he la ge
ins ances, up o20 palle s a e s o ed a one I/O-poin simul aneously, whe e an in i-
ni e bu e capaci y was p esumed. The e o e, u u e esea ch could explo e a mo e
gene al a ian mixing he blocking and bu e ing case by assuming an a bi a y
ini e bu e capaci y.
Appendix A. De ailed MIP esul s
Tables4 and5 show he esul s o he ou ma hema ical models p esen ed in Sec .4
ob ained by CPLEX wi hin an one hou compu a ional ime limi . The esul s in
Table4 e e o he nominal in eg a ed models MIP-
PRPPBl
and MIP-
PRPPBu
in o-
duced in Sec s.4.1.1 and4.2.1, while he esul s in Table5 e e o he obus in e-
g a ed models MIP-
PRPPR
Bl
and MIP-
PRPPR
Bu
p esen ed in Sec s.4.1.3 and4.2.3. In
bo h ables, he esul s a e di e en ia ed by he pa ame e sn andm as well as he
blocking (le ) and bu e ing case ( igh ). Fo each gi en combina ion, he numbe
o solu ions e i ied as op imally sol ed, he a e age op imali y gaps epo ed by
CPLEX, and he a e age compu a ional imes equi ed a elis ed.
I can be seen in Tables4 and5 ha all ins ances wi h
n≤8
palle s we e e i ied
as op imally sol ed, whe eas some ins ances wi h
n≥9
palle s could no be e i ied
wi hin he ime limi . O e all, he compu ing imes ise subs an ially wi h inc eas-
ing numbe s o palle sn and I/O-poin sm. The gene al ends a e he same in he
nominal and obus case, bu he compu ing imes and op imali y gaps inc ease a
bi as e in he obus case. O e all, an ins ance size o a ound
n=10
palle s seems

853
In eg a ed palle e ie al andp ocessing inwa ehouses…
Table 4 Nominal MIP esul s
n m
Blocking Bu e ing
#Op A g. gap [%] A g. ime [s] #Op A g. gap [%] A g. ime [s]
5 1 10 0.0 0.0 10 0.0 0.0
2 10 0.0 0.1 10 0.0 0.1
3 10 0.0 0.1 10 0.0 0.1
6 1 10 0.0 0.0 10 0.0 0.0
2 10 0.0 0.2 10 0.0 0.2
3 10 0.0 0.4 10 0.0 0.3
7 1 10 0.0 0.1 10 0.0 0.1
2 10 0.0 1.4 10 0.0 1.3
3 10 0.0 4.6 10 0.0 2.7
8 1 10 0.0 0.4 10 0.0 1.0
2 10 0.0 13.0 10 0.0 12.4
3 10 0.0 292.9 10 0.0 165.9
9 1 10 0.0 1.4 10 0.0 4.0
2 10 0.0 54.5 10 0.0 119.4
3 9 0.6 682.5 9 1.3 773.4
10 1 10 0.0 14.8 10 0.0 47.5
2 8 1.6 1307.3 6 2.3 1842.6
3 6 3.0 2452.6 8 2.5 1919.8
Table 5 Robus MIP esul s
n m
Blocking Bu e ing
#Op A g. gap [%] A g. ime [s] #Op A g. gap [%] A g. ime [s]
5 1 10 0.0 0.0 10 0.0 0.0
2 10 0.0 0.1 10 0.0 0.1
3 10 0.0 0.2 10 0.0 0.2
6 1 10 0.0 0.1 10 0.0 0.1
2 10 0.0 0.6 10 0.0 0.4
3 10 0.0 1.4 10 0.0 0.9
7 1 10 0.0 0.2 10 0.0 0.2
2 10 0.0 2.5 10 0.0 2.2
3 10 0.0 10.6 10 0.0 8.0
8 1 10 0.0 0.6 10 0.0 0.4
2 10 0.0 23.0 10 0.0 17.5
3 10 0.0 188.3 10 0.0 177.3
9 1 10 0.0 3.3 10 0.0 2.3
2 10 0.0 444.1 10 0.0 219.9
3 8 1.6 1329.1 9 1.8 1132.3
10 1 10 0.0 23.5 10 0.0 16.2
2 3 8.0 3013.6 5 4.5 2563.4
3 1 17.7 3354.6 3 7.5 2969.1
854
J.-N.Buckow e al.
o be he compu a ional limi beyond which ins ances can no longe be sol ed well
using he gi en MIP models.
Acknowledgemen s The au ho s a e g a e ul o he edi o s and wo anonymous e e ees o hei help ul
and cons uc i e commen s.
Funding Open Access unding enabled and o ganized by P ojek DEAL.
Da a A ailibili y All ins ances and esul s can be ound a h p:// www2. in o ma ik. uos. de/ kombo p / da a/
op/.
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 mis-
sion 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
Allah e di A (2015) The hi d comp ehensi e su ey on scheduling p oblems wi h se up imes/cos s.
Eu opean Jou nal o Ope a ional Resea ch 246(2):345–378
Allah e di A, Gup a J, Aldowaisan T (1999) A e iew o scheduling esea ch in ol ing se up conside a-
ions. Omega 27(2):219–239
Allah e di A, Ng C, Cheng T e al (2008) A su ey o scheduling p oblems wi h se up imes o cos s.
Eu opean Jou nal o Ope a ional Resea ch 187(3):985–1032
Ang M, Lim Y, Sim M (2012) Robus s o age assignmen in uni -load wa ehouses. Managemen Science
58(11):2114–2130
Ben-Tal A, Go yashko A, Gusli ze E e al (2004) Adjus able obus solu ions o unce ain linea p o-
g ams. Ma hema ical P og amming 99(2):351–376
Ben-Tal A, El Ghaoui L, Nemi o ski A (2009) Robus op imiza ion, ol 28. P ince on Uni e si y P ess
Be simas D, den He og D (2022) Robus and adap i e op imiza ion. Dynamic Ideas LLC
Be simas D, Sim M (2003) Robus disc e e op imiza ion and ne wo k lows. Ma hema ical P og amming
98(1):49–71
Be simas D, Sim M (2004) The p ice o obus ness. Ope a ions Resea ch 52(1):35–53
Bold M, Goe igk M (2021) A compac e o mula ion o he wo-s age obus esou ce-cons ained p ojec
scheduling p oblem. Compu e s & Ope a ions Resea ch 130:105232
Boysen N, S ephan K (2016) A su ey on single c ane scheduling in au oma ed s o age/ e ie al sys ems.
Eu opean Jou nal o Ope a ional Resea ch 254(3):691–704
B uni M, Di Puglia Pugliese L, Be aldi P e al (2017) An adjus able obus op imiza ion model o he
esou ce-cons ained p ojec scheduling p oblem wi h unce ain ac i i y du a ions. Omega 71:66–84
Buckow JN, Goe igk M, Knus S (2024) Re ie al op imiza ion in a wa ehouse wi h mul iple inpu /ou -
pu -poin s. OR Spec um. h ps:// doi. o g/ 10. 1007/ s00291- 024- 00775-x
Chen ZL, Hall N (2022) Supply chain scheduling, In e na ional Se ies in Ope a ions Resea ch & Man-
agemen Science, ol 323. Sp inge
de Kos e R, Le-Duc T, Zae pou N (2012) De e mining he numbe o zones in a pick-and-so o de
picking sys em. In e na ional Jou nal o P oduc ion Resea ch 50(3):757–771
Gilmo e P, Gomo y R (1964) Sequencing a one s a e- a iable machine: A sol able case o he a eling
salesman p oblem. Ope a ions Resea ch 12(5):655–679
Goe igk M, Ha isch M (2024) An in oduc ion o obus combina o ial op imiza ion, In e na ional Se ies
in Ope a ions Resea ch & Managemen Science, ol 361. Sp inge
855
In eg a ed palle e ie al andp ocessing inwa ehouses…
Goe igk M, G ün B, Heßle P (2013) B anch and bound algo i hms o he bus e acua ion p oblem.
Compu e s & Ope a ions Resea ch 40(12):3010–3020
Gong Y, de Kos e R (2011) A e iew on s ochas ic models and analysis o wa ehouse ope a ions. Logis-
ics Resea ch 3(4):191–205
Hosseini A, O o A, Pesch E (2024) Scheduling in manu ac u ing wi h anspo a ion: Classi ica ion and
solu ion echniques. Eu opean Jou nal o Ope a ional Resea ch 315(3):821–843
Jiang X, Sun L, Zhang Y e al (2022) O de ba ching and sequencing o minimising he o al o de com-
ple ion ime in pick-and-so wa ehouses. Expe Sys ems wi h Applica ions 187:115943
Jiu S (2022) Robus omnichannel e ail ope a ions wi h he implemen a ion o ship- om-s o e. T anspo -
a ion Resea ch Pa E: Logis ics and T anspo a ion Re iew 157:102550
Johnson S (1954) Op imal wo-and h ee-s age p oduc ion schedules wi h se up imes included. Na al
Resea ch Logis ics Qua e ly 1(1):61–68
Le o a o M, Figuei edo R, F o a Y (2022) Exac solu ions o he wo-machine obus low shop wi h
budge ed unce ain y. Eu opean Jou nal o Ope a ional Resea ch 300(1):46–57
Miya a H, Nagano M (2019) The blocking low shop scheduling p oblem: A comp ehensi e and concep-
ual e iew. Expe Sys ems wi h Applica ions 137:130–156
Qiu R, Sun Y, Sun M (2022) A obus op imiza ion app oach o mul i-p oduc in en o y managemen in
a dual-channel wa ehouse unde demand unce ain ies. Omega 109:102591
Reddi S, Ramamoo hy C (1972) On he low-shop sequencing p oblem wi h no wai in p ocess. Jou nal
o he Ope a ional Resea ch Socie y 23(3):323–331
Roodbe gen K, Vis I (2009) A su ey o li e a u e on au oma ed s o age and e ie al sys ems. Eu opean
Jou nal o Ope a ional Resea ch 194(2):343–362
Sun Y, Qiu R, Sun M (2024) A obus op imiza ion app oach o in en o y managemen wi h limi ed-
ime discoun s and se ice-le el equi emen unde demand unce ain y. In e na ional Jou nal o
P oduc ion Economics 267:109096
Teck S, Dewil R, Vans eenwegen P (2024) A simula ion-based gene ic algo i hm o a semi-au o-
ma ed wa ehouse scheduling p oblem wi h p ocessing ime a iabili y. Applied So Compu ing
160:111713
Tho sen A, Yao T (2015) Robus in en o y con ol unde demand and lead ime unce ain y. Annals o
Ope a ions Resea ch 257(1):207–236
an Dal R, an de Veen J, Sie ksma G (1993) Small and la ge TSP: Two polynomially sol able cases o
he a eling salesman p oblem. Eu opean Jou nal o Ope a ional Resea ch 69(1):107–120
Yanıkoğlu İ, Go issen B, den He og D (2019) A su ey o adjus able obus op imiza ion. Eu opean
Jou nal o Ope a ional Resea ch 277(3):799–813
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.