IDEAS home Printed from https://ideas.repec.org/a/inm/ormnsc/v47y2001i10p1384-1395.html
   My bibliography  Save this article

A Dynamic Lot-Sizing Model with Demand Time Windows

Author

Listed:
  • Chung-Yee Lee

    (Department of Industrial Engineering, Texas A...M University, College Station, Texas 77843-3131)

  • Sila Çetinkaya

    (Department of Industrial Engineering, Texas A...M University, College Station, Texas 77843-3131)

  • Albert P. M. Wagelmans

    (Econometric Institute and RIBES, Erasmus University Rotterdam, P.O.Box 1738, 3000 DR Rotterdam, The Netherlands)

Abstract

One of the basic assumptions of the classical dynamic lot-sizing model is that the aggregate demand of a given period must be satisfied in that period. Under this assumption, if backlogging is not allowed, then the demand of a given period cannot be delivered earlier or later than the period. If backlogging is allowed, the demand of a given period cannot be delivered earlier than the period, but it can be delivered later at the expense of a backordering cost. Like most mathematical models, the classical dynamic lot-sizing model is a simplified paraphrase of what might actually happen in real life. In most real-life applications, the customer offers a grace period---we call it a demand time window---during which a particular demand can be satisfied with no penalty. That is, in association with each demand, the customer specifies an acceptable earliest and a latest delivery time. The time interval characterized by the earliest and latest delivery dates of a demand represents the corresponding time window. This paper studies the dynamic lot-sizing problem with demand time windows and provides polynomial time algorithms for computing its solution. If backlogging is not allowed, the complexity of the proposed algorithm is O(T 2 ) where T is the length of the planning horizon. When backlogging is allowed, the complexity of the proposed algorithm is O(T 3 ).

