Mixed-model moving assembly line material placement optimization for a shorter time-dependent worker walking time

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