Abstract
The problem of sequencing assembly lines consists of determining the order in which a given set of products is launched down the line. Since individual products may require different parts in different quantities, the production sequence has a big influence on line-side inventory. Classically, sequences are often optimized with the goal of attaining level schedules, i.e., the part demand should be smooth during the planning horizon. However, this approach does not necessarily work well if parts are delivered at discrete points in time in bulk quantities. In this paper, we consider a production system where bins of parts are delivered periodically by a tow train from a central depot at fixed times. Due to the limited space at the assembly line, the maximum number of bins in stock at any time at any station should be minimal. We propose an exact solution method based on combinatorial Benders decomposition as well as bounding procedures and heuristics for this problem. The algorithms are shown to perform well both on instances from the literature and on new data sets. We also investigate whether classic level scheduling methods are effective at reducing line-side stock in an assembly system supplied by tow train, and to what degree line-side stock can be traded off for more frequent deliveries.
Similar content being viewed by others
References
Akgündüz, O. S., & Tunalı, S. (2011). A review of the current applications of genetic algorithms in mixed-model assembly line sequencing. International Journal of Production Research, 49(15), 4483–4503.
Bard, J. F., Dar-Elj, E., & Shtub, A. (1992). An analytic framework for sequencing mixed model assembly lines. The International Journal of Production Research, 30(1), 35–48.
Battini, D., Boysen, N., & Emde, S. (2013). Just-in-time supermarkets for part supply in the automobile industry. Journal of Management Control, 24(2), 209–217.
Bautista, J., Companys, R., & Corominas, A. (1996). Heuristics and exact algorithms for solving the Monden problem. European Journal of Operational Research, 88(1), 101–113.
Benders, J. F. (1962). Partitioning procedures for solving mixed-variables programming problems. Numerische Mathematik, 4(1), 238–252.
Boysen, N., & Emde, S. (2014). Scheduling the part supply of mixed-model assembly lines in line-integrated supermarkets. European Journal of Operational Research, 239(3), 820–829.
Boysen, N., Emde, S., Hoeck, M., & Kauderer, M. (2015). Part logistics in the automotive industry: Decision problems, literature review and research agenda. European Journal of Operational Research, 242(1), 107–120.
Boysen, N., Fliedner, M., & Scholl, A. (2008). Sequencing mixed-model assembly lines to minimize part inventory cost. OR Spectrum, 30(3), 611–633.
Boysen, N., Fliedner, M., & Scholl, A. (2009a). Level scheduling for batched JIT supply. Flexible Services and Manufacturing Journal, 21(1–2), 31–50.
Boysen, N., Fliedner, M., & Scholl, A. (2009b). Level scheduling of mixed-model assembly lines under storage constraints. International Journal of Production Research, 47(10), 2669–2684.
Boysen, N., Fliedner, M., & Scholl, A. (2009c). Sequencing mixed-model assembly lines: Survey, classification and model critique. European Journal of Operational Research, 192(2), 349–373.
Choi, W., & Lee, Y. (2002). A dynamic part-feeding system for an automotive assembly line. Computers & industrial engineering, 43(1), 123–134.
Codato, G., & Fischetti, M. (2006). Combinatorial Benders’ cuts for mixed-integer linear programming. Operations Research, 54(4), 756–766.
Emde, S. (2017a). Optimally scheduling interfering and non-interfering cranes. Naval Research Logistics (NRL), 64(6), 476–489.
Emde, S. (2017b). Scheduling the replenishment of just-in-time supermarkets in assembly plants. OR Spectrum, 39(1), 321.
Emde, S., & Boysen, N. (2012a). Optimally locating in-house logistics areas to facilitate JIT-supply of mixed-model assembly lines. International Journal of Production Economics, 135(1), 393–402.
Emde, S., & Boysen, N. (2012b). Optimally routing and scheduling tow trains for JIT-supply of mixed-model assembly lines. European Journal of Operational Research, 217(2), 287–299.
Emde, S., Fliedner, M., & Boysen, N. (2012). Optimally loading tow trains for just-in-time supply of mixed-model assembly lines. IIE Transactions, 44(2), 121–135.
Emde, S., & Gendreau, M. (2017). Scheduling in-house transport vehicles to feed parts to automotive assembly lines. European Journal of Operational Research, 260(1), 255–267.
Fliedner, M., Boysen, N., & Scholl, A. (2011). On the part inventory model sequencing problem: Complexity and beam search heuristic. Journal of Scheduling, 14(1), 17–25.
Garey, M., & Johnson, D. (1979). Computers and intractability: A guide to the theory of NP-hardness. San Francisco, CA: WH Freeman.
Giordano, F., & Schiraldi, M. M. (2013). On just-in-time production leveling. In M. M. Schiraldi (Ed.), Operations management (pp. 141–163). Rijeka: InTech.
Golz, J., Gujjula, R., Günther, H.-O., Rinderer, S., & Ziegler, M. (2012). Part feeding at high-variant mixed-model assembly lines. Flexible Services and Manufacturing Journal, 24(2), 119–141.
Hooker, J. N., & Ottosson, G. (2003). Logic-based Benders decomposition. Mathematical Programming, 96(1), 33–60.
Kubiak, W. (1993). Minimizing variation of production rates in just-in-time systems: A survey. European Journal of Operational Research, 66(3), 259–271.
Limère, V., Landeghem, H. V., Goetschalckx, M., Aghezzaf, E.-H., & McGinnis, L. F. (2012). Optimising part feeding in the automotive assembly industry: Deciding between kitting and line stocking. International Journal of Production Research, 50(15), 4046–4060.
Monden, Y. (2011). Toyota production system: An integrated approach to just-in-time (4th ed.). Boca Raton, FL: CRC Press.
Pereira, J., & Vilà, M. (2015). An exact algorithm for the mixed-model level scheduling problem. International Journal of Production Research, 53(19), 5809–5825.
Rahmaniani, R., Crainic, T. G., Gendreau, M., & Rei, W. (2017). The Benders decomposition algorithm: A literature review. European Journal of Operational Research, 259(3), 801–817.
Solnon, C., Cung, V. D., Nguyen, A., & Artigues, C. (2008). The car sequencing problem: Overview of state-of-the-art methods and industrial case-study of the ROADEF’2005 challenge problem. European Journal of Operational Research, 191(3), 912–927.
Yavuz, M., & Ergin, H. (2018). Advanced constraint propagation for the combined car sequencing and level scheduling problem. Computers & Operations Research, 100, 128–139.
Author information
Authors and Affiliations
Corresponding author
Additional information
Publisher's Note
Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.
Rights and permissions
About this article
Cite this article
Emde, S., Polten, L. Sequencing assembly lines to facilitate synchronized just-in-time part supply. J Sched 22, 607–621 (2019). https://doi.org/10.1007/s10951-019-00606-w
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10951-019-00606-w