Suggested Citation

  • Chung-Yee Lee & Sila Çetinkaya & Albert P. M. Wagelmans, 2001. "A Dynamic Lot-Sizing Model with Demand Time Windows," Management Science, INFORMS, vol. 47(10), pages 1384-1395, October.
    • Handle: RePEc:inm:ormnsc:v:47:y:2001:i:10:p:1384-1395
    DOI: 10.1287/mnsc.47.10.1384
    as

    Download full text from publisher

    File URL: http://dx.doi.org/10.1287/mnsc.47.10.1384
    Download Restriction: no
    File URL: https://libkey.io/10.1287/mnsc.47.10.1384?utm_source=ideas
    LibKey link: if access is restricted and if your library uses this service, LibKey will redirect you to where you can use your library subscription to access this item
    ---><---

    References listed on IDEAS

    as
    1. Niklas Kohl & Oli B. G. Madsen, 1997. "An Optimization Algorithm for the Vehicle Routing Problem with Time Windows Based on Lagrangian Relaxation," Operations Research, INFORMS, vol. 45(3), pages 395-406, June.
    2. Albert Wagelmans & Stan van Hoesel & Antoon Kolen, 1992. "Economic Lot Sizing: An O(n log n) Algorithm That Runs in Linear Time in the Wagner-Whitin Case," Operations Research, INFORMS, vol. 40(1-supplem), pages 145-156, February.
    3. Marshall L. Fisher & Kurt O. Jörnsten & Oli B. G. Madsen, 1997. "Vehicle Routing with Time Windows: Two Optimization Algorithms," Operations Research, INFORMS, vol. 45(3), pages 488-492, June.
    4. Martin Desrochers & Jacques Desrosiers & Marius Solomon, 1992. "A New Optimization Algorithm for the Vehicle Routing Problem with Time Windows," Operations Research, INFORMS, vol. 40(2), pages 342-354, April.
    5. Harvey M. Wagner & Thomson M. Whitin, 1958. "Dynamic Version of the Economic Lot Size Model," Management Science, INFORMS, vol. 5(1), pages 89-96, October.
    6. Hoesel C.P.M. van & Wagelmans A.P.M., 1997. "Fully polynomial approximation schemes for single-item capacitated economic lot-sizing problems," Research Memorandum 014, Maastricht University, Maastricht Research School of Economics of Technology and Organization (METEOR).
    7. Dong X. Shaw & Albert P. M. Wagelmans, 1998. "An Algorithm for Single-Item Capacitated Economic Lot Sizing with Piecewise Linear Production Costs and General Holding Costs," Management Science, INFORMS, vol. 44(6), pages 831-838, June.
    8. Liman, Surya D. & Panwalkar, Shrikant S. & Thongmee, Sansern, 1996. "Determination of common due window location in a single machine scheduling problem," European Journal of Operational Research, Elsevier, vol. 93(1), pages 68-74, August.
    9. van Hoesel, C.P.M. & Wagelmans, A.P.M., 1997. "Fully Polynomial Approximation Schemes for Single-Item Capacitated Economic Lot-Sizing Problems," Econometric Institute Research Papers EI 9735/A, Erasmus University Rotterdam, Erasmus School of Economics (ESE), Econometric Institute.
    10. Cary Swoveland, 1975. "A Deterministic Multi-Period Production Planning Model with Piecewise Concave Production and Holding-Backorder Costs," Management Science, INFORMS, vol. 21(9), pages 1007-1013, May.
    11. Awi Federgruen & Michal Tzur, 1991. "A Simple Forward Algorithm to Solve General Dynamic Lot Sizing Models with n Periods in 0(n log n) or 0(n) Time," Management Science, INFORMS, vol. 37(8), pages 909-925, August.
    12. Alok Aggarwal & James K. Park, 1993. "Improved Algorithms for Economic Lot Size Problems," Operations Research, INFORMS, vol. 41(3), pages 549-571, June.
    13. Gabriel R. Bitran & Thomas L. Magnanti & Horacio H. Yanasse, 1984. "Approximation Methods for the Uncapacitated Dynamic Lot Size Problem," Management Science, INFORMS, vol. 30(9), pages 1121-1140, September.
    14. Chung-Yee Lee & Eric V. Denardo, 1986. "Rolling Planning Horizons: Error Bounds for the Dynamic Lot Size Model," Mathematics of Operations Research, INFORMS, vol. 11(3), pages 423-432, August.
    15. M. Florian & J. K. Lenstra & A. H. G. Rinnooy Kan, 1980. "Deterministic Production Planning: Algorithms and Complexity," Management Science, INFORMS, vol. 26(7), pages 669-679, July.
    Full references (including those not matched with items on IDEAS)

    Citations

    Citations are extracted by the CitEc Project, subscribe to its RSS feed for this item.
    as


    Cited by:

    1. Guan, Yongpei & Liu, Tieming, 2010. "Stochastic lot-sizing problem with inventory-bounds and constant order-capacities," European Journal of Operational Research, Elsevier, vol. 207(3), pages 1398-1409, December.
    2. Hark-Chin Hwang, 2009. "Inventory Replenishment and Inbound Shipment Scheduling Under a Minimum Replenishment Policy," Transportation Science, INFORMS, vol. 43(2), pages 244-264, May.
    3. Jans, R.F. & Degraeve, Z., 2005. "Modeling Industrial Lot Sizing Problems: A Review," ERIM Report Series Research in Management ERS-2005-049-LIS, Erasmus Research Institute of Management (ERIM), ERIM is the joint research institute of the Rotterdam School of Management, Erasmus University and the Erasmus School of Economics (ESE) at Erasmus University Rotterdam.
    4. Yasemin Merzifonluoğlu & Joseph Geunes & H.E. Romeijn, 2007. "Integrated capacity, demand, and production planning with subcontracting and overtime options," Naval Research Logistics (NRL), John Wiley & Sons, vol. 54(4), pages 433-447, June.
    5. Akartunalı, Kerem & Dauzère-Pérès, Stéphane, 2022. "Dynamic lot sizing with stochastic demand timing," European Journal of Operational Research, Elsevier, vol. 302(1), pages 221-229.
    6. Hark-Chin Hwang, 2010. "Economic Lot-Sizing for Integrated Production and Transportation," Operations Research, INFORMS, vol. 58(2), pages 428-444, April.
    7. WOLSEY, Laurence A., 2005. "Lot-sizing with production and delivery time windows," LIDAM Discussion Papers CORE 2005043, Université catholique de Louvain, Center for Operations Research and Econometrics (CORE).
    8. Brahimi, Nadjib & Absi, Nabil & Dauzère-Pérès, Stéphane & Nordli, Atle, 2017. "Single-item dynamic lot-sizing problems: An updated survey," European Journal of Operational Research, Elsevier, vol. 263(3), pages 838-863.
    9. Guiffrida, Alfred L. & Nagi, Rakesh, 2006. "Cost characterizations of supply chain delivery performance," International Journal of Production Economics, Elsevier, vol. 102(1), pages 22-36, July.
    10. Yongpei Guan & Andrew J. Miller, 2008. "Polynomial-Time Algorithms for Stochastic Uncapacitated Lot-Sizing Problems," Operations Research, INFORMS, vol. 56(5), pages 1172-1183, October.
    11. Nadjib Brahimi & Stéphane Dauzère-Pérès & Najib M. Najid, 2006. "Capacitated Multi-Item Lot-Sizing Problems with Time Windows," Operations Research, INFORMS, vol. 54(5), pages 951-967, October.
    12. Yongpei Guan, 2011. "Stochastic lot-sizing with backlogging: computational complexity analysis," Journal of Global Optimization, Springer, vol. 49(4), pages 651-678, April.
    13. Hwang, Hark-Chin & Jaruphongsa, Wikrom, 2008. "Dynamic lot-sizing model for major and minor demands," European Journal of Operational Research, Elsevier, vol. 184(2), pages 711-724, January.
    14. Yiyong Xiao & Meng You & Xiaorong Zuo & Shenghan Zhou & Xing Pan, 2018. "The Uncapacitatied Dynamic Single-Level Lot-Sizing Problem under a Time-Varying Environment and an Exact Solution Approach," Sustainability, MDPI, vol. 10(11), pages 1-14, October.
    15. Bakker, Hannah & Bindewald, Viktor & Dunke, Fabian & Nickel, Stefan, 2023. "Logistics for diagnostic testing: An adaptive decision-support framework," European Journal of Operational Research, Elsevier, vol. 311(3), pages 1120-1133.
    16. Hark‐Chin Hwang, 2007. "Dynamic lot‐sizing model with production time windows," Naval Research Logistics (NRL), John Wiley & Sons, vol. 54(6), pages 692-701, September.
    17. Jaruphongsa, Wikrom & Cetinkaya, Sila & Lee, Chung-Yee, 2004. "Warehouse space capacity and delivery time window considerations in dynamic lot-sizing for a simple supply chain," International Journal of Production Economics, Elsevier, vol. 92(2), pages 169-180, November.
    18. Darvish, Maryam & Coelho, Leandro C., 2018. "Sequential versus integrated optimization: Production, location, inventory control, and distribution," European Journal of Operational Research, Elsevier, vol. 268(1), pages 203-214.
    19. Andrew Lim & Zhaowei Miao & Brian Rodrigues & Zhou Xu, 2005. "Transshipment through crossdocks with inventory and time windows," Naval Research Logistics (NRL), John Wiley & Sons, vol. 52(8), pages 724-733, December.
    20. Merzifonluoglu, Yasemin & Geunes, Joseph, 2006. "Uncapacitated production and location planning models with demand fulfillment flexibility," International Journal of Production Economics, Elsevier, vol. 102(2), pages 199-216, August.
    21. Brahimi, Nadjib & Dauzere-Peres, Stephane & Najid, Najib M. & Nordli, Atle, 2006. "Single item lot sizing problems," European Journal of Operational Research, Elsevier, vol. 168(1), pages 1-16, January.

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. Chung-Yee Lee & Sila Çetinkaya & Albert P.M. Wagelmans, 1999. "A Dynamic Lot-Sizing Model with Demand Time Windows," Tinbergen Institute Discussion Papers 99-095/4, Tinbergen Institute.
    2. Lee, C.Y. & Cetinkaya, S. & Wagelmans, A.P.M., 1999. "A dynamic lot-sizing model with demand time windows," Econometric Institute Research Papers EI 9948-/A, Erasmus University Rotterdam, Erasmus School of Economics (ESE), Econometric Institute.
    3. Chung-Lun Li & Qingying Li, 2016. "Polynomial-Time Solvability of Dynamic Lot Size Problems," Asia-Pacific Journal of Operational Research (APJOR), World Scientific Publishing Co. Pte. Ltd., vol. 33(03), pages 1-20, June.
    4. Chung-Yee Lee & Sila Çetinkaya & Wikrom Jaruphongsa, 2003. "A Dynamic Model for Inventory Lot Sizing and Outbound Shipment Scheduling at a Third-Party Warehouse," Operations Research, INFORMS, vol. 51(5), pages 735-747, October.
    5. van den Heuvel, W.J. & Wagelmans, A.P.M., 2003. "A geometric algorithm to solve the NI/G/NI/ND capacitated lot-sizing problem in O(T2) time," Econometric Institute Research Papers EI 2003-24, Erasmus University Rotterdam, Erasmus School of Economics (ESE), Econometric Institute.
    6. Hwang, Hark-Chin & Jaruphongsa, Wikrom, 2008. "Dynamic lot-sizing model for major and minor demands," European Journal of Operational Research, Elsevier, vol. 184(2), pages 711-724, January.
    7. Jans, Raf & Degraeve, Zeger, 2007. "Meta-heuristics for dynamic lot sizing: A review and comparison of solution approaches," European Journal of Operational Research, Elsevier, vol. 177(3), pages 1855-1875, March.
    8. Stan van Hoesel & H. Edwin Romeijn & Dolores Romero Morales & Albert P. M. Wagelmans, 2005. "Integrated Lot Sizing in Serial Supply Chains with Production Capacities," Management Science, INFORMS, vol. 51(11), pages 1706-1719, November.
    9. Awi Federgruen & Joern Meissner & Michal Tzur, 2007. "Progressive Interval Heuristics for Multi-Item Capacitated Lot-Sizing Problems," Operations Research, INFORMS, vol. 55(3), pages 490-502, June.
    10. Vernon Ning Hsu, 2000. "Dynamic Economic Lot Size Model with Perishable Inventory," Management Science, INFORMS, vol. 46(8), pages 1159-1169, August.
    11. van den Heuvel, Wilco & Wagelmans, Albert P.M., 2006. "A polynomial time algorithm for a deterministic joint pricing and inventory model," European Journal of Operational Research, Elsevier, vol. 170(2), pages 463-480, April.
    12. Hark-Chin Hwang, 2009. "Inventory Replenishment and Inbound Shipment Scheduling Under a Minimum Replenishment Policy," Transportation Science, INFORMS, vol. 43(2), pages 244-264, May.
    13. Fink, Jiří & Hurink, Johann L., 2015. "Minimizing costs is easier than minimizing peaks when supplying the heat demand of a group of houses," European Journal of Operational Research, Elsevier, vol. 242(2), pages 644-650.
    14. Goisque, Guillaume & Rapine, Christophe, 2017. "An efficient algorithm for the 2-level capacitated lot-sizing problem with identical capacities at both levels," European Journal of Operational Research, Elsevier, vol. 261(3), pages 918-928.
    15. Chung-Lun Li & Vernon Ning Hsu & Wen-Qiang Xiao, 2004. "Dynamic Lot Sizing with Batch Ordering and Truckload Discounts," Operations Research, INFORMS, vol. 52(4), pages 639-654, August.
    16. van den Heuvel, W.J. & Wagelmans, A.P.M., 2008. "A holding cost bound for the economic lot-sizing problem with time-invariant cost parameters," Econometric Institute Research Papers EI 2008-10, Erasmus University Rotterdam, Erasmus School of Economics (ESE), Econometric Institute.
    17. van Hoesel, C.P.M. & Romeijn, H.E. & Romero Morales, M.D. & Wagelmans, A., 2002. "Polynomial time algorithms for some multi-level lot-sizing problems with production capacities," Research Memorandum 018, Maastricht University, Maastricht Research School of Economics of Technology and Organization (METEOR).
    18. Alper Atamtürk & Dorit S. Hochbaum, 2001. "Capacity Acquisition, Subcontracting, and Lot Sizing," Management Science, INFORMS, vol. 47(8), pages 1081-1100, August.
    19. van den Heuvel, W., 2004. "On the complexity of the economic lot-sizing problem with remanufacturing options," Econometric Institute Research Papers EI 2004-46, Erasmus University Rotterdam, Erasmus School of Economics (ESE), Econometric Institute.
    20. Liu, X. & Tu, Yl., 2008. "Production planning with limited inventory capacity and allowed stockout," International Journal of Production Economics, Elsevier, vol. 111(1), pages 180-191, January.

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:inm:ormnsc:v:47:y:2001:i:10:p:1384-1395. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: Chris Asher (email available below). General contact details of provider: https://edirc.repec.org/data/inforea.html .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.