IDEAS home Printed from https://ideas.repec.org/a/spr/jsched/v24y2021i2d10.1007_s10951-020-00645-8.html
   My bibliography  Save this article

Cyclic lot-sizing problems with sequencing costs

Author

Listed:
  • Alexander Grigoriev

    (Maastricht University)

  • Vincent J. Kreuzen

    (Maastricht University)

  • Tim Oosterwijk

    (Maastricht University)

Abstract

We study a single-machine lot-sizing problem, where n types of products need to be scheduled on the machine. Each product is associated with a constant demand rate, maximum production rate and inventory costs per time unit. Every time when the machine switches production between products, sequencing costs are incurred. These sequencing costs depend both on the product the machine just produced and on the product the machine is about to produce. The goal is to find a cyclic schedule minimizing total average costs, subject to the condition that all demands are satisfied. We establish the complexity of the problem, and we prove a number of structural properties largely characterizing optimal solutions. Moreover, we present two algorithms approximating the optimal schedules by augmenting the problem input. Due to the high-multiplicity setting, even trivial cases of the corresponding conventional counterparts become highly non-trivial with respect to the output sizes and computational complexity, even without sequencing costs. In particular, the length of an optimal solution can be exponential in the input size of the problem. Nevertheless, our approximation algorithms produce schedules of a polynomial length and with a good quality compared to the optimal schedules of exponential length.

