Sedding, Helmu A.
A icle — Published Ve sion
Mixed-model mo ing assembly line ma e ial placemen
op imiza ion o a sho e ime-dependen wo ke walking
ime
Jou nal o Scheduling
P o ided in Coope a ion wi h:
Sp inge Na u e
Sugges ed Ci a ion: Sedding, Helmu A. (2023) : Mixed-model mo ing assembly line ma e ial
placemen op imiza ion o a sho e ime-dependen wo ke walking ime, Jou nal o Scheduling,
ISSN 1099-1425, Sp inge US, New Yo k, NY, Vol. 27, Iss. 3, pp. 257-275,
h ps://doi.o g/10.1007/s10951-023-00787-5
This Ve sion is a ailable a :
h ps://hdl.handle.ne /10419/323372
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 (2024) 27:257–275
h ps://doi.o g/10.1007/s10951-023-00787-5
Mixed-model mo ing assembly line ma e ial placemen op imiza ion
o a sho e ime-dependen wo ke walking ime
Helmu A. Sedding1,2
Accep ed: 25 May 2023 / Published online: 2 Sep embe 2023
© The Au ho (s) 2023
Abs ac
Ca mass p oduc ion commonly in ol es a mo ing assembly line ha mixes se e al ca models. This equi es plen y o
ma e ial supplies a he line side, bu a ailable space is sca ce. Thus, ma e ial is placed apa om ideal posi ions. Then,
picking i up in ol es walking along he line. This ime is non-p oduc i e and can encompass 10–15% o o al p oduc ion
ime. Thus, i is impo an o es ima e and minimize i du ing p oduc ion planning. Howe e , he calcula ions a e di icul
because he con eyo con inuously mo es. The e o e, mos li e a u e bounds walking ime by a cons an , bu his disca ds
aluable po en ial. To be e app oxima e i , we use a ime-dependen V-shaped unc ion. A compa ison indica es ha o
a majo i y o ins ances, cons an walking ime es ima es o 95% con idence a e a leas 51% highe . Then, we in oduce a
model o op imize ma e ial posi ions such ha he model-mix walking ime is minimized. This poses an NP-ha d sequencing
p oblem wi h a ecu si e and nonlinea objec i e unc ion. Ou key disco e y is a lowe bound on he objec i e o pa ial
solu ions, es ablished by a Lag angian elaxa ion ha can be sol ed in quad a ic ime. Resul ing b anch and bound based
algo i hms allow o quickly and eliably op imize up o he la ges eal-wo ld sized ins ances.
Keywo ds Scheduling ·Mo ing assembly line ·Walking ime ·Ma e ial placemen ·Mixed-model p oduc ion
1 In oduc ion
Mass-p oduc ion o ca s was pa icula ly made possible by
he mo ing assembly line. I con inuously anspo s he
wo k pieces om wo ke o wo ke . P oduc i i y is high-
es i he assembly ope a ions a e di ided equally be ween
all wo ke s. This is an NP-ha d bin packing ype op imiza-
ion p oblem (Ál a ez-Mi anda and Pe ei a, 2019) ha is
called assembly line balancing (Sal eson, 1955); su eys a e
ound in Ba aïa and Dolgui (2013,2022), Becke and Scholl
(2006), Boysen e al. (2022). Solu ions can imp o e wi h
sho e ime bu e s gi en mo e accu a e ime es ima es, e.g.,
o a wo ke ’s wo kload when assigning ope a ions.
A signi ican ime sink can be a wo ke ’s walking ime
o e ch pa s om he line side, amoun ing o 10–15%
o o al p oduc ion ime a a majo Ge man ca manu ac-
BHelmu A. Sedding
helmu [email protected]
1Ins i u e o Theo e ical Compu e Science, Ulm Uni e si y,
Ulm, Ge many
2Ins i u e o Da a Analysis and P ocess Design, ZHAW,
Win e hu , Swi ze land
u e (Scholl e al., 2013). This ime can ha dly be es ima ed
wi h a cons an : i is highly a iable because he dis ance
is ime-dependen . A me hod o es ima e i is in oduced in
Sedding (2020a) in p oduc ion o a single model. Walking
ime is hen minimized by placing ma e ial supplies a op i-
mal posi ions along he line side ( he ope a ion sequence is
ixed). This op imized and mo e exac walking ime es ima e
allows o be e gage he wo ke ’s wo kload du ing assembly
line balancing, po en ially inc easing o e all line u iliza ion.
To employ he es ima e in in e ac i e planning so wa e, as
compu e imes a e essen ial, which a e p o ided by heu is ics
in Sedding (2020a) wi h a median un ime o 0.002s. In his
pape , we adap his app oach o a model-mix p oduc ion,
which is common in ca assembly (S e na z, 2014).
Anassemblywo ke e chesneededma e ial o anassem-
bly ope a ion by walking o he espec i e ma e ial box. In
he ypical mo ing ca assembly line, boxes a e loca ed a he
lineside,alongwhich hewo kpiecemo es. Ideally,eachbox
is loca ed close o he wo kpiece’s posi ion a access ime, as
his minimizes walking ime. Howe e , i he line side space
is sca ce (Bau is a and Pe ei a, 2007; Bukchin and Melle ,
2005; Boysen e al., 2015), i is usually necessa y o place a
box apa om i s ideal loca ion along he line.
123
258 Jou nal o Scheduling (2024) 27:257–275
The mo ing wo kpiece’s dis ance o a box and he esul -
ing wo-way walking ime can be modeled by a con ex
unc ion o ime (Sedding, 2020a). Howe e , mos models
o assembly line planning in he li e a u e a e es ic ed o
cons an p ocessing ime es ima es, jus like in he classic
assemblylinebalancingp oblem (Sal eson,1955).Al hough
sequence-dependen nonp oduc i e p ocessing imes a e
includedinAnd ése al.(2008),Scholle al.(2013),Esmaeil-
beigi e al. (2016), hey canno be applied o p ecisely plan
walking imes a assembly lines wi h a mo ing wo kpiece:
O e ly la ge sa e y ac o s a e needed o uppe bound he
walking ime wi h a cons an . This gi es away po en ial o
inc ease he u iliza ion o an assembly line. In his s udy, we
es he po en ial o ime-dependen walking ime es ima es.
When assigning ope a ions o a wo ke , a ealis ic walk-
ing ime es ima e needs o ake possible local op imiza ions
in o accoun . A minimiza ion o a wo ke ’s walking ime can
be app oached in wo majo ways o a gi en se o assem-
bly ope a ions. On he one hand, i is possible o op imize
he ope a ion sequence (Jaehn and Sedding, 2016; Sedding,
2020b). On he o he , he posi ioning o he espec i e ma e-
ial boxes can be adjus ed (Klamp l e al., 2006; Finnsgå d
e al., 2011; Sedding, 2017,2020a). This equi es o ix
he ope a ion sequence o de e mine a walking ime op i-
mized box placemen . Finnsgå d e al. (2011) desc ibe a
manual op imiza ion and epo a walking dis ance educ ion
by 52%. Schmid e al. (2021) op imize he placemen wi h
a mixed-in ege p og amming app oach ha conside s a i-
able walking cos s du ing ma e ial placemen , bu igno es he
wo kpiece’s con inued mo emen while he wo ke walks.
Klamp l e al. (2006) ake his mo emen in o accoun , using
Euclidean dis ances o calcula e ime-dependen walking
imes. In h ee app oaches, hey conside placemen o boxes
along he line. Fi s wi h o e laps, hen wi hou o e laps, and
inallywi hs ackinga opeacho he .Nonlinea p og amming
isused o heu is ically ind placemen s. Howe e , hey eco d
a he long compu e imes al eady o a small ins ance o
i e ma e ial boxes. A one-dimensional walking ime model
yields a signi ican ly quicke op imiza ion in Sedding (2017,
2020a,2020c) o he case o single model placemen .
In his pape , we adap he ma e ial placemen op i-
miza ion in Sedding (2020a) o he mixed-model mo ing
assembly line. A mixed-model assembly sha es he same
line o se e al p oduc models (Thomopoulos, 1967). Then,
he p oduc ion can be e adap o a ying demands o each
model. This p oduc ion me hod is s anda d in ca assem-
bly (S e na z, 2014). Line side space can be e en mo e sca ce
i u he ma e ial is equi ed o each model (Boysen e al.,
2015). In he mixed-model se ing, he objec i e is o min-
imize o al p ocessing ime weigh ed by model sha e. This
allows o longe p ocessing imes on some p oduc mod-
els, especially a e ones, p o ided his can be compensa ed
o on o he p oduc models. Allowance is p o ided by he
wo ke loa ing up- o downs eam he line. Howe e , an
o e load o e he cou se o se e al cycles canno be com-
pensa ed anymo e as inc easing walking imes exace ba e
he o e load. Such si ua ions mus be p e en ed du ing plan-
ning, in pa icula o he p oduc ion sequence, c . Boysen
e al. (2009c) o a su ey.
Ou pape ’s con ibu ion lies in placing ma e ial boxes a
he line side o a wo ke ’s assembly ope a ions o e a mix
o p oduc models such ha he model-mix weigh ed ime-
dependen walking imes o ga he ma e ial a e minimized:
– Fi s , we display all assump ions and in oduce an op i-
miza ion model in Sec . 2. In compa ison o Sedding
(2020a,2020c), i pe mi s mul iple models and an o -
se o he placemen a ea (o indi ec ly he s a ime).
– We obse e ha he p oblem en ails a ecu si e, non-
linea objec i e unc ion, which impedes e alua ion o
pa ial solu ions and ende s inc emen al solu ion p oce-
du es di icul . We p o ide a p oo o s ong NP-ha dness
o any numbe o p oduc models (Sec . 3).
– A mixed-in ege p og am is de i ed om he single-
model case in Sedding (2020a,2020c).
– The main echnical con ibu ion o ou pape is a
Lag angian elaxa ion o he ma hema ical p og am, o
which we ind a pa i ion in o wo independen subp ob-
lems, each o which is sol ed in quad a ic ime. This
esul s in a as lowe bound o pa ial solu ions (Sec . 5).
This lowe bound is he co ne s one o a b anch and
bound algo i hm ha inc emen ally places he boxes. A
unca ed b anch and bound sea ch p o ides a as heu is-
ic (Sec . 6).
– Finally, a nume ical expe imen shows he e ec i eness
o he app oaches (Sec . 7). The o al un ime o he bes
heu is ic is negligibly small: o he la ges ins ances, he
median un ime is 0.071 s. Such a un ime is sui able o a
use in in e ac i e planning so wa e. Po en ial sa ings a e
high in compa ison o cons an walking ime es ima es as
well as in ui i e placemen s (Sec . 7.5).
– Ou model is he i s in he li e a u e o e icien ly con-
side and minimize a ime-dependen model o walking
imes o ma e ial placemen a he mixed-model mo ing
assembly line. As his p oduc ion mode is s anda d o
ca p oduc ion, ou app oach has a a - eaching applica-
bili y.
P elimina y e sions o his pape a e a ailable in his special
issue’s wo kshop p oceedings (Sedding, 2021) and in he
au ho ’s disse a ion (Sedding, 2020c, Chap e 6).
2 Modeling
This sec ion p esen s he s udied op imiza ion p oblem Pm
o placing boxes o a model-mix o mp oduc s. A e a
123
Jou nal o Scheduling (2024) 27:257–275 259
o mal de ini ion o all pa ame e s in a Pmins ance, i s
p e equisi es a e in oduced. The de ini ion o Pm ollows.
No e ha Pmbuilds upon he op imiza ion p oblem in
Sedding(2020a,2020c) o asinglep oduc assemblym=1.
While he single-model case is ex ended o a mixed-model
p oduc ion, all o he assump ions emain unchanged. A lis
o assump ions made o Pmis ga he ed in Table 1.
De ini ion 1 An ins ance o Pmis gi en by
−a∈Q∩[0,1]as walking ime slope (box ahead),
−b∈Q∩[0,∞)as walking ime slope (box behind),
−Ias se o p oduc models,
−m=|I|as numbe o p oduc models,
− i∈Q∩[0,1]as p oduc ion a e o model i∈I
s. . i∈I i=1,
−J={(i,j)|i∈I,as se o all jobs,
j∈{1,...,ni}}
−ni∈Nas numbe o jobs o model i∈I,
which emain in he ixed
sequence (i,1), (i,2),...,(i,ni),
−n=|J|=i∈Inias o al numbe o jobs,
−i,j∈Q∩[0,∞)as assembly ime o job (i,j)∈J,
−wi,j∈Nas wid h o he box o job (i,j)∈J,
−V∈Qas s a o he placemen in e al,
−W=V+(i,j)∈Jwi,jas he placemen in e al end.
Be o e he op imiza ion p oblem Pmcan be de ined, we
speci y how boxes can be placed, see how walking ime o
e ching pa o a boxes can be modeled, and de ine how o
calcula e he makespan (comple ion ime) o a p oduc ion
cycle encompassing walking and assembly ime. The esul
is isualized o an example ins ance in Fig.1.
2.1 Box placemen
Necessa y ma e ial o an assembly ope a ion is p o ided in a
dedica ed box (i,j)∈J. I akes up a ce ain box wid h wi,j
along he line side, exp essed as a sha e o he a ailable wid h
(in he dimension along he line). We may assume wi,j∈N
by scaling he coo dina e sys em acco dingly.
Le se Jdeno e he se o boxes o he he wo ke .
The boxes a e placed side-by-side wi hou o e laps. Gi en
a sca ce line side space, we assume he e a e no gaps
be ween boxes. Then, he boxes a e placed in a con igu-
ous sec ion a he line side: he space be ween Vand W=
V+(i,j)∈Jwi,j.
Then, a box placemen
{πi,j}(i,j)∈J(1)
Table 1 The model assump ions equal he s udy o he single-model case in Sedding (2020a,2020c) excep o A3 swi ching o a model-mix and
adding A16
A1 Single s a ion Focus on one assembly s a ion and wo k piece
A2 Single wo ke Focus on one wo ke . In e e ence is uled ou
A3 Mul iple p oduc a ian s We conside a model-mix o se e al p oduc a ian s, each wi h a di e en p oduc ion a e and i s own se o
assembly ope a ions and con aine s. While a p oduc ion sequence o he p oduc a ian s is no ye de e mined, i is assumed ha he
sequence ul ills he p oduc ion a es on a e age
A4 Fixed ope a ion sequence A wo ke has an immu able sequence o ope a ions albei i may be changed in p ac ice
A5 Single cycle A p oduc ion cycle begins when he wo kpiece en e s he wo ke ’s zone, and i ends when all ope a ions ha e been inished
on his wo kpiece. I ha akes sho e o longe han he a e age cycle ime, he wo ke can s a he nex cycle ea ly o la e. This may
cause a di e en s a ing poin , highly depending on he p oduc ion sequence. Howe e , he sequence is no a ailable du ing ma e ial
placemen . Thus, we assume an a e age cycle ime and dis ega d loa ing
A6 Single wo k poin The wo k poin is a one loca ion a he wo kpiece. We assume ha o he wo k poin s a e assigned o di e en wo ke s
on assembly line balancing (Becke and Scholl, 2009)
A7 One box pe ope a ion One single box agg ega es all ma e ial con aine s o an ope a ion, e.g., as a s ack o a shel
A8 One-dimensional box placemen Boxes a e placed along a line pa allel o he assembly line. Hence, he box wid h along his dimension is
he decisi e size o measu e a box’s occupied in e al a he line side
A9 No space be ween boxes The e a e no gaps be ween adjacen boxes in ou model. This assump ion is ealis ic as space a he line side is
ypically sca ce (S e na z, 2015). No e ha mo e elabo a e logis ics ope a ions like ma e ial sequencing o ki ing may educe equi ed
space a he line side (Boysen e al., 2015; Schmid and Limè e, 2019)
A10 S a iona y box posi ions Box posi ions a e ixed du ing p oduc ion and op imized be o ehand
A11 Uni o m walking eloci y Walking eloci y is cons an and he same o all ope a ions
A12 One-dimensional walking Only walking in pa allel o he assembly line is coun ed: Boxes a e loca ed in close angency he con eyo o
educe he o hogonal ma gin o a g ipping dis ance
A13 One walk pe ope a ion The wo ke e ches necessa y pa s all and only be o e he s a o an assembly ope a ion om a single box as in
A7, An ope a ion can agg ega e se e al sub-ope a ions, o all o which ma e ial is ga he ed in one single un
A14 No pick ime Pick imes a e neglec ed. Finnsgå d e al. (2011) epo s ha pick imes encompass jus 6% o nonp oduc i e ime
A15 Picking a ups eam side We simplis ically assume picking a he ups eam (le ) edge, albei se e al pick poin s may exis o a box
A16 Placemen a ea o se The box placemen in e al s a can be gi en wi h a shi o he s a ion s a along he line
123
260 Jou nal o Scheduling (2024) 27:257–275
Fig. 1 On planning he line side placemen , boxes a e posi ioned in a
sequence a he line side in [V,W), displayed in he igu e’s op ow.
Shown below a e assembly ope a ions (jobs) in ixed sequences o
h ee p oduc models. The ho izon al axis ep esen s he ime; i shows
assembly ope a ions pe o med by he wo ke while a wo kpiece mo es
along he line o e ime . No e ha he ime scale equals he space
scale. A he s a o a p oduc ion cycle, he wo ke is a ime and spa-
ial posi ion 0. Blue a ow lines indica e, exempla y o model 3, he
wo ke ’s longi udinal mo emen along he line du ing one p oduc ion
cycle, al e na ing be ween e ching ma e ial (walking he cu ed line)
and assembling, du ing bo h o which he wo kpiece mo es. Job (3,1)
s a s a ime 0; wi h walking ime 3,1(0)(indica ed by he s iped a ea,
o& om he box a π3,1) and assembly ime 3,1, he job comple es a
C3,1(0). Job comple ion imes, calcula ed ecu si ely, a e labeled in
blue colo . A p oduc ion cycle o model 3 is comple ed a ime (and
posi ion) C3,max. The objec i e is o minimize he a e age comple ion
ime o e all models by placing he boxes such ha walking imes a e
minimal.
s a es, o eachbox(i,j)∈J,a a ional- aluedposi ion V≤
πi,j≤W−wi,j o place i on in e al [πi,j,π
i,j+wi,j)a
he line side such ha (i,j)∈J[πi,j,π
i,j+wi,j)=[V,W).
No e ha a aining a box placemen is equi alen o inding
a sequence o he boxes along he line side.
2.2 Walking ime
The walking ime calcula ion in Sedding (2020a) is b ie ly
desc ibed in he ollowing. In his model, he wo ke only
walks along he mo ing assembly line; mo emen o hogo-
nal o he line can be igno ed. Th ee walking s a egies a e
co e ed: Always walking on he ixed loo , a op he con-
eyo ’s mo ing loo , o whiche e is be e in he cu en
mo emen di ec ion.
Fo walking up o a box (i,j)∈J, he wo ke lea es
he wo kpiece a a ce ain ime , a i es a he box’s posi-
ion πi,j, and hen e u ns o he wo kpiece. All he while, he
wo kpiece con inues o mo e. This gi es se e al mo emen
equa ions, which a e sol ed wi h a closed o mula. Then, he
walking ime is ep esen ed by he piecewise-linea unc ion
i,j( )=max{−a·( −πi,j), b·( −πi,j)}(2)
whe e πi,jis he box posi ion encoded in ime uni s, and
0≤a≤1 and b≥0 a e wo slopes ha depend on he
wo ke ’s eloci y and walking s a egy. See also Fig.2.
I he cu en ime equals he box posi ion (case =πi,j),
hen he walking ime is minimum, which occu s i he wo k-
piece jus passes by he box posi ion. O he wise, he walking
ime inc eases linea ly. I he wo kpiece has no ye passed
he box posi ion (case <π
i,j), hen he walking ime co -
esponds o −a·( −πi,j), o he wise i is b·( −πi,j).
The wo slopes ela e he wo kpiece’s eloci y con eyo o
he wo ke ’s walking eloci y wo ke >
con eyo . Fo exam-
ple, i he wo ke walks on a non-mo ing loo beside he
wo kpiece, hen a=2/( +1)and b=2/( −1)whe e
= wo ke / con eyo . The same slope alues a e a ained
i he wo ke walks on loo pla es ha mo e oge he wi h
he wo kpiece. I a wo ke can always choose he bes o
bo h op ions, hen he slopes a e a=(2 +1)/(1+ )2and
b=(2 +1)/ 2. No e ha his walking s a egy yields, i
=13.6asinKlamp le al.(2006), awalking ime educ ion
by 3.5% i <π
i,j, else 4.1%, see Sedding (2020a).
2.3 Makespan calcula ion
Be o e an assembly ope a ion can be p ocessed, a walk-
ing ime occu s o i s dis inc box (i,j)∈J. Toge he ,
hese wo cons i u e a job, which is also deno ed by (i,j).
Then, job (i,j)consis s o wo pa s: he nonp oduc i e
walking ime unc ion i,jin (2), and a e ha , a p oduc-
i e assembly ime i,j≥0 ha is a cons an nonnega i e
a ional numbe . Toge he , hey o m he job’s p ocessing
ime pi,j( )= i,j( )+i,j. S a ing a ime , he job com-
ple es a Ci,j( )= +pi,j( ). Subs i u ing all componen s,
123

