Scheduling of e-commerce packaging machines: blocking machines and their impact on the performance–waste tradeoff

B isko n, Di k; Boysen, Nils; Zey, Lenna
A icle — Published Ve sion
Scheduling o e-comme ce packaging machines: blocking
machines and hei impac on he pe o mance–was e
adeo
Jou nal o Scheduling
P o ided in Coope a ion wi h:
Sp inge Na u e
Sugges ed Ci a ion: B isko n, Di k; Boysen, Nils; Zey, Lenna (2024) : Scheduling o e-comme ce
packaging machines: blocking machines and hei impac on he pe o mance–was e adeo ,
Jou nal o Scheduling, ISSN 1099-1425, Sp inge US, New Yo k, NY, Vol. 28, Iss. 1, pp. 101-120,
h ps://doi.o g/10.1007/s10951-024-00826-9
This Ve sion is a ailable a :
h ps://hdl.handle.ne /10419/323370
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/
Jou nal o Scheduling (2025) 28:101–120
h ps://doi.o g/10.1007/s10951-024-00826-9
Scheduling o e-comme ce packaging machines: blocking machines
and hei impac on he pe o mance–was e adeo
Di k B isko n1·Nils Boysen2·Lenna Zey1
Accep ed: 1 Oc obe 2024 / Published online: 25 Oc obe 2024
© The Au ho (s) 2024
Abs ac
To s eamline hei ul illmen p ocesses, many e-comme ce e aile s oday use au oma ed packaging machines o hei
ou bound pa cels. An impo an pe o mance–was e adeo is associa ed wi h hese machines: To educe packaging was e
when handling di e en sized goods, packaging machines should be able o handle di e en ca on sizes. Howe e , mo e
ca on sizes lead o a mo e in ol ed scheduling p ocess, so ha he h oughpu pe o mance de e io a es (and ice e sa). To
in es iga e his adeo , his pape de elops scheduling p ocedu es o a speci ic ype o packaging machine, called blocking
machines. These packaging machines p o ide mul iple back- o-back packaging de ices, each con inuously p ocessing a
dedica ed ca on size, bu blocking each o he whene e incoming goods a e no p ope ly o de ed acco ding o ca on sizes
on he in eed con eyo . To educe he esul ing h oughpu loss, we de i e a ious scheduling p oblems o op imizing he
in low o goods, p o ide a ho ough analysis o he compu a ional complexi y, and de i e an exac dynamic p og amming
app oach ha is polynomial in he numbe o o de s o be packed. This allows us o sol e e en la ge eal-wo ld ins ances o
p o en op imali y wi h which we can analyze he pe o mance–was e adeo o blocking machines.
Keywo ds E-comme ce ·Packaging machines ·En i onmen al impac ·Scheduling
1 In oduc ion
Because o he epe i i e and physically demanding na u e o
wa ehouse wo k, many e o s ha e been made o educe he
bu den on human wo ke s. In addi ion o o kli s and con-
eyo s, which ha e an e en longe adi ion, c ane-ope a ed
high-bay wa ehouses, o example, ha e been assis ing in he
s o age and e ie al o goods since he 1960s (Boysen and de
Kos e , 2024). D i en by he huge success o e-comme ce, he
las decades ha e seen u he p og ess in he ield o wa e-
BNils Boysen
[email p o ec ed]
h p://www.om.uni-jena.de
Di k B isko n
[email p o ec ed]
h p://www.p odlog.uni-wuppe al.de
Lenna Zey
[email p o ec ed]
1Be gische Uni e si ä Wuppe al, P o essu ü BWL,
insbesonde e P oduk ion und Logis ik, Raine -G uen e -S .
21, 42119 Wuppe al, Ge many
2F ied ich-Schille -Uni e si ä Jena, Leh s uhl ü Ope a ions
Managemen , Ca l-Zeiß-S aße 3, 07743 Jena, Ge many
house au oma ion (see Azadeh e al. 2019). Today, he e a e
au oma ed solu ions o all basic wa ehousing unc ions (see
Boysen e al. 2019): Fo example, he e a e mobile shel -
li ing obo s o he anspo unc ion, au onomous mobile
obo s o picking ec angula goods om shel es, obo ic
a ms wi h acuum g ippe s o picking om bins, mobile
obo s wi h il able ays o o de so ing, and indus ial
obo s o pala alizing boxes and ca ons.
This pape deals wi h he au oma ion o he packaging unc-
ion, whe e he picked (and consolida ed) p oduc s equi ed
by cus ome o de s a e ei he w apped in plas ic ilm o
packed in ca dboa d boxes by a ully au oma ed packaging
machine. Machines o he la e case, which we ocus on in
his pape , a e e y common in e-comme ce because ca d-
boa d boxes p o ide be e p o ec ion, especially o agile
goods (Escu sell e al., 2021). These machines a e ed wi h
goods and ca dboa d packaging ma e ial ia a con eyo and a
eeding sha , espec i ely. Mos machines include a cu ing
mechanism o educe he size o he boxes o i he o de s.
This a oids highe pos age cha ges and excess ill ma e-
ial caused by unnecessa ily la ge packages. The packaging
ma e ial is hen olded, sealed and labeled by he machine.
Finally, he inished boxes a e con eyed o he shipping a ea.
123
102 Jou nal o Scheduling (2025) 28:101–120
Fig. 1 Pape E-Com Fi o Hugo Beck wi h wo back- o-back packaging
de ices (Sou ce: Hugo Beck)
In hei packaging machine e alua ion pape , P ose e al.
(2021) epo s a e-o - he-a h oughpu pe o mance o up
o 1000 packages pe hou o single-piece o de s. Fo mul i-
piece o de s, h oughpu is lowe because hei a ie y is s ill
a g ea e echnological challenge. Howe e , since he majo -
i y o e-comme ce o de s a e o a single i em ( he a e age
numbe o i ems o de ed a Amazon Ge many, o example,
is only 1.6, see Boysen e al. 2019), au oma ed packaging
machines a e e y common in oday’s e-comme ce ul ill-
men cen e s.
The e a e se e al ypes o packaging machines, which we
compa e in mo e de ail in Sec .2. One common se up ha
we will ocus on in his pape is he blocking machine,shown
in Fig.1. To a oid he disad an ages o se ups whe e ca ons
mus be changed on- he- ly whene e a di e en ca on size is
equi ed, blocking machines use mul iple downs eam pack-
aging de ices, each o which is pe manen ly associa ed wi h
a speci ic ca on size. These subsequen packaging de ices
a e a anged back- o-back along he in eed con eyo , caus-
ing blockages whene e incoming goods a e no p ope ly
o de ed by size. Because goods canno o e ake each o he
on he in eed con eyo , a good ha is assigned o an ups eam
packaging de ice will block subsequen goods ha equi e a
downs eam de ice. Thus, one o mul iple packaging slo s
in a packaging ba ch (i.e., he se o o de s concu en ly
packed by all pa allel packaging de ices) emain emp y and a
blocking loss occu s. A sui able sequencing o o de s wi hin
he in eed sequence can educe he blocking loss and hus
imp o e he h oughpu pe o mance o a blocking machine.
This di ec ly leads o he ollowing pe o mance–was e ade-
o : Mo e ca on sizes o choose om educes packaging
was e, bu also ends o inc ease he loss o h oughpu pe o -
mance due o blockings. To explo e he pe o mance–was e
adeo , his pape p o ides he ollowing con ibu ions:
•We in oduce a no el scheduling p oblem o block-
ing machines ha minimizes blocking loss o di e en
in lows o o de s. Fo example, many e-comme ce e ail-
e s equip hei human picke s wi h mul i-bin picking ca s
o collec comple ed o de s in a so -while-pick picking
p ocess (e.g., see De Kos e e al. 2007). In his case, he
in low o a packing machine can be al e ed by changing
he o de in which hese ca s a e p ocessed and he o de
in which each ca ’s o de s a e placed on he machine’s
in eed con eyo . We desc ibe al e na i e in lows and hei
e ec on he scheduling p oblem in Sec .3.
•We p o ide a ho ough analysis o compu a ional com-
plexi y o all esul ing p oblem a ian s. This leads o
an exac dynamic p og amming (DP) algo i hm ha is
polynomial in he numbe o goods o be packed, once
he numbe o ca on sizes is ixed. This allows us o
sol e la ge ins ances o eal-wo ld size wi hin e y sho
un imes o p o en op imali y.
•Wi h his algo i hm in hand, we explo e he pe o mance–
was e adeo o packaging machines. Fo a gi en
numbe o ca on sizes o be p o ided, we i s op imize
a sui able selec ion o speci ic ca on sizes o minimize
packaging was e. Then, we minimize he blocking loss
by sol ing ou scheduling p oblem o he selec ed ca -
on sizes. This allows us o quan i y packaging was e and
h oughpu loss i di e en numbe s o ca on sizes a e
o be p o ided. This deli e s decision suppo o wa e-
house manage s who need o make he igh choice o
ca on sizes.
The es o he pape is o ganized as ollows. In Sec .2,
we discuss ela ed decision p oblems and e iew he li -
e a u e. In Sec .3, we de ine he di e en a ian s o he
packaging machine scheduling p oblem (PMSP) ea ed in
his pape , which di e in he in low o goods and he lex-
ibili y o educe blocking loss by changing he p ocessing
sequence o o de s. Sec ion4con ains a de ailed analysis o
he compu a ional complexi y, and Sec .5p o ides an e i-
cien exac solu ion me hod based on DP. In Sec .6and Sec .
7we elabo a e on ou compu a ional s udy and explo e he
pe o mance–was e adeo . Finally, Sec .8concludes he
pape .
2 Rela ed decisions and li e a u e e iew
A ecen in-dep h su ey pape on sus ainabili y in e-
comme ce packaging (Escu sell e al., 2021) and ou own
( ho ough) li e a u e sea ch e eal ha he e is no p e ious
esea ch on packaging machine scheduling and i s impac on
he was e–pe o mance adeo . Howe e , in o de o posi-
ion ou wo k in ela ion o p e ious esea ch, we ake a
look a ela ed decision asks. Speci ically, we add ess (i) he
choice be ween di e en packaging machine se ups, (ii) he
choice o ca on sizes, and (iii) he packing o goods in o ca -
123
Jou nal o Scheduling (2025) 28:101–120 103
Fig. 2 Al e na i es o blocking machines. Le : Se up machine X7TM o Packsize equi ing se ups o ca on size swi ches (Sou ce: Packsize).
Righ : Pa allel packing machines connec ed by a con eyo sys em (Sou ce: Ro ema)
ons. Finally, we also discuss (i ) o he scheduling p oblems
wi h a simila p oblem s uc u e.
(i) Choice o packaging machine se ups: Based on nume -
ous si e isi s o e-comme ce wa ehouses, a ho ough
e alua ion o packaging machine manu ac u e s’ web-
si es, and discussions wi h manage s and consul an s in
he ield, he au ho s a e awa e o wo al e na i es o
blocking machines. Se up machines (see Fig. 2(le )) a e
equipped wi h an au oma ed ca on swi ching de ice.
They au oma ically load he cu en ly equi ed ca on
size in o he ca on eeding sha o hei single packag-
ing de ice and emo e he old one. The esul ing se ups
cannibalize packaging capaci y and, hus, also c ea e
a was e–pe o mance adeo . Since high-speed se ups
a e manda o y o economical applica ion o au oma ed
packaging, we we e old ha hey a e a common sou ce o
e o s ha equi e a lo o machine main enance. On he
posi i e side, se up machines do no equi e edundan
ha dwa e. To comple ely a oid he was e–pe o mance
adeo , mul iple independen packaging machines, each
dedica ed o a speci ic ca on size, can be used in pa al-
lel. These machines a e accessed ia swi ches om he
main con eyo (see Fig.2( igh )). Independen machines
wi hou ca on size swi ches, howe e , equi e a high
in es men . Blocking machines can be seen as a comp o-
mise be ween hese wo al e na i es. They use dedica ed
packaging de ices wi hou se ups, bu allow euse o pa s
o he ha dwa e. The p ice o his is a blocking loss i
p oduc s and hei demanded ca on sizes a e no p ope ly
sequenced in he in eed. In ou esea ch, we only add ess
blocking machines and lea e a mo e comp ehensi e e al-
ua ion o all di e en se ups o u u e esea ch.
(ii) Choice o ca on sizes: To achie e economies o scale
in pu chasing and o limi handling e o , e aile s can-
no p o ide a pe ec ly i ing ca on o e e y p oduc
(o mul i-piece o de ). The e o e, he numbe o ca on
sizes used is educed o a ew dozen a mos . Typically,
au oma ed packaging demands an e en smalle po olio
o ca on sizes han manual packaging due o he highe
lexibili y o human wo k. Once he numbe o di e -
en ca on sizes o be used is de e mined, choosing he
speci ic sizes ha minimize packaging was e o a gi en
se o o de s an op imiza ion p oblem by i sel . Heu is ics
based on clus e ing me hods (Liu e al., 2013; B inke and
Gündüz, 2016) and gene ic algo i hms (Singh and A d-
jmand, 2020) ha e been in oduced. Fo ou ope a ional
scheduling p oblem, we assume ha he se o a ailable
ca on sizes has al eady been decided in a p e ious (long-
e m) decision ask. Howe e , o ou e alua ion o he
was e–pe o mance adeo , we also de e mine he min-
imum was e ca on sizes o a gi en se o o de s o be
packed (see Sec .7.1). To do so, we apply a s aigh o -
wa d DP app oach, simila o he one p oposed by Lee
e al. (2015), which op imizes he heigh o c a es in he
chemical indus y o accommoda e a gi en se o goods.
(iii) Packing o goods in o ca ons: The ques ion o how o
pack he goods o mul i-piece o de s in o boxes is closely
ela ed o he bin packing p oblem. Su eys on his clas-
sic o he ope a ions esea ch domain a e p o ided, o
example, by Delo me e al. (2016) (exac algo i hms)
and Co man e al. (2013) (heu is ics). Howe e , unlike
bin packing, whe e all bins a e he same size and he
numbe o bins o pack all p oduc s mus be minimized,
e-comme ce e aile s ha e boxes o di e en sizes. Thei
choice is o de e mine he bes box o each o de join ly
wi h he packing ask, minimizing packaging was e and
add-on olume. Fon aine and Minne (2023) p oposes an
e icien b anch-and- epai me hod o his decision. Fo
ou scheduling p oblem, we assume ha he choice o ca -
on size in o which each o de is o be packed is al eady
gi en. Recall ha mos o de s o which au oma ed pack-
aging is applied a e single-piece o de s anyway, whe e
he choice o he bes - i ing ca on size is i ial.
(i ) Rela ed scheduling p oblems: The e is scheduling esea ch
o manu ac u e s o packaging machine y (e.g., (Adle e
123
104 Jou nal o Scheduling (2025) 28:101–120
al., 1993)) and o manu ac u e s o packaging ma e ials
(e.g., (Li e al., 2018)). Howe e , we a e no awa e o any
scien i ic scheduling esea ch ha speci ically add esses
e-comme ce e aile s and hei use o packaging machin-
e y o package hei own goods. Fo se up machines,
minimizing se up loss o a gi en o de se on a single
machine is a special case o he well-known a eling
salesman p oblem (Bu ka d e al., 1998). Fo blocking
machines, whe e he sizes o goods o each packaging
ba ch mus be p ope ly o de ed acco ding o he sub-
sequen packaging de ices, such ha he o al numbe
o packaging ba ches is minimized, his ans o ma ion
is no a ailable. Fu he mo e, unlike adi ional machine
scheduling, whe e he sequence in which o de s a e p o-
cessed is ypically un es ic ed, e-comme ce packaging
machines a e in ol ed in a mul i-s age p ocess (e.g.,
including picking and o de consolida ion (Boysen e al.,
2019)). The esul ing ma e ial low be ween hese s ages
o en elies on a ba chwise anspo (see Sec . 3.1), so
he lexibili y o sequence he in low o goods is lim-
i ed (i.e., only he sequence o ba ches and he o de
sequence pe ba ch can be changed). Ex ensions o a-
di ional machine scheduling o accoun o such limi ed
lexibili y in o de sequencing a e known as g oup ech-
nology. Machine scheduling adap a ions o his ype
o in low ha e been s udied, o example, by Ng e al.
(2005), Janiak e al. (2005), and Li e al. (2011). Howe e ,
due o ou comple ely di e en objec i e unc ion hese
p e ious scheduling p oblems a e no di ec ly applicable.
We conclude ha ou PMSP and i s in luence on he was e–
pe o mance adeo o packaging machines has no been
add essed be o e.
3 P oblem desc ip ion
To ease unde s anding o he a ian s o PMSP ea ed in his
pape , we s a wi h a e bal p oblem cha ac e iza ion, exam-
ples, and he discussion o ou basic assump ions in Sec .3.1.
A e wa d, we p o ide a p ecise ma hema ical p oblem de -
ini ion in Sec .3.2.
3.1 P oblem cha ac e iza ion, examples, and
assump ions
The basic decision ask o he PMSP is he sequence in which
o de s o be p ocessed by he packaging machine a e placed
on o he machine’s in eed con eyo . Each o de demands a
speci ic ca on size o be p ope ly packed, which a e p o-
ided by mul iple subsequen packaging de ices, a anged
back- o-back along he con eyo . Since o de s canno o e -
ake each o he on he con eyo , i may occu ha o de s
block each o he . A blocking occu s whene e a p eceding
o de demands a ca on size p o ided by an an e io (o he
same) packaging de ice, so ha a subsequen o de canno
each i s dedica ed, ye blocked posi ion along he bel . Thus,
one o mul iple packaging slo s in a packaging ba ch (i.e., he
se o o de s concu en ly packed by all pa allel packaging
de ices) emain emp y and a blocking loss occu s. A sui able
sequencing o o de s wi hin he in eed sequence can educe
he blocking loss and hus imp o e he h oughpu pe o -
mance o a blocking machine. The PMSP aims o minimize
he numbe o packaging ba ches ha a e equi ed o p ocess
all o de s.
Since packing is pa o a mul i-s age o de ul illmen p o-
cess, we a e ypically no comple ely ee in he sequence
o de s a e loaded in o he packaging machine’s in eed
sequence. Depending on he ype o inbound s eam, we ace
di e en le els o lexibili y how o manipula e he in eed
sequence. Many wa ehouses apply mul i-bin picking ca s,
as depic ed in Fig.3. Such a picking ca ei he accompanies
a human picke du ing a picke - o-pa s p ocess. Each bin
o a ca is hen associa ed wi h a speci ic cus ome o de ,
so ha he picke can di ec ly place each demanded p od-
uc in o he igh cus ome bin in a so -while-pick p ocess
(De Kos e e al., 2007). Al e na i ely, picking ca s a e also
applied o deli e o de s om he consolida ion s age, whe e
p oduc s ge so ed a e picking in a so -a e -pick p ocess
(Boysen e al., 2019). In bo h cases, o de s (each s o ed in a
sepa a e bin) a i e in picking ca s a he in eed s a ion o he
packaging machine, whe e o de a e o de is placed on o
he in eed con eyo (ei he manually o by an au oma ed
solu ion). Based on his basic p ocess, we di e en ia e he
ollowing ypes o inbound s eams:
•(a) Gi en ca sequence: The sequence in which he pick-
ing ca s a e p ocessed a he in eed s a ion can be gi en.
This is, o ins ance, he esul when p ocessing he ca s
a e he widesp ead i s -come- i s -se ed ule. Hence,
only he sequence in which he o de s o each subsequen
ca a e placed on o he con eyo is he le e o al e he
packaging machine’s in eed sequence. No e ha each ca
mus be comple ely p ocessed be o e he nex one can be
s a ed.
•(b) A bi a y ca sequence: Al e na i ely, nex o he
o de sequence pe ca also he sequence in which a
gi en se o picking ca s, wai ing a he loading s a-
ion, a e p ocessed can be pa o he decision. Once he
ca sequence is de e mined, again, each ca mus be
comple ely p ocessed be o e he nex one can be s a ed.
Ne e heless, his lea es mo e lexibili y o imp o e he
in eed sequence.
•(c) A bi a y in eed sequence: Finally, he la ges lexi-
bili y is a hand i all o de s o he gi en o de se can
123

