Skip to main content
SpringerLink
Log in

Multiple machine continuous setup lotsizing with sequence-dependent setups

  • Published:
Computational Optimization and Applications Aims and scope Submit manuscript

Abstract

We address the short-term production planning and scheduling problem coming from the glass container industry. A furnace melts the glass that is distributed to a set of parallel molding machines. Both furnace and machine idleness are not allowed. The resulting multi-machine multi-item continuous setup lotsizing problem with a common resource has sequence-dependent setup times and costs. Production losses are penalized in the objective function since we deal with a capital intensive industry. We present two mixed integer programming formulations for this problem, which are reduced to a network flow type problem. The two formulations are improved by adding valid inequalities that lead to good lower bounds. We rely on a Lagrangian decomposition based heuristic for generating good feasible solutions. We report computational experiments for randomly generated instances and for real-life data on the aforementioned problem, as well as on a discrete lotsizing and scheduling version.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  1. Ahuja, R.K., Magnanti, T.L., Orlin, J.B.: Network Flows: Theory, Algorithms, and Applications. Prentice-Hall, Englewood Cliffs (1993)

    Google Scholar 

  2. Almada-Lobo, B., Oliveira, J.F., Carravilla, M.A.: Production planning and scheduling in the glass container industry: A VNS approach. Int. J. Prod. Econ. 114, 363–375 (2008)

    Article  Google Scholar 

  3. Almada-Lobo, B., Klabjan, D., Carravilla, M.A., Oliveira, J.F.: Single machine multi-product capacitated lotsizing with sequence-dependent setups. Int. J. Prod. Res. 45, 4873–4894 (2007)

    Article  MATH  Google Scholar 

  4. Bertsekas, D.P.: Network Optimization: Continuous and Discrete Models. Athena Scientific, Belmont (1998)

    MATH  Google Scholar 

  5. Constantino, M.: A polyhedral approach to a production planning problem. Ann. Oper. Res. 96, 75–95 (2000)

    Article  MathSciNet  MATH  Google Scholar 

  6. Dematta, R., Guignard, M.: Dynamic production scheduling for a process industry. Oper. Res. 42, 492–503 (1994)

    Article  Google Scholar 

  7. Dematta, R., Guignard, M.: Studying the effects of production loss due to setup in dynamic production scheduling. Eur. J. Oper. Res. 72, 62–73 (1994)

    Article  Google Scholar 

  8. Dematta, R., Guignard, M.: The performance of rolling production schedules in a process industry. IIE Trans. 27, 564–573 (1995)

    Article  Google Scholar 

  9. Drexl, A., Kimms, A.: Lot sizing and scheduling—Survey and extensions. Eur. J. Oper. Res. 99, 221–235 (1997)

    Article  MATH  Google Scholar 

  10. Fleischmann, B.: The discrete lot-sizing and scheduling problem with sequence-dependent setup costs. Eur. J. Oper. Res. 75, 395–404 (1994)

    Article  MATH  Google Scholar 

  11. Geoffrion, A.M.: Lagrangian relaxation for integer programming. Math. Program. Study 2, 82–114 (1974)

    MathSciNet  Google Scholar 

  12. Held, M., Wolfe, P., Crowder, H.P.: Validation of subgradient optimization. Math. Program. 6, 62–88 (1974)

    Article  MathSciNet  MATH  Google Scholar 

  13. Hindi, K.S.: Solving the single-item, capacitated dynamic lot-sizing problem with startup and reservation costs by tabu search. Comput. Ind. Eng. 28, 701–707 (1995)

    Article  Google Scholar 

  14. Jans, R., Degraeve, Z.: An industrial extension of the discrete lot-sizing and scheduling problem. IIE Trans. 36, 47–58 (2004)

    Article  Google Scholar 

  15. Jans, R., Degraeve, Z.: Meta-heuristics for dynamic lot sizing: A review and comparison of solution approaches. Eur. J. Oper. Res. 177, 1855–1875 (2007)

    Article  MATH  Google Scholar 

  16. Karmarkar, U.S., Kekre, S., Kekre, S.: The dynamic lot-sizing problem with startup and reservation costs. Oper. Res. 35, 389–398 (1987)

    Article  MathSciNet  MATH  Google Scholar 

  17. Karmarkar, U.S., Schrage, L.: The deterministic dynamic product cycling problem. Oper. Res. 33, 326–345 (1985)

    Article  MATH  Google Scholar 

  18. Pochet, Y., Wolsey, L.A.: Production Planning by Mixed Integer Programming. Springer, New York (2006)

    MATH  Google Scholar 

  19. Salomon, M., Solomon, M.M., Van Wassenhove, L.N., Dumas, Y., Dauzere-Peres, S.: Solving the discrete lotsizing and scheduling problem with sequence dependent set-up costs and set-up times using the Travelling Salesman Problem with time windows. Eur. J. Oper. Res. 100, 494–513 (1997)

    Article  MATH  Google Scholar 

  20. Sandbothe, R.A.: A user interactive heuristic procedure for solving the multiple product cycling problem. Comput. Oper. Res. 23, 897–907 (1996)

    Article  MATH  Google Scholar 

  21. Vanderbeck, F.: Lot-sizing with start-up times. Manag. Sci. 44, 1409–1425 (1998)

    Article  MATH  Google Scholar 

  22. Wolsey, L.A.: MIP modelling of changeovers in production planning and scheduling problems. Eur. J. Oper. Res. 99, 154–165 (1997)

    Article  MATH  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. DEIG—Faculdade de Engenharia da Universidade do Porto, R.Dr. Roberto Frias, s/n, Porto, 4200-465, Portugal

    Bernardo Almada-Lobo

  2. Department of Industrial Engineering and Management Sciences, Northwestern University, Evanston, IL, USA

    Diego Klabjan

  3. Faculdade de Engenharia, da Universidade do Porto, Instituto de Engenharia de Sistemas e Computadores do Porto Campus da FEUP, Porto, Portugal

    Maria Antónia Carravilla & José F. Oliveira

Authors
  1. Bernardo Almada-Lobo
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Diego Klabjan
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Maria Antónia Carravilla
    View author publications

    You can also search for this author in PubMed Google Scholar

  4. José F. Oliveira
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Bernardo Almada-Lobo.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Almada-Lobo, B., Klabjan, D., Carravilla, M.A. et al. Multiple machine continuous setup lotsizing with sequence-dependent setups. Comput Optim Appl 47, 529–552 (2010). https://doi.org/10.1007/s10589-009-9235-8

Download citation

  • Received:

  • Revised:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s10589-009-9235-8

Keywords

Search

Navigation