Jou nal o Scheduling (2024) 27:257–275 261
Fig. 2 Visualiza ion o he walking ime unc ion i,jo job (i,j)∈J
in (2) as a unc ion o s a ime
he job’s comple ion ime is exp essed by
Ci,j( )= +i,j+max{−a·( −πi,j), b·( −πi,j)}.
(3)
Each p oduc model i∈I equi es p ocessing o a ce ain
numbe nio jobs in a ixed sequence deno ed by
(i,1), (i,2),...,(i,ni)
whe e niis he numbe o jobs in model i. Then, he las
comple ion ime Cmax
iin a model iis he composi ion o job
comple ion imes (3), s a ing he i s job (i,1)a ime 0:
Cmax
i=Ci,ni(··· Ci,2(Ci,1(0))) ···). (4)
No e ha a s a o he i s job a min = 0 is a ained by
shi ing he box placemen in e al by − min.
Rema k 1 The job sequence is ixed he e. As men ioned in
he in oduc ion, i is also possible o op imize walking ime
by pe mu ing he job sequence (Sedding, 2020b,2020c).
Thisbelongs o he ield o ime-dependen scheduling (Gaw-
iejnowicz, 2020b,2020a). Rela ed piecewise-linea con ex
Ci,j unc ionsa e desc ibed in Fa ahaniand Hosseini (2013),
Kawase e al. (2018), Konono (1998), while a ecen su ey
is ound in Sedding (2020b).
2.4 Op imiza ion p oblem
Minimizing he o e all walking ime in he mixed-model
se ing is equal o minimizing he o al weigh ed makespan
(comple ion ime) o e all p oduc models (Klamp l e al.,
2006). This can be a ained by a sum o each model i’s las
comple ion ime Cmax
iweigh ed by p oduc ion sha e i.This
objec i e is minimized in he s udied op imiza ion p oblem.
De ini ion 2 (P oblem Pm)Gi enaPmins ance (see De -
ini ion 1), minimize he weigh ed a e age makespan
φ=
i∈I
iCmax
i
by de e mining a box placemen {πi,j}(i,j)∈J, which places
he boxes, each ep esen ed by box wid h wi,j, in a sequence
in [V,W),see(1). This yields, o model i∈I, makespan
Cmax
i=(Ci,ni◦···◦Ci,2◦Ci,1)(0),
which composes he comple ion imes o model i’s job
sequence acco ding o (4). By (3), he comple ion ime Ci,j
o job (i,j)∈Jas a unc ion o job s a ime is gi en by
Ci,j( )= +i,j+max{−a·( −πi,j), b·( −πi,j)}.
In he single-model case, he makespan canno be la ge
han he cycle ime. E e y cycle, a new wo kpiece a i es,
hence a la ge makespan would equi e a line s oppage (o
a wo k o e load si ua ion). He ein lies a key ad an age o
model-mix p oduc ion: I he weigh ed a e age makespan φ
is no abo e he cycle ime, hen he e is no wo k o e load
(on a e age). Models wi h a highe makespan le he wo ke
loa downs eam, o he s ups eam.
Hence, some models may be allowed a makespan longe
han he cycle ime. Howe e , no e ha such an o e load
si ua ion would a ec he nex p oduc ion cycle’s s a ime.
Then,walking imesa ea ec ed.I i occu s epea edly,how-
e e , walking imes can g ow quickly as he wo ke is d i en
away om he boxes. I he wo ke has loa ed downs eam
behind he co esponding boxes, hen any delay inc eases he
comple ion ime by a ac o o (1+b)n o n emaining jobs,
which ollows om Sedding (2020b, Co olla y 2). In excess,
he wo ke needs assis ance and/o he line needs o s op.
Such o e load si ua ions mus p e en ed in planning o he
p oduc ion sequence.
Al hough he makespan should equal he cycle ime, i can
well be di e en o he placemen in e al’s end W. Mo e-
o e , he model allows a nonze o placemen in e al s a V.
In bo h cases, he placemen a ea is incong uen o he assem-
bly s a ion, co e ing only a pa , o ex ending ou o i . This
models ha he placemen a ea is o se o he assembly s a-
ion. This is equi ed, e.g., when subdi iding he line-side
space in o di e en sized egions, which can bene i he o e -
all assembly line balance. A nonze o s a ime o he i s job
can depic loa ing o he wo ke up- o downs eam he line.
This is ep esen ed in ou model by shi ing he placemen
in e al back by he same amoun .
3 Compu a ional complexi y
The main di icul y o op imizing a box placemen is caused
by he ecu si e and nonlinea na u e o he objec i e. Fo
example, i he i s job’s box is mo ed, hen i s walking
ime changes. As a consequence, succeeding jobs s a a a
di e en poin in ime. This ime migh be ea lie o la e
123
262 Jou nal o Scheduling (2024) 27:257–275
han be o e. As each walking ime unc ion is nonlinea , he
objec i e alue changes nonlinea ly. Mo eo e , he espec-
i e ideal box loca ion o succeeding jobs changes. Then, he
placemen o hese boxes needs u he eop imiza ion.
To highligh hecomplexi yo Pm, wep o e ha i isNP-
ha d in he s ong sense o an a bi a y numbe o p oduc
models m≥1. Fo his, we pe o m a educ ion om 3-
Pa i ion as de ined in Ga ey and Johnson (1978), which is
NP-comple e in he s ong sense (Ga ey and Johnson, 1975).
De ini ion 3 (3-Pa i ion) Gi en a bound B∈Nand 3zele-
men s in mul ise X={x1,...,x3z}⊂Nwi h B/4<
x<B/2 o x∈X, and x∈Xx=zB. The ques ion is:
does he e exis a pa i ion o Xin o zdisjoin mul ise s Ai,
i=1,...,zwi h x∈Aix=B?
Theo em 1 PmisNP-ha d in he s ong sense o a bi a y
m≥1.
P oo Fo m=2, we pe o m a educ ion om 3-Pa i ion
as o De ini ion 3. This equi es a decision e sion o Pm
ha speci ies a h eshold alue Φand asks i a solu ion exis s
wi h objec i e alue φ≤Φ.
A co esponding ins ance is cons uc ed as ollows. Fi s ,
we eely choose any allowed nonze o slope 0 <a≤1, b>
0 alue. Fo he wo models I={1,2}, we se p oduc ion
sha e 1=0 and 2=1. Hence, model 1 incu s no walking
ime in he objec i e unc ion. Howe e , i occupies space
a he line side o i s n1=3zjobs o which we le w1,j=
xj,j=1,...,3z, and choose an a bi a y 1,j alue. The
second model has n2=z+1 jobs. Fo each j=1,...,z+1,
we se w2,j=1 and 2,j=B+1. Finally, we se h eshold
alue
Φ=
j=1,...,z+1
l2,j=(B+1)(
z+1).
This ins ance’s objec i e alue is, gi en he unila e al p o-
duc ion sha es, φ=C2,z+1.AsC2,z+1≤Φ, he e is φ≤
Φ⇐⇒ φ=Φ. Le us assume ha φ=Φ. This equi es
in he second p oduc model o each j=1,...,z+1 ha
p2,j=2,j. This is he case i and only i he co espond-
ing box is p ecisely posi ioned a (B+1)·j. These boxes
lea e gaps o wid h B. Each gap is closed by he i s p oduc
model’s boxes i and only i he 3-Pa i ion ins ance can be
sol ed. Hence, Pmis NP-ha d o m=2.
We gene alize his educ ion o m>2 by ex ending he
ins ance wi h m−2 models I. Fo each i∈I,le i=
0. Then, he las comple ion imes o models Iyield no
impac on he objec i e unc ion. Mo eo e , we in oduce an
a bi a y numbe o jobs o each added model i∈I, each
wi h he same box wid h B+1 and an a bi a y assembly
ime. Because hese boxes a e oo wide o be placed be ween
wo adjacen boxes o he second p oduc model o φ≤Φ,
hey mus be placed a e he las one. Hence, hey asse
no e ec on he box placemen o he i s and he second
p oduc model.
Fo m=1, s ong NP-ha dness is shown in Sedding
(2020a). Concluding, a pseudopolynomial educ ion o 3-
Pa i ion o Pmexis s o m≥1. 
4 Ma hema ical p og amming
We desc ibe Pmsolu ions using ma hema ical p og am-
ming, adap ing he special case m=1 in Sedding (2020a,
2020c) om≥1. This includes a makespan calcula ion o
each p oduc model and changes he objec i e unc ion o a
sum o makespans weigh ed by p oduc ion sha e. Then, we
de i e a mixed-in ege p og am, e o mula ing box place-
men cons ain s.
4.1 Ma hema ical p og am
We in oduce con inuous a iables πi,jas box posi ion and
Ci,jas comple ion ime o job (i,j)∈J. Then, a ma he-
ma ical p og am o Pmcan be s a ed as:
minimize 
i∈I
iCi,ni
subjec o
Ci,0=0,i∈I,(5a)
Ci,j≥Ci,j−1+i,j−aCi,j−1−πi,k,(i,j)∈J,(5b)
Ci,j≥Ci,j−1+i,j+bCi,j−1−πi,k,(i,j)∈J,(5c)
{πi,j}(i,j)∈Jbeing a box placemen . (5d)
Comple ion imes a e se ecu si ely in cons ain s (5b) and
(5c) s a ing wi h (5a). Cons ain (5d) es ic s he box posi-
ion a iables o a alid box placemen as de ined in (1).
We obse e ha a aining a alid box placemen co e-
sponds o a job sequencing p oblem on a single machine,
which de e mines each job’s p ocessing in e al om s a
ime o comple ion ime. This is alike o he in e al a box
is placed upon; he di e ence being ha he job’s in e al is
ypically deno ed by i s end ( he comple ion ime), while we
ins ead desc ibe a box posi ion by he in e al s a .
On a side no e, i is known om job sequencing ha idle
imes add a u he laye o complexi y, e.g., when op i-
mizing non- egula objec i es like ea liness and a diness
penal ies (Ga ey e al., 1988). Simila ly, we p esume ha he
assump ion o placing boxes wi hou gaps p o ides, besides
he p ac ical eason, a compu a ional bene i .
123
Jou nal o Scheduling (2024) 27:257–275 263
4.2 Mixed-in ege p og am
Model (5) is es ic ed o a mixed-in ege p og am by subs i-
u ing heplacemen cons ain s(5d).The eexis sa a ie yo
possible o mula ions in he ela ed domain o job sequenc-
ing, c . Quey anne and Schulz (1994), Keha e al. (2009),
Bake and Kelle (2010) o e iews. We use disjunc i e
sequencing cons ain s o ensu e consis ency and compa-
abili y wi h he mixed-in ege p og am and he nume ical
s udy in Sedding (2020c) o he single-model case m=1.
Fo job sequencing, his me hod is ea ed, e.g., in Manne
(1960), Balas (1985), Quey anne (1993).
Disjunc i e sequencing cons ain s yield a o al o de on
he boxes o decide he posi ion o each. This is es ablished
by disjunc i e cons ain s be ween each pai o jobs.
Le us ease he no a ion by in oducing (i,j)≺(h,k),
a ela ion be ween jobs (i,j), (h,k)∈J ha holds i and
only i i<h, and in case o i=h,i j<k. Mo eo e ,
we abb e ia e a job’s pai no a ion by a single le e , i.e., by
w i ing x=(i,j)o y=(h,k)in his sec ion.
Then, (5d) is subs i u ed by
πx+wx≤πy∨πy+wy≤πx,x,y∈J,x≺y,(6)
V≤πx≤W−wx,x∈J.(7)
This can be e o mula ed as a mixed-in ege p og am using
he ‘big-M’ me hod. This elaxes ei he o he inequali ies in
(6) by adding W, because πx+wx≤W o all x∈J.Le
ux,ydeno e a bina y a iable o each job pai x,y∈Jwi h
x≺y. Then, while (7) emains, (6) is eplaced wi h
πx+wx≤πy+W1−ux,y,x,y∈J,x≺y,(8a)
πy+wy≤πx+Wu
x,y,x,y∈J,x≺y,(8b)
ux,y∈{0,1},x,y∈J,x≺y.(8c)
The esul ing mixed-in ege p og am (MIP) encompasses
cons ain s (5a)–(5c), (7), (8a)–(8c), wi h n(n−1)/2 bina y
a iables.
5 Lowe bound
A lowe bound on he minimum objec i e alue φ∗o a
Pmins ance is in oduced in he ollowing. We conside a
Lag angian elaxa ion o he ma hema ical p og am (5) and
show ha i is possible o sol e i wi h a quad a ic ime algo-
i hm.
The lowe bound also accep s a pa ially sol ed ins ance
o use wi hin a b anch and bound sea ch. A solu ion can
be cons uc ed by placing he boxes in he placemen in e -
al [V,W).I s a sa Vwi h he i s box,and places henex
box besides. This is epea ed un il all boxes a e placed. An
in e media e, pa ial solu ion can be subsumed as ollows.
De ini ion 4 A pa ial solu ion p o ides he box posi ion
πi,j,(i,j)∈JF, o a se o ixed jobs JF⊆Jsuch ha hese
boxes a e placed in [V,F)whe e F=V+(i,j)∈JFwi,j,
i.e., he e is V≤πi,j≤F−wi,j o (i,j)∈JF. Then, we
call {πi,j}(i,j)∈JFapa ial box placemen . I is comple ed by
placing he boxes o he emaining open jobs JO=J JF
be ween Fand W.
5.1 Recu ence sol ing
In (5), we sol e he ecu ence ela ion o he comple ion
ime a iables o a closed o m. Le us in oduce, o each
job (i,j)∈J, a con inuous a iable walking ime ωi,jand
de ia ion δi,jo he job’s s a ime om i s ideal s a ime
(i.e., πi,j). Each comple ion ime a iable is eplaced by
a sum o all assembly and walking imes un il hen. This
eplaces cons ain s (5a) o(5c) wi h
Ci,j=
k=1,..., j
i,k+ωi,k,(i,j)∈J,(9a)
ωi,j≥−aδi,j,(i,j)∈J,(9b)
ωi,j≥bδi,j,(i,j)∈J,(9c)
δi,j=−πi,j+
k=1,..., j−1
i,k+ωi,k,(i,j)∈J.(9d)
Walking ime is piecewise linea and, because i is mini-
mized, limi ed om below in cons ain s (9b) and (9c). I
depends on he de ia ion o a job’s s a ime o i s posi ion,
se in cons ain s (9d).
The walking ime a iables’ domain can be limi ed o
s eng hen he model: he domain is no less han ze o, and a
mos ,i co esponds o hewalking imein o wa dsdi ec ion
o a mos he box posi ion W−1, and in he backwa ds di ec-
ion, o he lowes possible posi ion V(and back). Hence,
0≤ωi,j≤max−aCi,j−1−(W−1),bCi,j−1−V
o (i,j)∈J. Subs i u ing he comple ion imes a iables
wi h he sum in (9a) gi es, o (i,j)∈J, he closed o mula
0≤ωi,j≤max⎧
⎨
⎩
−a⎛
⎝1−W+
k=1,..., j−1
i,k+ωi,k⎞
⎠,
b⎛
⎝−V+
k=1,..., j−1
i,k+ωi,k⎞
⎠⎫
⎬
⎭
.(9e)
123
264 Jou nal o Scheduling (2024) 27:257–275
5.2 Lag angian elaxa ion
Wi h he model modi ica ions, we pe o m a Lag angian
elaxa ion o cons ain s (9b) and (9c). This in oduces he
co esponding Lag angian mul iplie s λi,j≥0, λ
i,j≥0 o
(i,j)∈J.
Then, he Lag angian p oblem is
φ∗
Lag (L)=min φLag
wi h
φLag =
i∈I
iCi,ni+
(i,j)∈J
λi,j−aδi,j−ωi,j
+λ
i,jbδi,j−ωi,j(10)
subjec o
L=λi,j,λ

