Level scheduling under limited resequencing flexibility
Tóm tắt
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.
Tài liệu tham khảo
Bautista J, Companys R, Corominas A (1996) Heuristics and exact algorithms for solving the Monden problem. Eur J Operat Res 88:101–113
Boysen N, Fliedner M, Scholl A (2009a) Sequencing mixed-model assembly lines: survey, classification and model critique. Eur J Operat Res 192:349–373
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
Brauner N, Crama Y (2004) The maximum deviation just-in-time scheduling problem. Discrete Appl Math 134:25–50
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
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
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
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
Fliedner M, Boysen N, Scholl A (2010) Solving symmetric mixed-model multi-level just-in-time scheduling problems. Discrete Appl Math 158:222–231
Gusikhin O, Caprihan R, Stecke KE (2008) Least in-sequence probability heuristic for mixed-volume production lines. Int J Product Res 46:647–673
Hopcroft J, Karp R (1973) An n2.5 algorithm for maximum matching in bipartite graphs. SIAM J Comput 2:225–231
Inman RR, Bulfin RL (1991) Sequencing JIT mixed-model assembly lines. Manag Sci 37:901–904
Inman RR, Bulfin RL (1992) Quick and dirty sequencing for mixed-model multi-level JIT systems. Int J Product Res 30:2011–2018
Inman RR, Schmeling DM (2003) Algorithm for agile assembly-to-order in the automotive industry. Int J Product Res 41:3831–3848
Kubiak W (1993) Minimizing variation of production rates in just-in-time systems: a survey. Eur J Operat Res 66:259–271
Kubiak W (2003) Cyclic just-in-time sequences are optimal. J Global Optim 27:333–347
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
Kubiak W, Sethi SP (1994) Optimal just-in-time schedules for flexible transfer lines. Int J Flexible Manuf Syst 6:137–154
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
Lahmar M, Benjaafar S (2007) Sequencing with limited flexibility. IIE Trans 39:937–955
Lahmar M, Ergan H, Benjaafar S (2003) Resequencing and feature assignment on an automated assembly line. IEEE Trans Robotics 19:89–102
Lim A, Xu Z (2009) Searching optimal resequencing and feature assignment on an automated assembly line. J Operat Res Soc 60:361–371
Lowerre BT (1976) The HARPY speech recognition system. Ph.D. thesis, Carnegie-Mellon University, USA, April
Miltenburg J (1989) Level Schedules for mixed-model assembly lines in just-in-time production systems. Manag Sci 35:192–207
Monden Y (1998) Toyota production system: an integrated approach to just-in-time. 3rd edn, Norcross
Ow PS, Morton TE (1988) Filtered beam search in scheduling. Int J Product Res 26:297–307
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
Spieckermann S, Gutenschwager K, Voss S (2004) A sequential ordering problem in automotive paint shops. Int J Product Res 42:1865–1878
Steiner G, Yeomans JS (1993) Level schedules for mixed-model, just-in-time processes. Manag Sci 39:728–735