Jou nal o Scheduling (2025) 28:101–120 105
Fig. 3 Picking ca s in a
wa ehouse (Sou ce: Ligh ning
Pick)
be b ough in o an a bi a y in eed sequence. This case
a ises i he cu en planning un only has o decide on
he o de sequence o a single picking ca o i incom-
ing goods ha e been in e media ely s o ed in a andom
access bu e (e.g., in an ASRS, see Boysen and S ephan,
2016).
No e ha o he wa ehouses do no apply picking ca s o
deli e o de s o packaging machines. I only single-piece
o de s a e picked, hen all demanded p oduc s can be placed
in o he same la ge bin. O de consolida ion is no necessa y,
because i is known ha each p oduc e e s o i s own o de .
These bins wi h single-piece o de s can also a i e a he
in eed s a ion, e.g., deli e ed by o kli s, AGVs, o on a con-
eyo . In ela ion o he ca -based p ocess elabo a ed abo e,
bins co espond o ca s and p oduc s o o de s. Al hough he
physical p ocess is di e en , i can be modeled by he same
h ee ypes o inbound s eams as elabo a ed abo e. No e, u -
he mo e, ha a ixed and gi en in eed sequence o o de s,
which canno be al e ed (e.g., because i di ec ly a i es
om he picking a ea on a con eyo ), lea es no op imiza ion
p oblem and is hus no conside ed in ou p oblem di e -
en ia ion. These al e na i e inbound s eams o e di e en
le els o lexibili y o al e he in eed sequence. Explo ing
he impac o hese lexibili y le els (also including a ixed
in eed sequence) on he was e–pe o mance adeo is pa
o ou compu a ional s udy in Sec .7.
Example 1 The basic inpu da a o he example ins ance
depic ed in Fig.4a a e ou picking ca s, deno ed A, B, C,
and D, each illed wi h wo di e en o de s. Each o de ’s
demanded ca on size is gi en by he whi e numbe wi hin
he espec i e g ay o de squa e. We ha e demanded ca -
on sizes om 1 o 5, so ha ou packaging machine also
has i e back- o-back packaging de ices each se icing one
o he sizes. On he igh side, we see wo di e en in eed
sequences (b) and (c). A gi en ca sequence leads o h ee
packaging ba ches and a blocking loss o se en (see solu ion
(b)). The ela ionship among hese wo pe o mance mea-
su es is as ollows: We ha e h ee ba ches wi h i e packaging
de ices. This leads o 15 slo s, among which eigh a e used
by he gi en o de s, whe eas se en emain unused and cons i-
u e blocking loss. I he ca sequence is pa o he decision,
hen op imal solu ion (c) leads o only wo packaging ba ches
and a blocking loss o 2 ·5−8=2.
Example 2 Now, we conside he same si ua ion as in Exam-
ple 1, whe e, howe e , he manage ial decision has been
made o me ely p o ide wo ca on sizes o size 3 and 5.
Figu e5d indica es he modi ied inpu da a, whe e he ac ual
sizes o he o de s, which a e equal o he sizes o Example
1, a e indica ed by he whi e subsc ip s wi hin he g ay o de
squa es. Thei assignmen o he nex la ge a ailable ca on
size is gi en by he (no mal-sized) whi e numbe s in he o de
squa es. This induces a packaging was e o six, due o pu ing
o de s in o ca ons o la ge size han is ac ually equi ed.
An op imal solu ion o PMSP, which does no imp o e i
he ca sequence can be al e ed, is depic ed in (e). Because
we only ha e wo ca on sizes, we only equi e wo back- o-
back packaging de ices, which educes he in es men cos
o he blocking machine. This, howe e , also implies less
packaging capaci y, so ha we need i e packaging ba ches
(and hus ha e o accep a longe makespan un il all o de s a e
comple ed). Two packaging de ices and i e ba ches di ec ly
imply a blocking loss o 2·5−8=2 slo s ha emain emp y,
which is howe e no imp o emen compa ed o solu ion (c)
o Example 1. We can deduce wo issues o hese wo exam-
ples: (i) Mo e sequencing lexibili y (i.e., i he ca sequence
is pa o he decision and no gi en) as well as (ii) ewe ca -
on sizes can bu need no educe he h oughpu loss.
Be o e, we con inue wi h a p ecise p oblem de ini ion o ou
PMSP a ian s, we discuss he (simpli ying) assump ions
made in his pape o de i e he PMSP in i s e y basic o m:
•We conside only a single packaging machine wi h ixed
o de assignmen s. When mul iple pa allel packaging
machines a e a ailable, he o de assignmen is ano he
ele an decision. Ou solu ion me hods can be applied
o e alua e di e en o de -machine assignmen s, bu we
lea e he e alua ion o such a decomposi ion app oach
o u u e esea ch.
123
106 Jou nal o Scheduling (2025) 28:101–120
Fig. 4 Example 1o PMSP wi h and wi hou gi en ca sequence
Fig. 5 Example 2o PMSP wi h ewe ca on sizes
•Fo con enience, we neglec he po en ial impac o p e-
ious planning uns. Tha is, we neglec he possibili y
ha he las o de s o he p eceding planning un could
po en ially sha e a packing ba ch wi h he i s o de s o
he subsequen planning un. I is easy o elax his sim-
pli ica ion, bu we ha e chosen o s ick wi h he simples
p oblem se up.
•We assume ha a iable-speed con eyo segmen s ensu e
ha o de s a i e in he in eed sequence wi hou gaps. O
cou se, he scheduling o packaging machines is pa ic-
ula ly impo an when packaging is a bo leneck s age.
In his case, gaps deg ade he h oughpu o a bo leneck
esou ce. The e o e, we assume ha a e aile in e es ed
in PMSP has al eady elimina ed his ob ious sou ce o
was ed bo leneck capaci y. I gaps exis , hey could esul
in addi ional blocking loss despi e p ope ly sequenced
o de s app oaching a blocking machine. We lea e he
conside a ion o gaps o u u e esea ch.
•We assume ha each o de equi es a speci ic ca on size.
The addi ional lexibili y p o ided by hie a chical com-
pa ibili y, which allows o de s o be packed in la ge
ca ons han necessa y o educe h oughpu loss a he
cos o addi ional was e, is hus neglec ed and le o
u u e esea ch.
•Finally, we assume ha all inpu da a is known wi h
ce ain y. No e ha o a eliable au oma ed packag-
ing p ocess, de ailed size in o ma ion abou he a i ing
p oduc s mus be a ailable anyway, so his assump ion
does no seem o be a se e e cons ain in ou case.
Gi en his decision con ex , ou PMSP is p ecisely de ined
in he ollowing sec ion.
3.2 P oblem de ini ion
We conside a gi en se Jo o de s, whe e each o de j∈J
has a (ca on) size sj∈{1,...,S}and a ca (numbe ) cj∈
{1,...,C}. He e, Sis he numbe o dis inc sizes and Cis
he numbe o ca s. We assume ha each size in {1,...,S}
and each ca in {1,...,C}is ela ed o a leas one o de
(o he wise, we can educe he numbe o sizes o he numbe
o ca s). No e ha bo h, Sand C, a e implied by Jand,
hus, a e gi en, as well. We deno e he se o o de s wi h ca
numbe cas Jcand will say ha o de jis in ca ci j∈Jc.
A solu ion is a pe mu a ion σo o de s in J. We deno e he
k- h o de in σby σ(k). A solu ion σis easible i and only
i o each pai o ca s cand cwi h c<cei he all o de s
wi h ca numbe cp ecede all o de s wi h ca numbe c
in σo he o he way a ound (i ca sequencing is pa o
he decision). Feasibili y o a solu ion σ, hus, implies ha
o de s appea clus e ed by ca numbe s in σ.
To e alua e a solu ion, we deno e by (σ) =|{k|k=
1,...,|J|−1,sσ(k)≤sσ(k+1)}| he numbe o packaging
ba ches o a solu ion, which equals he numbe o o de s
ollowed immedia ely by an o de o la ge o equal size in
σ). We say ha he e is a b eak be ween posi ions kand k+1,
i sσ(k)≤sσ(k+1), ha is, i a new ba ch s a s in posi ion
k+1. Because each packaging ba ch akes cons an ime o
packing he o de s a he subsequen packaging de ices in
pa allel, we, hen, associa e (σ) wi h he makespan, ha is,
Cmax(σ) =(σ).
The PSMP is o de e mine a solu ion ha minimizes Cmax(σ)
among all easible solu ions.
While he special case o PSMP wi h C=1 co e s he
se ing wi h an a bi a y in eed sequence (see Sec .3.1), he
se ing wi h a gi en in eed sequence is no co e ed by a spe-
cial case o PSMP. The e o e, we de ine a a ian o PSMP,
123
Jou nal o Scheduling (2025) 28:101–120 107
namely PSMP- ixed, o o malize his p oblem. PSMP- ixed
has he same inpu as PSMP, he same solu ion space, and
he same e alua ion o solu ions. A solu ion is conside ed
easible, howe e , i and only i o each pai o ca s cand c
wi h c<call o de s wi h ca numbe cp ecede all o de s
wi h ca numbe cin σ. We, hus, equi e ha he gi en
ca sequence has ca s in inc easing o de o hei numbe s.
The PSMP- ixed is o de e mine a solu ion ha minimizes
Cmax(σ) among all easible solu ions.
4 Analysis o compu a ional complexi y
This sec ion p o ides an in-dep h analysis o compu a ional
complexi y o PSMP and PSMP- ixed. Fo he o me p ob-
lem, we dis inguish cases whe e he gi en numbe o ca s
is ei he C=1, Cis ixed o a gi en cons an , o Cis pa
o he inpu . Fo bo h p oblems, he gi en numbe o ca on
sizes Scan ei he be ixed o is pa o he inpu . Thus, we
conside eigh p oblem a ian s in o al.
We s a wi h PSMP- ixed. We conside he g eedy s yle
algo i hm ske ched in he ollowing. We assign o de s in
Jone by one o posi ions in he pe mu a ion in ascending
o de . Fo each posi ion k, an o de is assignable i i has no
been assigned o a p e ious posi ion ye and i s ca numbe
e e s o he ca cu en ly p ocessed acco ding o he gi en
sequence. Le sbe he size o he o de in posi ion k−1i
k>1, and s=∞o he wise. Le , u he mo e, Jbe he se
o a ailable o de s wi h sizes smalle han s.I J=∅, hen
we choose an o de wi h maximum ca on size among all
a ailable o de s o posi ion k. This implies a b eak be ween
posi ions k−1 and k,i k>1. I J=∅, hen we choose
an o de wi h maximum size among o de s in J o posi ion
k. This implies no b eak be ween posi ions k−1 and k,i
k>1. We e e o his algo i hm as GREEDY and in oduce
he ollowing lemma ela ed o i .
Lemma 1 GREEDY achie es an op imum solu ion o PSMP-
ixed.
P oo Conside an op imum solu ion σ∗and a u he solu-
ion σob ained by GREEDY. Le k<|J|be he i s posi ion
whe e σ∗and σdi e . No e ha i he e is no such posi ion
σis op imum. Ob iously, cσ∗(k)=cσ(k). We dis inguish wo
cases ega ding he sizes o σ∗(k)and σ(k).
•I sσ∗(k)=sσ(k), hen we can simply swi ch σ∗(k)and
σ(k)in σ∗and ob ain an op imum solu ion ha equals σ
up o posi ion k.
•I sσ∗(k)= sσ(k), we modi y σ∗as ollows. Le kbe he
posi ion whe e σ(k)is assigned o acco ding o σ∗, ha
is σ∗(k)=σ(k). No e ha k>k. We mo e σ∗(k) o
posi ion kand delay all o de s in posi ions k o k−1
by one posi ion. We e e o he modi ied solu ion as σ.
No e ha posi ions 1 o k−1 and k+1 o|J|a e no
modi ied. Fu he mo e, be ween posi ions k+2 and k
o de s in σa e in he same ela i e o de as in σ∗. Hence,
he o al numbe o b eaks immedia ely be o e he jobs
in hese posi ions is no highe in σ han in σ∗.Fo he
conside a ion o posi ions kand k+1 we dis inguish wo
cases in he ollowing
–I sσ∗(k)>sσ(k), hen a b eak occu s in σ∗be ween
k−1 and kbu no b eak occu s in σbe ween k−1 and
k, because sσ(k)is maximum among o de s in J.This
holds ue i J=∅and among all a ailable o de s i
J=∅. Hence, he e is no b eak in σbe ween k−1
and k. Howe e , he e is a b eak in σbe ween kand
k+1, because he e is one in σ∗be ween k−1 and
kand sσ(k)<sσ∗(k). So, he o al numbe o b eaks
be ween k−1 and kand be ween kand k+1is1in
bo h, σ∗and σ.
–I sσ∗(k)<sσ(k), hen a b eak occu s in σ∗be ween
k−1 and kand a b eak occu s in σbe ween k−1
and k, because GREEDY a anges a b eak only i
J=∅. Then, he e is a b eak in σbe ween k−1
and kbecause he e is one in σ. The e is no b eak in σ
be ween kand k+1, because sσ(k)>sσ∗(k). Hence,
again he o al numbe o b eaks be ween k−1 and
kand be ween kand k+1 is 1 in bo h, σ∗and σ.
Hence, in bo h cases σis op imum, as well.
Concluding, he e is an op imum solu ion coinciding wi h σ
up o posi ion kand, by applying he a gumen in an i e a i e
manne , σis op imum. 
Now, we a e able o easily e i y ha he in eed sequence in
Fig.4b is indeed op imum o gi en ca sequence A,B,C,D],
because i is he ou pu o GREEDY. Rega ding he compu-
a ional complexi y, he ollowing heo em ollows.
Theo em 1 PSMP wi h a ixed numbe o ca s and PSMP-
ixed can be sol ed in polynomial ime.
P oo We can e alua e each sequence o ca s using GREEDY
acco ding o Lemma 1. I is easy o see ha GREEDY uns
in polynomial ime and he e is a ixed numbe C!o ca
sequences and, hence, his p ocedu e uns in polynomial
ime. 
Recall ha he case C=1 co esponds o an a bi a y in eed
sequence as men ioned in Sec .3.1. Hence, PSMP wi h an
a bi a y in eed sequence can be sol ed in polynomial ime.
Finally, we conside PSMP wi h a ixed numbe o ca on
sizes S. We s a wi h he basic idea o he app oach, which
is o sepa a e he decisions abou b eaks be ween o de s o
he same ca and hose o consecu i e ca s in a solu ion. We
e e o hese ypes as in e nal b eaks and ex e nal b eaks.We
123
108 Jou nal o Scheduling (2025) 28:101–120
do so, by guessing he numbe Cs,so ca s wi h i s o de ’s
size sand las o de ’s size s o each pai (s,s)o sizes in
an op imum solu ion. We e e o a se o such numbe s (one
numbe o each pai (s,s)) as a size p o ile.
Example 1(con .): The size p o iles co esponding o he
solu ion depic ed in Fig.4b and c, espec i ely, a e speci ied
as
⎛
⎜
⎜
⎜
⎜
⎝
00000
10000
00000
00200
01000
⎞
⎟
⎟
⎟
⎟
⎠
and
⎛
⎜
⎜
⎜
⎜
⎝
00000
10001
00000
00200
00000
⎞
⎟
⎟
⎟
⎟
⎠
.
Fo example, we ha e C4,3=2, because in bo h solu ions
he e a e wo ca s wi h i s o de ’s size 4 and las o de ’s size
3. Howe e , while he solu ion in Fig. 4b has a ca wi h i s
o de ’s size 5 and las o de ’s size 2 and, hus, C5,2=1, he
solu ion in Fig.4c has no such ca . Thus, we ha e C5,2=0.
We de e mine (i) he sequence o o de s wi hin each ca ,
such ha he e a e exac ly Cs,sca s wi h i s o de ’s size
sand las o de ’s size sand (ii) he sequence o ca s, hen,
o each size p o ile. No e ha bo h decisions oge he imply
a easible solu ion. No e, u he mo e, ha o aking he
second decision only i s o de ’s size and las o de ’s size
o a ca a e ele an . Hence, we can ake he i s decision
i espec i e o he second.
The p ocedu e, which we dub SIZE_PROFILE, enume -
a es all size p o iles and de e mines (i) he sequence o
o de s wi hin each ca and (ii) he sequence o ca s as
de ailed below. We es ic ou sel es o size p o iles wi h
(s,s)∈S×SCs,s=C.
1. To de e mine he sequence o o de s wi hin he each ca ,
we i s de e mine he minimum numbe o in e nal b eaks
c,s,sbe ween o de s o ca c, i he i s o de ’s size is
sand he las o de s size is s. We can use a s aigh o -
wa d adap ion o GREEDY wi h C=1, whe e we ha e
no eedom o decide he i s and he las posi ion and
he co esponding o de s a e elimina ed om he se o
a ailable o de s. We e ain om gi ing a o mal p oo ,
because i is essen ially he same as he p oo o Lemma 1
(no e ha addi ionally k<|J| o he a ian a hand).
Hence, we can de e mine all c,s,s alues in polynomial
ime.
Ha ing de e mined c,s,s o each ca cand pai o sizes
(s,s), we now conside a bipa i e g aph G=(V,U,E)
whe e nodes in V={1,...,C}co espond o ca s and
nodes in Uco espond o pai s o sizes. Exac ly Cs,s
nodes in Uco espond o pai (s,s). An edge be ween
node c∈Vand a node in Uco esponding o he pai o
sizes (s,s) e lec s ca c o ha e i s o de ’s size sand
las o de ’s size s(and exis s only i ccan ha e i s o de ’s
Table 1 c,s,s o each ca c
and pai o sizes (s,s)in
Example 1
(s,s)ABCD
(1,2)–––1
(2,1)–––0
(3,4)–11–
(4,3)–00–
(2,5)1–––
(5,2)0–––
size sand las o de ’s size s). Choosing his edge in he
ollowing co esponds o choosing he sequence o o de s
o ca cimplying c,s,sin e nal b eaks de e mined by
he adap ion o GREEDY. Consequen ly, an edge be ween
c∈Vand a node in Uco esponding o pai o sizes (s,s)
has weigh c,s,s, and we de e mine a minimum weigh
pe ec ma ching G. Such a ma ching implies a choice o
a sequence o o de s o each ca , which is in line wi h he
gi en size p o ile and has a minimum numbe o in e nal
b eaks be ween o de s o he same ca .
Example 1(con .): Table 1ou lines c,s,s o each ca
cand each pai (s,s)o sizes o he ins ance depic ed
in Fig.4a. A nume ical alue is gi en only i ccan ha e
i s o de ’s size sand las o de ’s size s. Mo eo e , Fig.6
depic s bipa i e g aphs and highligh s minimum weigh
pe ec ma chings o wo size p o iles o his ins ance
ins ance.
2. To de e mine he sequence o ca s, we p opose a DP
app oach, whe e we cons uc he sequence by adding
ca s one by one o an exis ing sequence o ca s. A s a e
(
k,l)speci ies he numbe ks,so ca s scheduled so a
wi h i s o de ’s size sand las o de ’s size s o each
pai (s,s)and he size lo he las o de in he sequence.
We ha e a ansi ion om s a e (
k,l) o s a e (
k,l),i
and only i exac ly one numbe k
s,sis inc eased by one
as compa ed o ks,s, he o he s a e iden ical, and he las
size indica o l=s e lec s ha a ca co esponding
o pai (s,s)has been added o he sequence. T ansi ion
cos s a e in {0,1}and e lec whe he o no an ex e nal
b eak occu s be o e he i s o de o he newly added ca .
No e ha his is implied by land he i s o de ’s size s.
No e, u he mo e, ha he DP app oach does no di e -
en ia e ca s wi h he same pai o i s o de ’s size and las
o de ’s size (as de e mined abo e). Each s a e is e alua ed
by he numbe o ex e nal b eaks be ween ca s so a .
Theo em 2 PSMP can be sol ed in polynomial ime, i he
numbe o ca on sizes is ixed.
P oo SIZE_PROFILE e alua es each size p o ile ollowing
he abo e poin s 1. and 2. The numbe o size p o iles is in
O(CS2)and, hus, polynomial ( o ixed S). Fo each size
123
Jou nal o Scheduling (2025) 28:101–120 115
Fig. 8 Run ime o DP in CPU seconds depending on he numbe o
popula sizes Sand he numbe o jobs pe ca |Jc|
•High impac o he numbe o popula sizes S: The o he
in luencing ac o o he un ime o DP acco ding o ou
heo e ical analysis (see Sec .5.2) is he numbe o pop-
ula sizes S. Recall ha only he (popula ) sizes wi h he
mos o de s pe ca need o be conside ed. Acco ding o
ou compu a ional esul s, hei numbe inc eases, ob i-
ously, i we ha e mo e sizes S(i.e., mo e sizes inc ease
he p obabili y ha mo e o hem a e popula ), he size
dis ibu ion is uni o m (i.e., he iangula dis ibu ion
p oduces a ew highly demanded sizes, so ha jus a ew
become popula ), and ha e small o de capaci y |Jc|pe
ca . Especially, he la e e ec seems o coun e in ui ion,
because mo e o de s (and hus la ge ins ance sizes) seem
o induce sho e un imes.
The la e e ec is u he analyzed in Fig.8. He e, he un-
imes o ins ances wi h C=20 ca s and S=15 ca on sizes
a e depic ed as a unc ion o he jobs pe ca |Jc|and he o al
numbe o popula sizes So e all ca s. No e ha he lowe
bound on Sis C, i each ca has exac ly one popula size.
In Fig.8, we es ic ou sel es o alues o S=25,...,34,
because alues ou o his ange a e a e. Ins ances esul ing
in he same numbe o popula sizes Sa e connec ed. In line
wi h ou heo e ical un ime analysis o DP, we can obse e
ha he un imes emain ( a he ) s able o a cons an num-
be o popula sizes S, i espec i e o he numbe o jobs pe
ca |Jc|. As expec ed, he un imes seem o inc ease almos
linea ly wi h an inc ease o popula sizes S.
The e o e, we can conclude ha he coun e in ui i e esul
o Table 3(i.e., la ge ca capaci ies |Jc|dec ease un ime)
can hus be explained by he ac ha mo e o de s wi h hei
espec i e sizes end o dec ease he amoun o popula ca on
sizes So an ins ance. Mo e andom size selec ions o mo e
o de s on la ge ca s du ing da a gene a ion inc eases he
p obabili y ha only a ew o hem will ecei e he highes
demand and hus be popula . Wi h only a ew size selec ions,
i is mo e likely ha all sizes will ha e low demand and many
o hem will hen be popula .
We conclude ha , consis en wi h ou heo e ical analysis, he
un ime o DP o sol ing PSMP wi h a bi a y ca sequence
is mainly d i en by he numbe o ca s Cand he numbe o
popula sizes S. Howe e , e en o wa ehouses whe e hese
numbe s ake hei maximum alue, he un ime o DP is
small. Thus, DP seems well sui ed o sol e e en la ge PSMP
ins ances o eal-wo ld size o p o en op imali y.
7 Manage ial issues
This sec ion is de o ed o managemen issues. Speci ically,
we in es iga e he ollowing h ee esea ch asks: (i) Once
i has been decided how many di e en ca on sizes should
be a ailable, he speci ic ca on sizes need o be de e mined.
To decide his impo an long- e m issue, we use ano he DP
app oach o minimize he packaging was e o a gi en o de
se . Packaging was e a ises by pu ing p oduc s in o la ge
ca ons han necessa y o sa e on he numbe o employed
ca on sizes. Wi h he DP, we can de e mine he packaging
was e as a unc ion o he numbe o a ailable ca on sizes.
(ii) The comple e was e–pe o mance adeo o blocking
machines is e alua ed in Sec .7.2. He e, we in es iga e o
wha ex en mo e ca on sizes educe packaging was e bu
inc ease he pe o mance loss (and ice e sa). We quan i y
he pe o mance loss by he blocking loss de ined in Sec .3,
which coun s he numbe o emp y packing slo s unused due
o blocked packaging de ices. (iii) Finally, Sec . 7.3 exam-
ines he alue o sequencing lexibili y. The wo ex emes a e
ei he no lexibili y o ull lexibili y. In he o me case, a
ixed sequence o o de s app oaches he packaging machine
wi hou he possibili y o changing i . Full lexibili y (i.e.,
he gi en se o o de s can be pu in o an a bi a y in eed
sequence), on he o he hand, p omises he leas pe o mance
loss, and inbound p ocesses based on picking ca s (wi h
ei he a gi en o a bi a y ca sequence) lie somewhe e in
be ween he wo ex emes. We examine how swi ching o
ei he o hese inbound p ocesses a ec s he h oughpu pe -
o mance o a packaging machine.
7.1 Wha ca on sizes o selec ?
P io o ope a ional scheduling, which is he main ocus o
his pape , long- e m decisions mus be made ega ding he
a ailable ca on sizes. The design o he blocking machine
(and he esul ing in es men cos ) is mainly in luenced by
he numbe o ca on sizes o be p o ided, since each addi-
ional ca on size equi es ano he packaging de ice. We
p o ide decision suppo on he igh numbe o ca on sizes
in Sec .7.2. The e, we explo e he was e–pe o mance ade-
123