i,j(i,j)∈J≥0,
as well as cons ain s (9a) o(9e), and cons ain (5d).
The se o mul iplie s Lcan be op imized using a s anda d
subg adien op imiza ion, see Fishe (2004). No e ha he
lowe bound inequali y φ∗
Lag (L)≤φ∗holds o any L.
Subs i u ing he comple ion ime a iables in (10) acco d-
ing o (9a) yields
φLag =
(i,j)∈J
i(i,j+ωi,j)+(bλ
i,j−aλi,j)δi,j−(λi,j+λ
i,j)ωi,j
=
(i,j)∈J
i,jζi,j+
(i,j)∈J
ωi,jθi,j
 
Ω
+
(i,j)∈Jaλi,j−bλ
i,jπi,j
 
Π
wi h cons an s
ζi,j= i+
k=j+1,...,nibλ
i,k−aλi,k,(i,j)∈J,
and θi,j=ζi,j−λi,j+λ
i,j,(i,j)∈J.
Obse e ha he walking ime and box placemen a iables
occu only in di e en cons ain s.
P ope y 1 In he Lag angian p oblem, hewalking ime a i-
ables ωi,j,(i,j)∈J, and box posi ion a iables πi,j,
(i,j)∈JO( om De ini ion 4), a e independen .
Thus, i is possible o sepa a ely op imize walking imes and
box posi ions. This gi es us he pa ial objec i e
Ω=
(i,j)∈J
ωi,jθi,j
o he walking imes, and
Π=
(i,j)∈Jaλi,j−bλ
i,jπi,j
o he box posi ions.
5.3 Op imizing box posi ion alues
The boxes o he open jobs JO(c . De ini ion 4)a e o
be placed wi hin a box sequence be ween Fand W.In
pa ial objec i e Π, each box (i,j)∈JOadds e m
aλi,j−bλ
i,jπi,j. Hence o minimize Π, we ge a clas-
sic o al weigh ed comple ion ime scheduling p oblem o
he boxes (as jobs), which is sol ed in polynomial ime by
so ing hem (Smi h, 1956).
Lemma 1 Pa ial objec i e Πis minimum i πi,j,(i,j)∈JO,
a e ob ained by sequencing JO’s boxes noninc easingly by
aλi,j−bλ
i,j
wi,j
.
Thus o nO=|JO|, op imal box posi ion alues a e a ained
in O(nOlog nO) ime.
5.4 Op imizing walking ime alues
The walking ime a iables ωi,j,(i,j)∈J, a e op imized
by minimizing Ω.
Fo each (i,j)∈J, he alue ange o ωi,jis limi ed by
cons ain s (9e). I can be ans o med wi h cons an s qi,j=
−V+k=1,..., j−1i,kand q
i,j=1−W+qi,j+V o he
ange
0≤ωi,j≤max⎧
⎪
⎪
⎪
⎪
⎪
⎨
⎪
⎪
⎪
⎪
⎪
⎩
−a⎛
⎝q
i,j+
k=1,..., j−1
ωi,k⎞
⎠
 
