Explicit modeling of multi-period setup times in proportional lot-sizing and scheduling problem with variable capacity

• Autorzy: Kaczmarczyk Waldemar

Identyfikatory

DOI

10.24425/acs.2021.139735

• Języki publikacji: EN

Abstrakty

EN

Small bucket models with many short fictitious micro-periods ensure high-quality schedules in multi-level systems, i.e., with multiple stages or dependent demand. In such models, setup times longer than a single period are, however, more likely. This paper presents new mixed-integer programming models for the proportional lot-sizing and scheduling problem (PLSP) with setup operations overlapping multiple periods with variable capacity. A new model is proposed that explicitly determines periods overlapped by each setup operation and the time spent on setup execution during each period. The model assumes that most periods have the same length; however, a few of them are shorter, and the time interval determined by two consecutive shorter periods is always longer than a single setup operation. The computational experiments show that the new model requires a significantly smaller computation effort than known models.

Słowa kluczowe

EN

production; lot-sizing; scheduling; mixed-integer programming

• Wydawca: Polish Academy of Sciences, Committee of Automatic Control and Robotics
• Czasopismo: Archives of Control Sciences
• Rocznik: 2021
• Tom: Vol. 31, No. 4
• Strony: 883--912
• Opis fizyczny: Bibliogr. 22 poz., rys., tab., wzory

Twórcy

autor

Kaczmarczyk Waldemar

• Department of Strategic Management, AGH University of Science and Technology, Al. Mickiewicza 30, 30-059, Kraków, Poland

Bibliografia

• [1] I. Barany, T.J. van Roy and L.A. Wolsey: Uncapacitated lot-sizing: The convex hull of solutions. Mathematical Programming Studies, 22 (1984), 32-43, DOI: 10.1007/BFb0121006.
• [2] G. Belvaux and L.A. Wolsey: Modelling practical lot-sizing problems as mixed-integer programs. Management Science, 47(7), (2001), 993-1007, DOI: 10.1287/mnsc.47.7.993.9800.
• [3] J.D. Blocher, S. Chand and K. Sengupta: The changeover scheduling problem with time and cost considerations: Analytical results and a forward algorithm. Operations Research, 47(7), (1999), 559-569, DOI: 10.1287/opre.47.4.559.
• [4] W. Bozejko, M. Uchronski and M. Wodecki: Multi-machine scheduling problem with setup times. Archives of Control Sciences, 22(4), (2012), 441- 449, DOI: 10.2478/v10170-011-0034-y.
• [5] W. Bozejko, A. Gnatowski, R. Idzikowski and M. Wodecki: Cyclic flow shop scheduling problem with two-machine cells. Archives of Control Sciences, 27(2), (2017), 151-167, DOI: 10.1515/acsc-2017-0009.
• [6] D. Cattrysse, M. Salomon, R. Kuik and L. van Wassenhove: A dual ascent and column generation heuristic for the discrete lotsizing and scheduling problem with setup times. Management Science, 39(4), (1993), 477-486, DOI: 10.1287/mnsc.39.4.477.
• [7] K. Copil, M. Worbelauer, H. Meyr and H. Tempelmeier: Simultaneous lotsizing and scheduling problems: a classification and review of models. OR Spectrum, 39(1), (2017), 1-64, DOI: 10.1007/s00291-015-0429-4.
• [8] A. Drexl and K. Haase: Proportional lotsizing and scheduling. International Journal of Production Economics, 40(1), (1995), 73-87, DOI: 10.1016/0925-5273(95)00040-U.
• [9] B. Fleischmann: The discrete lot-sizing and scheduling problem. European Journal of Operational Research, 44(3), (1990), 337-348, DOI: 10.1016/0377-2217(90)90245-7.
• [10] K. Haase: Lotsizing and scheduling for production planning. Number 408 in Lecture Notes in Economics and Mathematical Systems. Springer-Verlag, Berlin, 1994.
• [11] W. Kaczmarczyk: Inventory cost settings in small bucket lot-sizing and scheduling models. In Total Logistic Management Conference, Zakopane, Poland, November 25-28 2009.
• [12] W. Kaczmarczyk: Modelling multi-period set-up times in the proportional lot-sizing problem. Decision Making in Manufacturing and Services, 3(1-2), (2009), 15-35, DOI: 10.7494/dmms.2009.3.2.15.
• [13] W. Kaczmarczyk: Proportional lot-sizing and scheduling problem with identical parallel machines. International Journal of Production Research, 49(9), (2011), 2605-2623, DOI: 10.1080/00207543.2010.532929.
• [14] W. Kaczmarczyk: Valid inequalities for proportional lot-sizing and scheduling problem with fictitious microperiods. International Journal of Production Economics, 219(1), (2020), 236-247, DOI: 10.1016/j.ijpe.2019.06.005.
• [15] W. Kaczmarczyk: Explicit modelling of multi-period setup times in proportional lot-sizing problem with constant capacity. (2021), Preprint available at Research Square, DOI: 10.21203/rs.3.rs-1086310/v1.
• [16] U.S. Karmarkar and L. Schrage: The deterministic dynamic product cycling problem. Operations Research, 33(2), (1985), 326-345, DOI: 10.1287/opre.33.2.326.
• [17] A. Kimms and A. Drexl: Proportional lot sizing and scheduling: Some extensions. Networks, 32(2), (1998), 85-101, DOI: https://doi.org/10.1002/ (SICI)1097-0037(199809)32:23.0.CO;2-E.
• [18] J. Krystek and M. Kozik: Analysis of the job shop system with transport and setup times in deadlock-free operating conditions. Archives of Control Sciences, 22(4), (2012), 417-425, DOI: 10.2478/v10170-011-0032-0.
• [19] Y. Pochet and L.A. Wolsey: Production planning by mixed integer programming. Series in Operations Research and Financial Engineering. Springer, New York, 2006.
• [20] J. Rudy, J. Pempera and Cz. Smutnicki: Improving the TSAB algorithm through parallel computing. Archives of Control Sciences, 30(2), (2020), 411-435, DOI: 10.24425/acs.2020.134672.
• [21] C. Suerie: Modeling of period overlapping setup times. European Journal of Operational Research, 174(2), (2006), 874-886, DOI: 10.1016/ j.ejor.2005.03.033.
• [22] H. P. Williams. Model building in Mathematical Programming. Wiley, 2006.

Uwagi

1. This work has been supported by NCN Research Grant #DEC-2013/11/B/ST8/04458 and by AGH UST Grant #11.11.200.324.

2. Opracowanie rekordu ze środków MNiSW, umowa Nr 461252 w ramach programu "Społeczna odpowiedzialność nauki" - moduł: Popularyzacja nauki i promocja sportu (2021).