×

Level scheduling under limited resequencing flexibility. (English) Zbl 1213.90116

Summary: A mixed-model assembly line requires the solution of a short-term sequencing problem, which decides on the succession of different models launched down the line. A famous solution approach stemming from the Toyota production system is the so-called level scheduling (LS), which aims to distribute the part consumption induced by a model sequence evenly over the planning horizon. LS attracted a multitude of different researchers, who, however, invariably treat initial sequence planning where all degrees of freedom in assigning models to production cycles exist. In the real-world, conflicting objectives and restrictions of preceding production stages, i.e., body and paint shop, simultaneously need to be considered and perturbations of an initial sequence will regularly occur, so that the sequencing problem often becomes a resequencing problem. Here, a given model sequence is to be reshuffled with the help of resequencing buffers (denoted as pull-off tables). This paper shows how to adapt famous solution approaches for alternative LS problems, namely the product-rate-variation (PRV) and the output-rate-variation (ORV) problem, if the (re-)assignment of models to cycles is restricted by the given number of pull-off tables. Furthermore, the effect of increasing re-sequencing flexibility is investigated, so that the practitioner receives decision support for buffer dimensioning, and the ability of the PRV in reasonably approximating the more detailed ORV in a resequencing environment is tested.

MSC:

90B35 Deterministic scheduling theory in operations research
90B30 Production models

References:

[1] Bautista J, Companys R, Corominas A (1996) Heuristics and exact algorithms for solving the Monden problem. Eur J Operat Res 88:101–113 · Zbl 0913.90159 · doi:10.1016/0377-2217(94)00165-0
[2] Boysen N, Fliedner M, Scholl A (2009a) Sequencing mixed-model assembly lines: survey, classification and model critique. Eur J Operat Res 192:349–373 · Zbl 1157.90405 · doi:10.1016/j.ejor.2007.09.013
[3] Boysen N, Fliedner M, Scholl A (2009b) The product rate variation problem and its relevance in real world mixed-model assembly lines. Eur J Operat Res 197:818–824 · Zbl 1159.90359 · doi:10.1016/j.ejor.2008.06.038
[4] Brauner N, Crama Y (2004) The maximum deviation just-in-time scheduling problem. Discrete Appl Math 134:25–50 · Zbl 1042.90015 · doi:10.1016/S0166-218X(03)00222-1
[5] Dhamala TN, Kubiak W (2005) A brief survey of just-in-time sequencing for mixed-model systems. International Journal of Operations Research 2: 38–47 · Zbl 1115.90337
[6] Ding F-Y, Cheng L (1993a) A simple sequencing algorithm for mixed-model assembly lines in just-in-time production systems. Operat Res Lett 13:27–36 · Zbl 0771.90050 · doi:10.1016/0167-6377(93)90081-Q
[7] Ding F-Y, Cheng L (1993b) An effective mixed-model assembly line sequencing heuristic for just-in-time production systems. J Operat Manag 11:45–65 · doi:10.1016/0272-6963(93)90032-K
[8] Ding F-Y, Sun H (2004) Sequence alteration and restoration related to sequenced parts delivery on an automobile mixed-model assembly line with multiple departments. Int J Product Res 42:1525–1543 · doi:10.1080/00207540310001645156
[9] Fliedner M, Boysen N, Scholl A (2010) Solving symmetric mixed-model multi-level just-in-time scheduling problems. Discrete Appl Math 158:222–231 · Zbl 1185.90074 · doi:10.1016/j.dam.2009.09.013
[10] Gusikhin O, Caprihan R, Stecke KE (2008) Least in-sequence probability heuristic for mixed-volume production lines. Int J Product Res 46:647–673 · Zbl 1128.90379 · doi:10.1080/00207540600824300
[11] Hopcroft J, Karp R (1973) An n2.5 algorithm for maximum matching in bipartite graphs. SIAM J Comput 2:225–231 · Zbl 0266.05114 · doi:10.1137/0202019
[12] Inman RR, Bulfin RL (1991) Sequencing JIT mixed-model assembly lines. Manag Sci 37:901–904 · Zbl 0729.90672 · doi:10.1287/mnsc.37.7.901
[13] Inman RR, Bulfin RL (1992) Quick and dirty sequencing for mixed-model multi-level JIT systems. Int J Product Res 30:2011–2018 · doi:10.1080/00207549208948135
[14] Inman RR, Schmeling DM (2003) Algorithm for agile assembly-to-order in the automotive industry. Int J Product Res 41:3831–3848 · doi:10.1080/00207540310001595792
[15] Kubiak W (1993) Minimizing variation of production rates in just-in-time systems: a survey. Eur J Operat Res 66:259–271 · Zbl 0771.90051 · doi:10.1016/0377-2217(93)90215-9
[16] Kubiak W (2003) Cyclic just-in-time sequences are optimal. J Global Optim 27:333–347 · Zbl 1134.90475 · doi:10.1023/A:1024847308982
[17] Kubiak W, Sethi SP (1991) A note on ”level schedules for mixed-model assembly lines in just-in-time production systems”. Manag Sci 37:121–122 · Zbl 0727.90033 · doi:10.1287/mnsc.37.1.121
[18] Kubiak W, Sethi SP (1994) Optimal just-in-time schedules for flexible transfer lines. Int J Flexible Manuf Syst 6:137–154 · doi:10.1007/BF01328809
[19] Kubiak W, Steiner G, Yeomans JS (1997) Optimal level schedules for mixed-model, multi-level just-in-time assenbly systems. Ann Operat Res 69:241–259 · Zbl 0880.90061 · doi:10.1023/A:1018985029260
[20] Lahmar M, Benjaafar S (2007) Sequencing with limited flexibility. IIE Trans 39:937–955 · doi:10.1080/07408170701416665
[21] Lahmar M, Ergan H, Benjaafar S (2003) Resequencing and feature assignment on an automated assembly line. IEEE Trans Robotics 19:89–102 · doi:10.1109/TRA.2002.807556
[22] Lim A, Xu Z (2009) Searching optimal resequencing and feature assignment on an automated assembly line. J Operat Res Soc 60:361–371 · Zbl 1156.90367 · doi:10.1057/palgrave.jors.2602533
[23] Lowerre BT (1976) The HARPY speech recognition system. Ph.D. thesis, Carnegie-Mellon University, USA, April
[24] Miltenburg J (1989) Level Schedules for mixed-model assembly lines in just-in-time production systems. Manag Sci 35:192–207 · Zbl 0666.90040 · doi:10.1287/mnsc.35.2.192
[25] Monden Y (1998) Toyota production system: an integrated approach to just-in-time. 3rd edn, Norcross
[26] Ow PS, Morton TE (1988) Filtered beam search in scheduling. Int J Product Res 26:297–307
[27] Sabuncuoglu I, Gocgun Y, Erel E (2008) Backtracking and exchange of information: methods to enhance a beam search algorithm for assembly line scheduling. Eur J Operat Res 186:915–930 · Zbl 1149.90130 · doi:10.1016/j.ejor.2007.02.024
[28] Spieckermann S, Gutenschwager K, Voss S (2004) A sequential ordering problem in automotive paint shops. Int J Product Res 42:1865–1878 · Zbl 1094.90018 · doi:10.1080/00207540310001646821
[29] Steiner G, Yeomans JS (1993) Level schedules for mixed-model, just-in-time processes. Manag Sci 39:728–735 · Zbl 0783.90047 · doi:10.1287/mnsc.39.6.728
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.