αi,j
,
b⎛
⎝qi,j+
k=1,..., j−1
ωi,k⎞
⎠
 
βi,j
⎫
⎪
⎪
⎪
⎪
⎪
⎬
⎪
⎪
⎪
⎪
⎪
⎭
.(11)
We obse e o any i∈I, and wi h inc easing j om 1
o ni ha e m αi,j(as de ined in (11)) is noninc easing and
e m βi,j(as in (11)) is nondec easing. Hence, we can ind
some κi∈{0,...,ni}such ha αi,j>β
i,j o all j=κi+
1,...,ni. Gi en such a κi, we can eplace cons ain s (11)
by
0≤ωi,j≤αi,ji j≤κi,
0≤ωi,j≤βi,ji j>κ
i.
123
Jou nal o Scheduling (2024) 27:257–275 271
Table 5 Median (50%
pe cen ile), qua ile (25%, 75%
pe cen ile), and 95% pe cen ile
minimum walking ime
pe cen age o o al weigh ed
wo k ime o n=24 and
m=4 ins ances wi h a known
op imum, in walking eloci y
and walking s a egy pai s
S1 S2
Q25 (%) Q50 (%) Q75 (%) Q95 (%) Q25 (%) Q50 (%) Q75 (%) Q95 (%)
24651576733384350
42224273318212327
8 9.7 11 13 17 8.3 11 13 17
16 4.6 5.8 7.1 9.7 4.3 5.4 6.5 9.5
Fig. 3 Pe cen age o inished ins ances wi h n=24 and m=4ina
line plo o algo i hm un ime in seconds
Fig. 4 Box plo s o pe cen age walking ime e o PE(φ, φ∗)o a
heu is ic’s φ o n=24 and m=4 ins ances sol ed by B&B wi h
op imum φ∗
Wi h he SA uppe bound, an op imum is ound o 72%
o he ins ances, u he educing he MPE o 1.77%. Fo
n=24 and m=4, he median un ime is 0.140s, which
includes he SA un ime.
Excep o small ins ances, he ime-limi ed MIP a 10 o
60s has wo se PE and MPE alues e en hough he un ime is
much highe han o he o he heu is ics: The MIP’s median
un ime co esponds o he ime limi because a ailable com-
pu e ime is mos ly used up comple ely. Wi h a long un ime,
only a small PE emains.
An assessmen o he ull se o ins ances would equi e
knowledge o an op imal solu ion o all ins ances. Fo
2463 ins ances, an op imum could no be a ained wi hin
he 1 h ime limi wi h nei he exac algo i hm (MIP, B&B).
To s udy he se o all ins ances in a consis en way, we use
he objec i e alue φHo he long unning MIP (<1h) as
a e e ence, because i e u ns he smalles o e all MPE in
he p eceding subg oup analysis. The heu is ics’ objec i e
alue φcan hen be assessed wi h he pe cen age o ins ances
ha yield φ≤φH, and wi h he mean o he pe cen age walk-
ing ime e o PE(φ, φH)deno ed by HMPE. We obse e
simila esul s o his es as in he subg oup analysis. In
pa icula , execu ing he MIP o 60s gi es yields ela i ely
high HMPE o la ge ins ances. Compa ed o he MIP un-
ime o 1 h, he HMPE o he T B&B is no iceably less o
high nand m alues, while main aining a much sho e un-
ime. See also Table 7.
Concluding, he T B&BUB SA p o ides he bes heu is ic
solu ions, makes good use o SA’s ini ial uppe bound, and
e ains a low un ime. This sugges s ha he esea ch and
implemen a ion e o o he T B&B is wo hwhile, espe-
cially in combina ion wi h SA. Bo h he T B&B and he MIP
can be pa ame e ized ega ding solu ion quali y, al hough he
la e admi s g ea e walking ime in he same un ime.
8 Conclusion
In his pape , we conside he mixed-model placemen o
boxes o minimize wo ke walking a he mo ing assem-
bly line. The ime-dependen walking ime model allows o
a much highe p ecision acco ding o ou nume ical expe i-
men : in mos ins ances, cons an walking ime es ima es ha
123