116 Jou nal o Scheduling (2025) 28:101–120
Fig. 9 Packaging machine du ing he ca on olding p ocess (Sou ce:
Spa ck Technologies)
o ha is mainly d i en by he numbe o a ailable ca on
sizes.
This sec ion is dedica ed o he choice o speci ic ca -
on sizes, once he decision on he numbe o ca on sizes
o p o ide has al eady been made. I —based, o ins ance,
on his o ical da a— eliable in o ma ion on he sizes o he
o de s o be packed and he equency, in which each o de
size occu s, is a ailable, hen we can op imize he speci ic
ca on sizes, such ha he o al packaging was e ge s mini-
mized. Packaging machines old he ca on o e he goods o
be packed (see Fig.9) and cu ing o he ca on a a sui -
able posi ion ensu es ha in low di ec ion no packaging
was e occu s. Ac oss he low di ec ion, howe e , packag-
ing was e a ises whene e a good is packed in o a ca on o
excessi e wid h. This educes he min-was e p oblem o a
one-dimensional p oblem ha only decides on he wid h o
he ca ons o be p o ided. Once he o ien a ion o he o de s
o be packed is gi en, he esul ing op imiza ion p oblem can
easily be sol ed by a s aigh o wa d DP. Recall ha a sim-
ila DP has al eady been in oduced by Lee e al. (2015) o
op imizing he heigh o c a es in he chemical indus y (see
Sec .2). The DP p oceeds as ollows.
We employ s a es (s,k), which de ine ha ca on size s∈
{1,...,S}is selec ed as he k- h ca on size o be p o ided.
Fo a gi en numbe o o al ca on sizes K o selec , we hus
ha e O(|S|·K)s a es. We conside po en ial ca on sizes
om S o 1. As a esul , we ha e a single s a ing s a e (S,1)
and a single dummy end s a e (0,K+1). A ansi ion om
s a e (s,k) o (s,k), wi h s<sand k=k+1, e lec s ha
all o de sizes ha ing o de size s≥sj>sge assigned o
ca on size s. Fo each o hose o de s, a packaging was e o
s−sjoccu s. As a esul , he cos c(s,s), associa ed wi h
he ansi ion, equal he sum o he esul ing was e.
Finally, we o mula e he Bellman unc ion as (s,k)=
min  (s,k−1)+c(s,s)|s>s. Clea ly, his DP de e -
Fig. 10 Example o he DP sol ing he min-was e policy
Fig. 11 Packaging was e pe numbe o ca on sizes o he eal-wo ld
da ase
mines he minimum packaging was e o he gi en o de sizes
in polynomial ime.
Example 4 Based on he o de da a gi en in Example 1,
Fig.10a p esen s he esul ing inpu da a o he min-was e
policy. The esul ing DP g aph, i K=2 ca on sizes a e o
be p o ided, is gi en in Fig.10b. The bold-ma ked op imal
solu ion leads o wo ca on sizes o size 5 and 3, wi h a o al
was e o 6, which equals he si ua ion in Example 2.
Gi en his op imiza ion app oach, we can quan i y he
packaging was e o ou eal-wo ld da ase (see Sec .6.1)
depending on he numbe o ca on sizes ha a e p o ided.
The esul s a e plo ed in Fig.11. The pe o mance me ic
epo ed he e deno es he minimum was e de e mined by DP
o he espec i e numbe o a ailable ca on sizes in ela ion
o he was e i only a single one-size- i s-all ca on is applied
in %. The un imes o applying he min-was e DP a e nea
ze o o e e y es ed alue o K, while i akes be ween 1.86s
(K=1) and 16.79s (K=10) on a e age o apply he min-
was e DP ollowed by sol ing he esul ing ins ance by DP.
These esul s lead us o ou i s manage ial akeaway.
Finding 1: Mo e ca on sizes can signi ican ly educe he
amoun o packaging was e. Howe e , he posi i e impac
o addi ional ca on sizes quickly diminishes. Adding a sec-
ond ca on size mo e han hal es he amoun o packaging
was e, bu adding an addi ional ca on size when mo e han
a hand ul a e al eady a ailable ha dly con ibu es o any u -
he signi ican educ ion. This is good news o packaging
machine use s: The e is no need o ha e an excessi e num-
123
Jou nal o Scheduling (2025) 28:101–120 117
be o ca on sizes. Wi h jus a hand ul o sizes, mos o he
possible was e educ ion can be achie ed.
7.2 The was e–pe o mance adeo
This sec ion comple es he pic u e on he was e–pe o mance
adeo and also includes he pe o mance impac o he
numbe o a ailable ca on sizes. Recall ha mo e ca on
sizes end o make i ha de o p ope ly so he inbound
o de s acco ding o demanded ca on sizes on he in eed con-
eyo . Thus, mo e ca on sizes no only p omise a educ ion
o packaging was e—as he p e ious sec ion has shown—
bu also end o inc ease he blocking loss, whe e capaci y is
was ed and packaging slo s mus emain emp y. Mo e ca on
sizes come along wi h mo e back- o-back packaging de ices
ha need o be ins alled along he in eed con eyo . Thus,
mo e a ailable ca on sizes induce highe in es men cos o
he blocking machine and an inc ease o packaging capaci y
pe packaging ba ch. To e alua e hese expec ed cohe ences
in ou eal-wo ld da a (i.e., sol ed wi h DP o he op imized
ca on sizes), Fig.12 ela es he numbe o a ailable ca -
on sizes o he pe o mance side o he was e–pe o mance
adeo .
Speci ically, hese esul s ela e o he ollowing h ee basic
pe o mance me ics and how hey a e impac ed by he num-
be o a ailable ca on sizes, namely: (a) he makespan (i.e.,
de ined by he numbe o packaging ba ches ha a e equi ed
o pack all o de s), (b) he o al blocking loss (i.e., de ined
by he o al packaging capaci y, ob ained by mul iplying he
ba ches wi h he numbe o packaging de ices, minus he
numbe o o de s), and (c) he blocking loss pe packag-
ing de ice (i.e., o al blocking loss di ided by he numbe
o packaging de ices). These esul s sugges he ollowing
indings:
(a) Makespan: Mo e ca on sizes o choose om equi es
mo e back- o-back packing de ices, each dedica ed o
a speci ic size. Mo e de ices inc ease he packaging
capaci y, so we can alida e he expec ed e ec ha he
makespan o p ocessing he o de s o he eal-wo ld
da ase dec eases wi h mo e ca on sizes (see Fig.12a).
Howe e , hei posi i e e ec is diminishing, which is an
indica o o he inc easing di icul y o ac ually using he
addi ional packaging capaci y.
(b) To al blocking loss: The inc ease in o al blocking loss he
mo e ca on sizes a e a ailable is isualized in Fig.12b.
Ob iously, mo e and mo e packaging slo s mus emain
emp y because e en ou exac DP algo i hm canno p op-
e ly so he in eed sequence by ca on size.
(c) Blocking loss pe packaging de ice: Each addi ional
packaging de ice added by ano he ca on size causes an
addi ional amoun o blocking loss pe de ice, as shown
in Fig.12c. We can see ha he i s addi ional ca on
sizes in pa icula lead o a signi ican inc ease in his
pe o mance me ic. Howe e , once a ce ain numbe o
ca on sizes a e al eady a ailable, each addi ional packag-
ing de ice ends o add a luc ua ing amoun o blocking
loss pe de ice wi hou a clea end.
By ela ing hese pe o mance me ics o he packaging was e
examined in he p e ious sec ion, he ull was e–pe o mance
adeo can be isualized using Fig.13. He e, we show he
e icien on ie o di e en numbe s o a ailable ca on
sizes in e ms o bo h dimensions (i.e., was e and pe o -
mance). O cou se, he inal choice o an app op ia e numbe
o ca on sizes depends no only on hese wo dimensions,
bu also on he o al cos o owne ship o any addi ional pack-
aging de ice. Because cos in o ma ion a ies widely among
packaging machine manu ac u e s and can change o e ime,
we will no include cos in ou analysis. Ins ead, we end his
sec ion wi h he ollowing ake-home message:
Finding 2: Mo e ca on sizes educe packaging was e, bu
also lead o mo e blocking loss, whe e mo e and mo e pack-
aging slo s mus emain emp y because he back- o-back
packaging de ices canno ecei e o de s p ope ly sequenced
by size. Howe e , bo h e ec s diminish quickly, so in o-
ducing jus a ew (i.e., a hand ul in ou da a) ca on sizes
can p o ide a good comp omise in he was e–pe o mance
adeo . This is good news o e-comme ce e aile s because
i helps keep he necessa y in es men in back- o-back pack-
aging equipmen a a manageable le el.
7.3 The impac o sequencing lexibili y
Packing is jus one s age o he comple e o de ul illmen
p ocess o wa ehouses and dis ibu ion cen e s. Be o e an
o de can be packed in o a sui able ca on, he o de ed
p oduc s mus be e ie ed ei he by a picke - o-pa s o a
pa s- o-picke p ocess (see De Kos e e al. 2007, Lee e
al. 2019). Depending on how hese p e ious s ages a e con-
nec ed o he in eed con eyo o a packaging machine, ou
PSMP aces di e en le els o sequencing lexibili y (see also
Sec .3.1). Basically, he e a e he ollowing al e na i es:
(i) Fixed in eed sequence: No sequencing lexibili y o ou
PSMP is a ailable, i he p eceding s ages a e di ec ly
connec ed by a con eyo ha is ixedly a ached o he
in eed o he packaging machine. In his case, he in eed
sequence equals he p ocessing sequence o he p e i-
ous s ages, which is ypically no op imized acco ding
o he needs o he packaging s age. We emula e his
case by de e mining en andom o de sequences o
each ins ance o ou eal-wo ld da ase , which canno
be al e ed by ou PSMP. Thei esul s a e a e aged.
(ii) Gi en ca sequence: The o de anspo be ween he
p eceding s ages and packaging can also be o ganized in
123
118 Jou nal o Scheduling (2025) 28:101–120
Fig. 12 Pe o mance impac o di e en numbe o a ailable ca on sizes
a ba chwise manne , e.g., ia picking ca s o bins. I he
a i al sequence o hese anspo ba ches is gi en, he
PSMP wi h gi en ca sequence is o be sol ed, and he e
emains he lexibili y o op imize he in eed sequence o
o de s pe ca . The add sequencing lexibili y p omises
less blocking loss compa ed o (i) bu comes a he p ice
o double handling. The o de s mus be e ie ed in a spe-
ci ic sequence om hei ba ches o p ope ly place hem
on he in eed con eyo . This p oduces ex a sea ch e o
and manual handling. We emula e his case by d aw-
ing en andom ca sequences pe ins ance, sol ing each
o he esul ing PSMP- ixed ins ances wi h GREEDY o
op imali y, and a e aging he esul s.
(iii) A bi a y ca sequence: E en mo e lexibili y is o e ed,
i also he sequences in which he ba ches (ca s) a e p o-
cessed is pa o he op imiza ion by sol ing PSMP wi h
a bi a y ca sequence. On op o he double handling,
his also inc eases he demand o shop loo space o
he in e media e s o age o he ba ches. We emula e his
case by sol ing PSMP wi h a bi a y ca sequence o
each eal-wo ld ins ance.
(i ) Pe ec in eed sequence: Finally, blocking loss can be
a oided o he la ges possible ex en , i a andom access
on he comple e o de se is possible a he in eed s a ion
o he packaging machine. This ei he equi es addi ional
ha dwa e (e.g., an au oma ed s o age and e ie al sys em
(ASRS)) o excessi e manual labo o e ie e he o de s
in a bi a y sequence om a ious ba ches. We emula e
his case, by adding all o de s o a single ca and sol ing
he esul ing ins ance wi h GREEDY (see Sec .4).
Since i seems almos impossible o quan i y he cos o hese
al e na i es in an objec i e and gene alizable way, we ocus
Fig. 13 E icien on ie o di e en numbe s o a ailable ca on sizes
and hei impac on packing was e and blocking loss
only on he pe o mance impac o addi ional sequencing
lexibili y. In Fig.14, we ela e he makespan o al e na i es
(i), (ii), and (iii) o ha o al e na i e (i ) and deno e his pe -
o mance me ic ’inc ease in makespan in %’. The un imes
o (i), (ii), (iii) and (i ) a e 0.17s, 0.28s, 17.6s and 0.6s on
a e age. The a e age esul s o ou eal-wo ld da ase show
ha a ixed in eed sequence ha does no accoun o block-
ing loss o he packaging machine was es a lo o packaging
capaci y and leads o an inc ease in makespan o mo e han
200% compa ed o he pe ec in eed sequence. The pe o -
mance loss o a ba ch anspo o he packaging s age is much
smalle , which leads us o he inal manage ial akeaway o
his pape .
123
Jou nal o Scheduling (2025) 28:101–120 119
Fig. 14 Pe o mance impac o sequencing lexibili y
Finding 3: Ba ch anspo o o de s o he packing s age
p omises a good comp omise be ween he highe in es men
cos o mo e sophis ica ed solu ions based on andom o de
access on all o de s and he excessi e blocking loss o gi en
in eed sequences. Especially i he anspo ba ches a e no
oo small, his is s ill ue i he ba ches a e p ocessed on a
i s -come, i s -se ed basis based on a gi en ca sequence.
8 Conclusions
This pape ocuses on he scheduling o e-comme ce pack-
aging machines. Speci ically, we a e he i s o add ess he
peculia i ies o blocking machines, whe e mul iple back- o-
back packaging de ices p o ide access o packaging ca ons
o di e en sizes. Fo a ious ypes o in lows, his pape
de ines he esul ing o de scheduling p oblem such ha
blocking loss (i.e., was ed packaging slo s ha canno be u i-
lized because he o de s o be packed a e no p ope ly o de ed
acco ding o ca on sizes on he in eed con eyo ) is mini-
mized. We p o ide an in-dep h analysis o he compu a ional
complexi y and p o ide exac solu ion me hods ha p o ide
op imal solu ions in a un ime polynomial in he numbe o
o de s. Ou pe o mance analysis shows ha hese algo i hms
can sol e e en la ges ins ances o eal-wo ld size o p o en
op imali y in less han a minu e. In addi ion, we in es iga e
managemen issues and summa ize he esul s in o h ee main
managemen akeaways.
F om a heo e ical pe spec i e, u u e esea ch should add ess
he open case and esol e he complexi y s a us o PSMP wi h
a bi a y ca sequence when he numbe o ca on sizes is
pa o he inpu . F om a p ac ical pe spec i e, u u e esea ch
should sys ema ically compa e blocking machines wi h o he
ypes o packaging machines (e.g., se up machines) in e ms
o he was e–pe o mance adeo . The la e , in pa icula ,
could make a aluable con ibu ion o success ully educing
he en i onmen al bu den o excessi e packaging was e in
e-comme ce.
Funding Open Access unding enabled and o ganized by P ojek
DEAL.
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 indi-
ca 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 ecomm
ons.o g/licenses/by/4.0/.
Re e ences
Adle , L., F aiman, N., Kobacke , E., Pinedo, M., Plo nico , J. C.,
& Wu, T. P. (1993). BPSS: A scheduling suppo sys em o he
packaging indus y. Ope a ions Resea ch, 41(4), 641–648.
Azadeh, K., De Kos e , R., & Roy, D. (2019). Robo ized and au oma ed
wa ehouse sys ems: Re iew and ecen de elopmen s. T anspo a-
ion Science, 53(4), 917–945.
Boysen, N., & de Kos e , R. (2024). 50 yea s o wa ehousing esea ch—
An ope a ions esea ch pe spec i e. Eu opean Jou nal o Ope a-
ional Resea ch.h ps://doi.o g/10.1016/j.ejo .2024.03.026
Boysen, N., De Kos e , R., & Weidinge , F. (2019). Wa ehousing in
he e-comme ce e a: A su ey. Eu opean Jou nal o Ope a ional
Resea ch, 277(2), 396–411.
Boysen, N., & S ephan, K. (2016). A su ey on single c ane schedul-
ing 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 inke , J., & Gündüz, H. I. (2016). Op imiza ion o demand- ela ed
packaging sizes using a p-median app oach. The In e na ional
Jou nal o Ad anced Manu ac u ing Technology, 87, 2259–2268.
Bu ka d, R. E., Deineko, V. G., Van Dal, R., an de Veen, J. A., &
Woeginge , G. J. (1998). Well-sol able special cases o he a el-
ing salesman p oblem: A su ey. SIAM Re iew, 40(3), 496–546.
Co man, E. G., Csi ik, J., Galambos, G., Ma ello, S., & Vigo,
D. (2013). Bin Packing App oxima ion Algo i hms: Su ey and
Classi ica ion. In P. M. Pa dalos, D.-Z. Du, & R. L. G aham
(Eds.), Handbook o Combina o ial Op imiza ion (pp. 455–531).
Sp inge . h ps://doi.o g/10.1007/978-1-4419-7997-1_35
De Kos e , R., Le-Duc, T., & Roodbe gen, K. J. (2007). Design and
con ol o wa ehouse o de picking: A li e a u e e iew. Eu opean
Jou nal o Ope a ional Resea ch, 182(2), 481–501.
Delo me, M., Io i, M., & Ma ello, S. (2016). Bin packing and cu -
ing s ock p oblems: Ma hema ical models and exac algo i hms.
Eu opean Jou nal o Ope a ional Resea ch, 255(1), 1–20.
Escu sell, S., Llo ach-Massana, P., & Ronce o, M. B. (2021). Sus ain-
abili y in e-comme ce packaging: A e iew. Jou nal o Cleane
P oduc ion, 280, 124314.
Fliedne , M., Boysen, N., & Scholl, A. (2011). On he pa in en o y
model sequencing p oblem: Complexi y and beam sea ch heu is-
ic. Jou nal o Scheduling, 14, 17–25.
Fon aine, P., & Minne , S. (2023). A b anch-and- epai me hod o
h ee-dimensional bin selec ion and packing in e-comme ce. Ope -
a ions Resea ch, 71(1), 273–288.
123
120 Jou nal o Scheduling (2025) 28:101–120
Janiak, A., Ko alyo , M. Y., & Po mann, M.-C. (2005). Single machine
g oup scheduling wi h esou ce dependen se up and p ocessing
imes. Eu opean Jou nal o Ope a ional Resea ch, 162(1), 112–
121.
Lee, S. J., Chew, E. P., Lee, L. H., & Thio, J. (2015). A s udy on c a e
sizing p oblems. In e na ional Jou nal o P oduc ion Resea ch,
53(11), 3341–3353.
Li, X., Gao, L., Pan, Q., Wan, L., & Chao, K.-M. (2018). An e ec i e
hyb id gene ic algo i hm and a iable neighbo hood sea ch o
in eg a ed p ocess planning and scheduling in a packaging machine
wo kshop. IEEE T ansac ions on Sys ems, Man, and Cybe ne ics:
Sys ems, 49(10), 1933–1945.
Li, S., Ng, C. T., & Yuan, J. (2011). G oup scheduling and due da e
assignmen on a single machine. In e na ional Jou nal o P oduc-
ion Economics, 130(2), 230–235.
Liu, Y., Wang, Z., & Cheng, G. Q. (2013). Op imiza ion design o size
o oo wea ou e packaging boxes. Ad anced Ma e ials Resea ch,
694, 3516–3521.
Ng, C. T., Cheng, T. E., Janiak, A., & Ko alyo , M. Y. (2005). G oup
scheduling wi h con ollable se up and p ocessing imes: Min-
imizing o al weigh ed comple ion ime. Annals o Ope a ions
Resea ch, 133(1–4), 163–174.
Olis , (2019) . B azilian e-comme ce public da ase by olis . h ps://
www.kaggle.com/da ase s/olis b /b azilian-ecomme ce (las
access: Janua y 2024).
P ose , S., B andne , M., He man, K., S einbach, E., B and ne , P., &
Schaue , O. (2021). Sus ainable anspo packaging: E alua ion
and easibili y o di e en use cases. LOGI-Scien i ic Jou nal on
T anspo and Logis ics, 12(1), 159–170.
Singh, M., & A djmand, E. (2020). Ca on se op imiza ion in e-
comme ce wa ehouses: A case s udy. Jou nal o Business Logis-
ics, 41(3), 222–235.
Publishe ’s No e Sp inge Na u e emains neu al wi h ega d o ju is-
dic ional claims in published maps and ins i u ional a ilia ions.
123