Suggested Citation

  • Alexander Grigoriev & Vincent J. Kreuzen & Tim Oosterwijk, 2021. "Cyclic lot-sizing problems with sequencing costs," Journal of Scheduling, Springer, vol. 24(2), pages 123-135, April.
    • Handle: RePEc:spr:jsched:v:24:y:2021:i:2:d:10.1007_s10951-020-00645-8
    DOI: 10.1007/s10951-020-00645-8
    as

    Download full text from publisher

    File URL: http://link.springer.com/10.1007/s10951-020-00645-8
    File Function: Abstract
    Download Restriction: Access to the full text of the articles in this series is restricted.
    File URL: https://libkey.io/10.1007/s10951-020-00645-8?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
    ---><---

    As the access to this document is restricted, you may want to search for a different version of it.

    References listed on IDEAS

    as
    1. Dorit S. Hochbaum & Ron Shamir, 1991. "Strongly Polynomial Algorithms for the High Multiplicity Scheduling Problem," Operations Research, INFORMS, vol. 39(4), pages 648-653, August.
    2. Michaël Gabay & Alexander Grigoriev & Vincent J. C. Kreuzen & Tim Oosterwijk, 2016. "High Multiplicity Scheduling with Switching Costs for Few Products," Operations Research Proceedings, in: Marco Lübbecke & Arie Koster & Peter Letmathe & Reinhard Madlener & Britta Peis & Grit Walther (ed.), Operations Research Proceedings 2014, edition 1, pages 437-443, Springer.
    3. Narro Lopez, Miguel A. & Kingsman, Brian G., 1991. "The economic lot scheduling problem: theory and practice," International Journal of Production Economics, Elsevier, vol. 23(1-3), pages 147-164, October.
    4. N. Brauner & Y. Crama & A. Grigoriev & J. Van De Klundert, 2007. "Multiplicity and complexity issues in contemporary production scheduling," Statistica Neerlandica, Netherlands Society for Statistics and Operations Research, vol. 61(1), pages 75-91, February.
    5. Michael Rothkopf, 1966. "Letter to the Editor—The Traveling Salesman Problem: On the Reduction of Certain Large Problems to Smaller Ones," Operations Research, INFORMS, vol. 14(3), pages 532-533, June.
    6. Dimitris Bertsimas & David Gamarnik & Jay Sethuraman, 2003. "From Fluid Relaxations to Practical Algorithms for High-Multiplicity Job-Shop Scheduling: The Holding Cost Objective," Operations Research, INFORMS, vol. 51(5), pages 798-813, October.
    7. Marco Lübbecke & Arie Koster & Peter Letmathe & Reinhard Madlener & Britta Peis & Grit Walther (ed.), 2016. "Operations Research Proceedings 2014," Operations Research Proceedings, Springer, edition 1, number 978-3-319-28697-6, December.
    8. Holmbom, Martin & Segerstedt, Anders, 2014. "Economic Order Quantities in production: From Harris to Economic Lot Scheduling Problems," International Journal of Production Economics, Elsevier, vol. 155(C), pages 82-90.
    9. Fayez Fouad Boctor, 1982. "The Two-Product, Single-Machine, Static Demand, Infinite Horizon Lot Scheduling Problem," Management Science, INFORMS, vol. 28(7), pages 798-807, July.
    10. John J. Clifford & Marc E. Posner, 2000. "High Multiplicity in Earliness-Tardiness Scheduling," Operations Research, INFORMS, vol. 48(5), pages 788-800, October.
    11. N. Brauner & Y. Crama & A. Grigoriev & J. Klundert, 2005. "A Framework for the Complexity of High-Multiplicity Scheduling Problems," Journal of Combinatorial Optimization, Springer, vol. 9(3), pages 313-323, May.
    12. Haase, Knut & Kimms, Alf, 2000. "Lot sizing and scheduling with sequence-dependent setup costs and times and efficient rescheduling opportunities," International Journal of Production Economics, Elsevier, vol. 66(2), pages 159-169, June.
    Full references (including those not matched with items on IDEAS)

    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. Cheng, T.C.E. & Shafransky, Y. & Ng, C.T., 2016. "An alternative approach for proving the NP-hardness of optimization problems," European Journal of Operational Research, Elsevier, vol. 248(1), pages 52-58.
    2. N. Brauner & Y. Crama & A. Grigoriev & J. Klundert, 2005. "A Framework for the Complexity of High-Multiplicity Scheduling Problems," Journal of Combinatorial Optimization, Springer, vol. 9(3), pages 313-323, May.
    3. Wolosewicz, Cathy & Dauzère-Pérès, Stéphane & Aggoune, Riad, 2015. "A Lagrangian heuristic for an integrated lot-sizing and fixed scheduling problem," European Journal of Operational Research, Elsevier, vol. 244(1), pages 3-12.
    4. Amorim, P. & Belo-Filho, M.A.F. & Toledo, F.M.B. & Almeder, C. & Almada-Lobo, B., 2013. "Lot sizing versus batching in the production and distribution planning of perishable goods," International Journal of Production Economics, Elsevier, vol. 146(1), pages 208-218.
    5. Heuts, R.M.J. & Nederstigt, P. & Roebroek, W. & Selen, W.J., 1992. "Multi-product cycling with packaging in the process industry," Other publications TiSEM 533d6bbb-e61a-4e4b-a44e-1, Tilburg University, School of Economics and Management.
    6. Selvarajah, Esaignani & Steiner, George, 2006. "Batch scheduling in a two-level supply chain--a focus on the supplier," European Journal of Operational Research, Elsevier, vol. 173(1), pages 226-240, August.
    7. John J. Clifford & Marc E. Posner, 2000. "High Multiplicity in Earliness-Tardiness Scheduling," Operations Research, INFORMS, vol. 48(5), pages 788-800, October.
    8. Kovcs, Andrs & Brown, Kenneth N. & Tarim, S. Armagan, 2009. "An efficient MIP model for the capacitated lot-sizing and scheduling problem with sequence-dependent setups," International Journal of Production Economics, Elsevier, vol. 118(1), pages 282-291, March.
    9. A. Agnetis & S. Smriglio, 2000. "Optimal assignment of high multiplicity flight plans to dispatchers," Naval Research Logistics (NRL), John Wiley & Sons, vol. 47(5), pages 359-376, August.
    10. Heuts, R.M.J. & Nederstigt, P. & Roebroek, W. & Selen, W.J., 1992. "Multi-product cycling with packaging in the process industry," Research Memorandum FEW 544, Tilburg University, School of Economics and Management.
    11. Sterna, Malgorzata, 2011. "A survey of scheduling problems with late work criteria," Omega, Elsevier, vol. 39(2), pages 120-129, April.
    12. Omri Dover & Dvir Shabtay, 2016. "Single machine scheduling with two competing agents, arbitrary release dates and unit processing times," Annals of Operations Research, Springer, vol. 238(1), pages 145-178, March.
    13. Manzhan Gu & Xiwen Lu & Jinwei Gu, 2017. "An asymptotically optimal algorithm for large-scale mixed job shop scheduling to minimize the makespan," Journal of Combinatorial Optimization, Springer, vol. 33(2), pages 473-495, February.
    14. Brander, Par & Forsberg, Rolf, 2006. "Determination of safety stocks for cyclic schedules with stochastic demands," International Journal of Production Economics, Elsevier, vol. 104(2), pages 271-295, December.
    15. Kirschstein, Thomas, 2018. "Planning of multi-product pipelines by economic lot scheduling models," European Journal of Operational Research, Elsevier, vol. 264(1), pages 327-339.
    16. Christoph Hertrich & Christian Weiß & Heiner Ackermann & Sandy Heydrich & Sven O. Krumke, 2020. "Scheduling a proportionate flow shop of batching machines," Journal of Scheduling, Springer, vol. 23(5), pages 575-593, October.
    17. Ferreira, Deisemara & Clark, Alistair R. & Almada-Lobo, Bernardo & Morabito, Reinaldo, 2012. "Single-stage formulations for synchronised two-stage lot sizing and scheduling in soft drink production," International Journal of Production Economics, Elsevier, vol. 136(2), pages 255-265.
    18. Vidal-Carreras, Pilar I. & Garcia-Sabater, Jose P. & Coronado-Hernandez, Jairo R., 2012. "Economic lot scheduling with deliberated and controlled coproduction," European Journal of Operational Research, Elsevier, vol. 219(2), pages 396-404.
    19. Dolgui, Alexandre & Kovalev, Sergey & Kovalyov, Mikhail Y. & Nossack, Jenny & Pesch, Erwin, 2014. "Minimizing setup costs in a transfer line design problem with sequential operation processing," International Journal of Production Economics, Elsevier, vol. 151(C), pages 186-194.
    20. Leven, Erik & Segerstedt, Anders, 2007. "A scheduling policy for adjusting economic lot quantities to a feasible solution," European Journal of Operational Research, Elsevier, vol. 179(2), pages 414-423, June.

    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:spr:jsched:v:24:y:2021:i:2:d:10.1007_s10951-020-00645-8. 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: Sonal Shukla or Springer Nature Abstracting and Indexing (email available below). General contact details of provider: http://www.springer.com .

    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.