272 Jou nal o Scheduling (2024) 27:257–275
Table 6 Heu is ic solu ions on ins ances sol ed op imally by B&B, g ouped by n,m, o bo h
nmWNID MIP (<10s) MIP (<60s) MIP (<1h) HC T B&BUB HC SA T B&BUB SA
op (%) MPE (%) op (%) MPE (%) op (%) MPE (%) op (%) MPE (%) op (%) MPE (%) op (%) MPE (%) op (%) MPE (%) op (%) MPE (%)
∗∗1 121 57 4.3 67 2.5 85 0.6 39 8.7 46 5.0 68 3.3 72 1.8
8∗4 66 100 0.0 100 0.0 100 0.0 82 2.5 92 0.6 95 0.9 98 0.1
12 ∗0 101 96 0.0 100 0.0 100 0.0 49 6.7 63 3.0 80 3.3 86 0.9
16 ∗0 127 63 1.3 80 0.4 99 0.0 32 9.1 39 5.7 66 3.6 70 1.8
20 ∗0 144 25 5.9 43 3.4 80 0.5 20 11.6 25 8.0 56 4.2 59 2.7
24 ∗0 157 9 12.2 21 7.9 52 2.2 14 13.1 16 6.9 45 4.1 48 2.8
28 ∗0 164 11 12.8 24 7.5 57 2.1 20 12.5 22 9.6 51 6.0 55 3.7
∗2 2 101 61 4.0 71 2.3 89 0.5 39 11.2 65 7.1 44 8.3 70 3.4
∗4 0 149 56 4.9 66 2.9 84 0.8 33 10.2 66 2.4 42 5.3 69 1.5
∗8 1 113 53 3.9 64 2.4 82 0.6 44 4.7 72 0.5 52 1.4 76 0.3
8 2 8 74 100 0.0 100 0.0 100 0.0 77 4.1 87 1.2 91 2.4 96 0.4
8 4 0 86 100 0.0 100 0.0 100 0.0 70 3.3 88 0.5 92 0.3 97 0.1
8 8 4 39 100 0.0 100 0.0 100 0.0 100 0.0 100 0.0 100 0.0 100 0.0
12 2 1 97 100 0.0 100 0.0 100 0.0 49 10.2 57 5.7 75 8.5 82 2.2
12 4 0 125 100 0.0 100 0.0 100 0.0 44 7.4 60 2.7 79 1.1 85 0.6
12 8 0 82 89 0.1 99 0.0 100 0.0 54 2.5 73 0.4 85 0.1 91 0.1
16 2 0 108 76 1.0 91 0.3 100 0.0 33 12.0 36 9.4 63 7.9 68 3.8
16 4 0 156 65 1.5 83 0.5 100 0.0 28 10.9 36 6.3 65 2.4 69 1.4
16 8 0 117 48 1.4 67 0.5 98 0.0 35 4.4 45 1.5 69 0.4 74 0.3
20 2 0 113 31 5.2 53 2.7 89 0.3 25 13.4 27 10.8 55 8.3 60 4.8
20 4 0 173 22 7.0 42 4.1 77 0.7 16 13.5 20 9.8 54 3.5 56 2.6
20 8 0 146 22 5.7 35 3.3 72 0.6 20 7.8 27 3.3 59 0.8 62 0.7
24 2 0 114 10 11.2 22 7.1 61 1.7 18 14.4 19 12.3 45 6.9 49 5.0
24 4 0 184 8 13.8 19 8.8 49 2.8 10 15.5 12 6.4 41 4.4 43 2.8
24 8 0 172 10 11.5 21 7.8 46 2.1 14 9.3 18 1.9 49 1.1 51 0.7
28 2 0 106 17 12.6 31 6.8 63 1.9 20 17.4 23 14.2 47 11.1 52 6.4
28 4 0 219 6 13.7 18 8.5 56 2.5 16 11.5 17 8.3 52 2.9 55 2.1
28 8 0 196 8 11.7 20 7.5 46 1.9 24 3.9 27 2.2 57 0.4 61 0.4
op , pe cen age o ins ances sol ed op imally among hose ha B&B sol ed wi hin 1 h; MPE, mean pe cen age walking ime e o o he ins ance’s minimum walking ime
∗agg ega e o all a ian s o he espec i e pa ame e
123
Jou nal o Scheduling (2024) 27:257–275 273
Table 7 Heu is ic solu ions on ins ances compa ed o he heu is ic MIP (<1h), g ouped by n,m, o bo h
nmWNID MIP (<10s) MIP (<60s) HC T B&BUB HC SA T B&BUB SA
≤φH(%) HMPE (%) ≤φH(%) HMPE (%) ≤φH(%) HMPE (%) ≤φH(%) HMPE (%) ≤φH(%) HMPE (%) ≤φH(%) HMPE (%) ≤φH(%) HMPE (%)
∗∗1 124 50 5.0 60 2.8 39 8.2 49 4.6 72 2.3 76 0.9
8∗4 66 100 0.0 100 0.0 82 2.5 92 0.6 95 0.9 98 0.1
12 ∗0 101 96 0.0 100 0.0 49 6.7 63 3.0 80 3.3 86 0.9
16 ∗0 127 63 1.3 81 0.4 32 9.1 39 5.7 66 3.6 71 1.8
20 ∗0 143 25 5.4 45 2.8 23 11.0 29 7.4 62 3.7 66 2.1
24 ∗0 151 10 9.9 22 5.6 22 10.7 35 4.6 63 1.9 67 0.6
28 ∗0 153 6 13.2 13 7.8 28 9.3 34 6.5 66 0.8 69 −0.5
∗2 1 101 55 4.6 64 2.5 41 10.3 68 5.9 45 7.7 73 2.5
∗4 0 148 50 5.5 60 3.1 33 9.6 70 1.5 44 5.0 74 0.6
∗8 1 121 46 4.8 56 2.8 44 4.7 78 −0.4 57 1.1 81 −0.5
8 2 8 74 100 0.0 100 0.0 77 4.1 87 1.2 91 2.4 96 0.4
8 4 0 86 100 0.0 100 0.0 70 3.3 88 0.5 92 0.3 97 0.1
8 8 4 39 100 0.0 100 0.0 100 0.0 100 0.0 100 0.0 100 0.0
12 2 1 97 100 0.0 100 0.0 49 10.2 57 5.7 75 8.5 82 2.2
12 4 0 125 100 0.0 100 0.0 44 7.4 60 2.7 79 1.1 85 0.6
12 8 0 82 89 0.1 99 0.0 54 2.5 73 0.4 85 0.1 91 0.1
16 2 0 108 76 1.0 91 0.3 33 12.0 36 9.4 64 7.9 68 3.8
16 4 0 156 65 1.5 83 0.5 28 10.9 36 6.3 65 2.4 69 1.4
16 8 0 117 48 1.4 67 0.5 35 4.4 46 1.5 70 0.4 75 0.2
20 2 0 112 31 4.8 54 2.4 26 13.1 28 10.5 57 8.0 62 4.4
20 4 0 171 22 6.2 44 3.4 19 12.7 24 9.0 60 2.8 63 1.9
20 8 0 145 22 5.0 38 2.7 23 7.1 34 2.7 70 0.2 72 0.1
24 2 0 110 10 9.5 23 5.4 25 12.3 27 10.2 57 4.7 61 3.0
24 4 0 176 9 10.8 21 5.9 18 12.6 29 3.7 60 1.8 64 0.1
24 8 0 166 10 9.3 23 5.6 24 7.4 50 −0.2 72 −0.9 77 −1.3
28 2 0 105 10 12.2 18 6.8 33 10.4 34 9.0 63 3.9 67 1.5
28 4 0 176 4 14.4 10 8.7 22 10.8 26 8.0 62 0.6 66 −0.6
28 8 0 180 4 13.0 12 8.0 29 6.7 42 2.5 72 −2.2 74 −2.4
≤φH, pe cen age o ins ances sol ed a leas as well as he heu is ic objec i e alue φH ha MIP a ained wi hin 1 h; HMPE, mean pe cen age walking ime e o o he walking ime a ained by
he MIP wi hin 1 h (heu is ically)
∗agg ega e o all a ian s o he espec i e pa ame e
123
274 Jou nal o Scheduling (2024) 27:257–275
include 95% o cases a e a leas 51% highe han wi h ou
ime-dependen model (see Sec . 7.5).
We p o e ha his op imiza ion p oblem is NP-ha d in he
s ong sense o any numbe o p oduc models. We obse e
ha mode a ely sized ins ances wi h up o 16 jobs can be
sol ed wi h a mixed-in ege p og am ha employs disjunc-
i e sequencing cons ain s o a oid box o e lapping. Fo
la ge ins ances, we cons uc b anch and bound-based algo-
i hms.A Lag angian elaxa ion leads o a lowe bound ha is
sol ed in quad a ic ime. This bound is employed in a b anch
and bound sea ch, o which a unca ed sea ch ee yields
a heu is ic. Also, we desc ibe an in ui i e heu is ic ha is
complemen ed wi h a local sea ch and simula ed annealing
o ind an ini ial uppe bound.
The nume ical esul s indica e ha ou exac b anch and
bound based algo i hms p o ide supe io un ime and quali y
compa ed o sol ing a mixed-in ege p og am. The un ime
o he bes heu is ic ypically emains below 1 s, con ibu ing
o an in e ac i e planning expe ience ha is mo e accu a e
and pe mi s less sa e y bu e ime.
Funding Open access unding p o ided by ZHAW Zu ich Uni e si y
o Applied Sciences.
Decla a ions
Con lic o in e es The au ho has no compe ing in e es s o decla e
ha a e ele an o he con en o his a icle.
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 eduse,youwillneed oob ainpe missiondi ec ly om hecopy-
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
Ál a ez-Mi anda, E., & Pe ei a, J. (2019). On he complexi y o assem-
bly line balancing p oblems. Compu e s & Ope a ions Resea ch,
108, 182–186. h ps://doi.o g/10.1016/j.co .2019.04.005
And és, C., Mi alles, C., & Pas o , R. (2008). Balancing and schedul-
ing asks in assembly lines wi h sequence-dependen se up imes.
Eu opean Jou nal o Ope a ional Resea ch, 187(3), 1212–1223.
h ps://doi.o g/10.1016/j.ejo .2006.07.044
Bake , K. R., & Kelle , B. (2010). Sol ing he single-machine sequenc-
ing p oblem using in ege p og amming. Compu e s & Indus ial
Enginee ing, 59(4), 730–735. h ps://doi.o g/10.1016/j.cie.2010.
07.028
Balas, E. (1985). On he acial s uc u e o scheduling polyhed a.
Ma hema ical P og amming S udy, 24, 179–218. h ps://doi.o g/
10.1007/BFb0121051
Ba aïa, O., & Dolgui, A. (2013). A axonomy o line balancing
p oblems and hei solu ion app oaches. In e na ional Jou nal o
P oduc ion Economics, 142(2), 259–277. h ps://doi.o g/10.1016/
j.ijpe.2012.10.020
Ba aïa, O., & Dolgui, A. (2022). Hyb idiza ions in line balancing p ob-
lems: A comp ehensi e e iew on new ends and o mula ions.
In e na ional Jou nal o P oduc ion Economics, 250, 108673.
h ps://doi.o g/10.1016/j.ijpe.2022.108673
Bau is a, J., & Pe ei a, J. (2007). An algo i hms o a ime and space
cons ained assembly line balancing p oblem. Eu opean Jou nal
o Ope a ional Resea ch, 177(3), 2016–2032. h ps://doi.o g/10.
1016/j.ejo .2005.12.017
Becke , C., & Scholl, A. (2006). A su ey on p oblems and me hods in
gene alized assembly line balancing. Eu opean Jou nal o Ope -
a ional Resea ch, 168(3), 694–715. h ps://doi.o g/10.1016/j.ejo .
2004.07.023
Becke , C., & Scholl, A. (2009). Balancing assembly lines wi h a i-
able pa allel wo kplaces: P oblem de ini ion and e ec i e solu ion
p ocedu e. Eu opean Jou nal o Ope a ional Resea ch, 199(2),
359–374. h ps://doi.o g/10.1016/j.ejo .2008.11.051
Boysen,N.,Fliedne ,M.,&Scholl,A.(2008).Sequencingmixed-model
assembly lines o minimize pa in en o y cos . OR Spec um,
30(3), 611–633. h ps://doi.o g/10.1007/s00291-007-0095-2
Boysen, N., Fliedne , M., & Scholl, A. (2009a). Le el Scheduling o
ba ched JIT supply. Flexible Se ices and Manu ac u ing Jou nal,
21(1–2), 31–50. h ps://doi.o g/10.1007/s10696-009-9058-z
Boysen, N., Fliedne , M., & Scholl, A. (2009b). Le el scheduling o
mixed-model assembly lines unde s o age cons ain s. In e na-
ional Jou nal o P oduc ion Resea ch, 47(10),2669–2684.h ps://
doi.o g/10.1080/00207540701725067
Boysen, N., Fliedne , M., & Scholl, A. (2009c). Sequencing mixed-
model assembly lines: Su ey, classi ica ion and model c i ique.
Eu opean Jou nal o Ope a ional Resea ch, 192(2), 25. h ps://
doi.o g/10.1016/j.ejo .2007.09.013
Boysen,N., Scholl,A.,& Woppe e ,N.(2012). Resequencing o mixed-
model assembly lines: Su ey and esea ch agenda. Eu opean
Jou nal o Ope a ional Resea ch, 216(3), 594–604. h ps://doi.
o g/10.1016/j.ejo .2011.08.009
Boysen, N., Emde, S., Hoeck, M., & Kaude e , M. (2015). Pa logis ics
in he au omo i e indus y: Decision p oblems, li e a u e e iew
and esea ch agenda. Eu opean Jou nal o Ope a ional Resea ch,
242(1), 107–120. h ps://doi.o g/10.1016/j.ejo .2014.09.065
Boysen, N., Schulze, P., & Scholl, A. (2022). Assembly line balanc-
ing: Wha happened in he las i een yea s? Eu opean Jou nal o
Ope a ional Resea ch, 301(3), 797–814. h ps://doi.o g/10.1016/
j.ejo .2021.11.043
B en , R. P. (1971). An algo i hm wi h gua an eed con e gence o
inding a ze o o a unc ion. The Compu e Jou nal, 14(4), 422–
425. h ps://doi.o g/10.1093/comjnl/14.4.422
Bukchin, Y., & Melle , R. D. (2005). A space alloca ion algo i hm o
assemblylinecomponen s.IIE T ansac ions, 37(1),51–61.h ps://
doi.o g/10.1080/07408170590516854
ˇ
Ce ný, V. (1985). The modynamical app oach o he a eling salesman
p oblem: An e icien simula ion algo i hm. Jou nal o Op imiza-
ion Theo y and Applica ions, 45(1), 41–51. h ps://doi.o g/10.
1007/BF00940812
Esmaeilbeigi, R., Nade i, B., & Cha khga d, P. (2016). New o mu-
la ions o he se up assembly line balancing and scheduling
p oblem. OR Spec um, 38(2), 493–518. h ps://doi.o g/10.1007/
s00291-016-0433-3
Fa ahani, M. H., & Hosseini, L. (2013). Minimizing cycle ime in
single machine scheduling wi h s a ime-dependen p ocess-
ing imes. The In e na ional Jou nal o Ad anced Manu ac u ing
123
Jou nal o Scheduling (2024) 27:257–275 275
Technology, 64(9), 1479–1486. h ps://doi.o g/10.1007/s00170-
012-4116-1
Finnsgå d, C., Wäns öm, C., Medbo, L., & Neumann, W. P. (2011).
Impac o ma e ials exposu e on assembly wo ks a ion pe o -
mance. In e na ional Jou nal o P oduc ion Resea ch, 49(24),
7253–7274. h ps://doi.o g/10.1080/00207543.2010.503202
Fishe , M. L. (2004). The Lag angian Relaxa ion Me hod o Sol ing
In ege P og amming P oblems. Managemen Science, 50(12 Sup-
plemen ), 1861–1871. h ps://doi.o g/10.1287/mnsc.1040.0263
Fo d, H., & C ow he , S. (1922). My li e and wo k. Doubleday Page &
Co.
Ga ey, M. R., & Johnson, D. S. (1975). Complexi y esul s o mul i-
p ocesso scheduling unde esou ce cons ain s. SIAM Jou nal on
Compu ing, 4(4), 397–411. h ps://doi.o g/10.1137/0204035
Ga ey, M. R., & Johnson, D. S. (1978). “S ong” NP-comple eness
esul s: Mo i a ion, examples, and implica ions. Jou nal o he
ACM, 25(3), 499–508. h ps://doi.o g/10.1145/322077.322090
Ga ey, M. R., Ta jan, R. E., & Wil ong, G. T. (1988). One-p ocesso
schedulingwi hsymme icea linessand a dinesspenal ies.Ma h-
ema ics o Ope a ions Resea ch, 13(2), 330–348. h ps://doi.o g/
10.2307/3689828
Gawiejnowicz S (2020a) Models and Algo i hms o Time-Dependen
Scheduling, 2nd edn. Monog aphs in Theo e ical Compu e Sci-
ence, Sp inge , Be lin, Heidelbe g, h ps://doi.o g/10.1007/978-
3-662-59362-2
Gawiejnowicz, S. (2020b). A e iew o ou decades o ime-dependen
scheduling: Main esul s, new opics, and open p oblems. Jou nal
o Scheduling, 23(1), 3–47. h ps://doi.o g/10.1007/s10951-019-
00630-w
Hajek, B. (1988). Cooling schedules o op imal annealing. Ma hema -
ics o Ope a ions Resea ch, 13(2), 311–329. h ps://doi.o g/10.
1287/moo .13.2.311
Held, M., Wol e, P., & C owde , H. P. (1974). Valida ion o subg adien
op imiza ion. Ma hema ical P og amming, 6(1), 62–88. h ps://
doi.o g/10.1007/BF01580223
Jaehn, F., & Sedding, H. A. (2016). Scheduling wi h ime-dependen
disc epancy imes. Jou nal o Scheduling, 19(6), 737–757. h ps://
doi.o g/10.1007/s10951-016-0472-2
Kawase, Y., Makino, K., & Seimi, K. (2018). Op imal composi ion
o de ing p oblems o piecewise linea unc ions. Algo i hmica,
80(7), 2134–2159. h ps://doi.o g/10.1007/s00453-017-0397-y
Keha, A. B., Khowala, K., & Fowle , J. W. (2009). Mixed in ege p o-
g amming o mula ions o single machine scheduling p oblems.
Compu e s & Indus ial Enginee ing, 56(1), 357–367. h ps://doi.
o g/10.1016/j.cie.2008.06.008
Ki kpa ick, S., Gela , C. D., & Vecchi, M. P. (1983). Op imiza ion by
Simula ed Annealing. Science, 220(4598), 671–680. h ps://doi.
o g/10.1126/science.220.4598.671
Klamp l,E., Gusikhin, O.,& Rossi,G.(2006). Op imiza iono wo kcell
layou s in a mixed-model assembly line en i onmen . In e na-
ional Jou nal o Flexible Manu ac u ing Sys ems, 17(4),277–299.
h ps://doi.o g/10.1007/s10696-006-9029-6
Konono , A. V. (1998). P oblems in scheduling heo y on a single
machine wi h job du a ions p opo ional o an a bi a y unc ion.
Disk e ny˘ı Analiz i Issledo anie Ope a si˘ı, 5(3), 17–37.
Limè e, V., Landeghem, H. V., & Goe schalckx, M. (2015). A decision
model o ki ing and line s ocking wi h a iable ope a o walking
dis ances. Assembly Au oma ion, 35(1), 47–56. h ps://doi.o g/10.
1108/AA-05-2014-043
Manne, A. S. (1960). On he job-shop scheduling p oblem. Ope a ions
Resea ch, 8(2), 219–223. h ps://doi.o g/10.1287/op e.8.2.219
Mülle klein, D., Fon aine, P., & Os e meie , F. (2022). In eg a ed
conside a ion o assembly line scheduling and eeding: A new
model and case s udy om he au omo i e indus y. Compu e s
& Indus ial Enginee ing, 170, 108288. h ps://doi.o g/10.1016/j.
cie.2022.108288
P ess, W. H., Teukolsky, S. A., Ve e ling, W. T., & Flanne y, B. P.
(1992). Nume ical ecipes in C: The a o scien i ic compu ing.
Camb idge Uni e si y P ess.
Quey anne, M. (1993). S uc u e o a simple scheduling polyhed on.
Ma hema ical P og amming, 58(1–3), 263–285. h ps://doi.o g/
10.1007/BF01581271
Quey anne, M., & Schulz, A. S. (1994). Polyhed al app oaches o
machine scheduling. (p. 3). Tech. ep.: Technische Uni e si ä
Be lin, Fachbe eich.
Sal eson, M. E. (1955). The assembly line balancing p oblem. Jou nal
o Indus ial Enginee ing, 6(3), 18–25.
Schmid, N. A., & Limè e, V. (2019). A classi ica ion o ac ical assem-
bly line eeding p oblems. In e na ional Jou nal o P oduc ion
Resea ch, 57(24), 7586–7609. h ps://doi.o g/10.1080/00207543.
2019.1581957
Schmid, N. A., Limè e, V., & Raa, B. (2021). Mixed model assembly
line eeding wi h disc e e loca ion assignmen s and a iable s a-
ion space. Omega, 102, 102286. h ps://doi.o g/10.1016/j.omega.
2020.102286
Scholl, A., Boysen, N., & Fliedne , M. (2013). The assembly line
balancing and scheduling p oblem wi h sequence-dependen
se up imes: P oblem ex ension, model o mula ion and e icien
heu is ics. OR Spec um, 35(1), 291–320. h ps://doi.o g/10.1007/
s00291-011-0265-0
Sedding, H. A. (2017) Box placemen as ime dependen scheduling o
educe au omo i e assembly line wo ke walk imes. In P oceed-
ings o he 13 h Wo kshop on Models and Algo i hms o Planning
and Scheduling P oblems, Seeon, Ge many, pp 92–94.
Sedding, H. A. (2020a). Line side placemen o sho e assembly line
wo ke pa hs. IISE T ansac ions, 52(2), 181–198. h ps://doi.o g/
10.1080/24725854.2018.1508929
Sedding, H. A. (2020b). Scheduling jobs wi h a V-shaped ime-
dependen p ocessing ime.Jou nal o Scheduling, 23(6),751–768.
h ps://doi.o g/10.1007/s10951-020-00665-4
Sedding, H. A. (2020c). Time-dependen pa h scheduling: Algo i h-
mic minimiza ion o walking ime a he mo ing assembly line.
Sp inge . h ps://doi.o g/10.1007/978-3-658-28415-2
Sedding, H. A. (2021). A lowe bound o sequen ially placing boxes a
he mo ing assembly line o minimize walking ime. In P oceed-
ings o he 3 d In e na ional Wo kshop on Dynamic Scheduling
P oblems, Adam Mickiewicz Uni e si y, Pozna´n, Poland, pp 63–
69.
Smi h, W. E. (1956). Va ious op imize s o single-s age p oduc ion.
Na al Resea ch Logis ics Qua e ly, 3(1–2), 59–66. h ps://doi.
o g/10.1002/na .3800030106
S e na z, J. (2014). Enhanced mul i-Ho mann heu is ic o e icien ly
sol ing eal-wo ld assembly line balancing p oblems in au omo-
i e indus y. Eu opean Jou nal o Ope a ional Resea ch, 235(3),
740–754. h ps://doi.o g/10.1016/j.ejo .2013.11.005
S e na z, J. (2015). The join line balancing and ma e ial supply
p oblem. In e na ional Jou nal o P oduc ion Economics, 159,
304–318. h ps://doi.o g/10.1016/j.ijpe.2014.07.022
Thomopoulos, N. T. (1967). Line balancing-sequencing o mixed-
model assembly. Managemen Science, 14(2), B59–B75. h ps://
doi.o g/10.1287/mnsc.14.2.B59
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