Skip to main content
SpringerLink
Log in

Joint rolling-horizon scheduling of materials processing and lot-sizing with sequence-dependent setups

  • Published:
Journal of Heuristics Aims and scope Submit manuscript

Abstract

A lot sizing and scheduling problem from a foundry is considered in which key materials are produced and then transformed into many products on a single machine. A mixed integer programming (MIP) model is developed, taking into account sequence-dependent setup costs and times, and then adapted for rolling horizon use. A relax-and-fix (RF) solution heuristic is proposed and computationally tested against a high-performance MIP solver. Three variants of local search are also developed to improve the RF method and tested. Finally the solutions are compared with those currently practiced at the foundry.

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

  • Aarts, E.H.L., Lenstra, J.K.: Local Search in Combinatorial Optimization. Wiley, Chichester (1997)

    MATH  Google Scholar 

  • Araujo, S.A., Arenales, M.N., Clark, A.R.: A Lot-sizing and furnace scheduling in small market-driven foundries. Comput. Oper. Res. (2007, in press)

  • Arosio, M., Sianesi, A.: A heuristic algorithm for master production scheduling generation with finite capacity and sequence dependent setups. Int. J. Prod. Res. 31, 531–553 (1993)

    Article  Google Scholar 

  • Belvaux, G., Wolsey, L.A.: Modelling practical lot-sizing problems as mixed integer programs. Manag. Sci. 47, 993–1007 (2001)

    Article  Google Scholar 

  • Beraldi, P., Ghianib, G., Guerrieroc, E., Grieco, A.: Scenario-based planning for lot-sizing and scheduling with uncertain processing times. Int. J. Prod. Econ. 101(1), 140–149 (2006)

    Article  Google Scholar 

  • Clark, A.R.: Optimization approximations for capacity constrained material requirements planning problems. Int. J. Prod. Econ. 84, 115–131 (2003a)

    Article  Google Scholar 

  • Clark, A.R.: Hybrid heuristics for planning lot sizes and setups. Comput. Ind. Eng. 45, 545–562 (2003b)

    Article  Google Scholar 

  • Clark, A.R.: Rolling horizon heuristics for production and setup planning with backlogs and error-prone demand forecasts. Prod. Plan. Control 16, 81–97 (2005)

    Article  Google Scholar 

  • Diaz, A., Glover, F., Ghaziri, H.M., González, J.L., Laguna, M., Moscato, P., Tseng, F.T., Optimización Heurística y Redes Neuronales. Editorial Paraninfo, Spain (1996)

    Google Scholar 

  • Dillenberger, C., Escudero, L.F., Wollensak, A., Zhang, W.: On practical resource allocation for production planning and scheduling with period overlapping setups. Eur. J. Oper. Res. 75, 275–286 (1994)

    Article  MATH  Google Scholar 

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

    Article  MATH  Google Scholar 

  • Dumoulin, A., Vercellis, C.: Tactical models for hierarchical capacitated lot-sizing problems with setups and changeovers. Int. J. Prod. Res. 38, 51–67 (2000)

    Article  MATH  Google Scholar 

  • Eglese, R.W.: Simulated annealing: a tool for operational research. Eur. J. Oper. Res. 46, 271–281 (1990)

    Article  MATH  MathSciNet  Google Scholar 

  • Fleischmann, B., Meyr, H.: The general lotsizing and scheduling problem. Oper. Res. Spectr. 19, 11–21 (1997)

    Article  MATH  MathSciNet  Google Scholar 

  • Ghosh Dastidar, S., Nagi, R.: Scheduling injection molding operations with multiple resource constraints and sequence dependent setup times and costs. Comput. Oper. Res. 32, 2987–3005 (2005)

    Article  MATH  Google Scholar 

  • Glover, F.W., Kochenberger, G.A. (eds.): Handbook of Metaheuristics. Kluwer Academic, Boston (2003)

    MATH  Google Scholar 

  • Gopalakrishnan, M., Miller, D.M., Schmidt, C.P.: A framework for modelling setup carryover in the capacitated lot-sizing problem. Int. J. Prod. Res. 33, 1973–1988 (1995)

    Article  MATH  Google Scholar 

  • Gupta, D., Magnusson, T.: The capacitated lot-sizing and scheduling problem with sequence-dependent setup costs and setup times. Comput. Oper. Res. 32, 727–747 (2005)

    Article  MATH  MathSciNet  Google Scholar 

  • Haase, K., Kimms, A.: Lot sizing and scheduling with sequence dependent setup costs and times and efficient rescheduling opportunities. Int. J. Prod. Econ. 66, 159–169 (2000)

    Article  Google Scholar 

  • ILOG: Cplex 7.1 User’s manual. ILOG SA BP 85 9 Rue de Verdun 94253. Gentilly, France. http://www.ilog.com (2001)

  • Karimi, B., Fatemi Ghomi, S.M.T., Wilson, J.M.: The capacitated lot sizing problem: a review of models and algorithms. Omega 31, 365–378 (2003)

    Article  Google Scholar 

  • Kelly, J.D., Mann, J.L.: Flowsheet decomposition heuristic for scheduling: a relax-and-fix method. Comput. Chem. Eng. 28, 2193–2200 (2004)

    Article  Google Scholar 

  • Kuik, R., van Wassenhove, L.N., Maes, J.: Linear programming, simulated annealing and tabu search heuristics for lotsizing in bottleneck assembly systems. IIE Trans. 25(1), 62–72 (1993)

    Article  Google Scholar 

  • Meyr, H.: Simultaneous lotsizing and scheduling by combining local search with dual reoptimization. Eur. J. Oper. Res. 120, 311–326 (2000)

    Article  MATH  MathSciNet  Google Scholar 

  • Meyr, H.: Simultaneous lotsizing and scheduling on parallel machines. Eur. J. Oper. Res. 139, 277–292 (2002)

    Article  MATH  MathSciNet  Google Scholar 

  • Porkka, P., Vepsalainen, A.P.J., Kuula, M.: Multiperiod production planning carrying over set-up time. Int. J. Prod. Res. 41, 1133–1148 (2003)

    Article  MATH  Google Scholar 

  • Ovacik, I.M., Uzsoy, R.: Rolling horizon procedures for dynamic parallel machine scheduling with sequence dependent setup time. Int. J. Prod. Res. 33, 3173–3192 (1995)

    Article  MATH  Google Scholar 

  • Santos-Meza, E., Santos, M.O., Arenales, M.N.: Lot-sizing problem in an automated foundry. Eur. J. Oper. Res. 139, 490–500 (2002)

    Article  MATH  Google Scholar 

  • Smith-Daniels, V.L., Ritzman, L.P.: A model for lot sizing and sequencing in process industries. Int. J. Prod. Res. 26, 647–674 (1988)

    Article  Google Scholar 

  • Smith-Daniels, V.L., Smith-Daniels, D.E.: A mixed integer programming model for lot sizing and sequencing packaging lines in the process industries. IIE Trans. 18, 278–285 (1986)

    Article  Google Scholar 

  • Stadtler, H.: Multilevel lot sizing with setup times and multiple constrained resources: internally rolling schedules with lot-sizing windows. Oper. Res. 51, 487–502 (2003)

    Article  Google Scholar 

  • Suerie, C., Stadtler, H.: The capacitated lot-sizing problem with linked lot-sizes. Manag. Sci. 49, 1039–1054 (2003)

    Article  Google Scholar 

  • Teghem, J., Pirlot, M., Antoniadis, C.: Embedding of linear programming in a simulated annealing algorithm for solving a mixed integer production planning problem. J. Comput. Appl. Math. 64, 91–102 (1995)

    Article  MATH  MathSciNet  Google Scholar 

  • Wolsey, L.A., Integer Programming. Wiley, New York (1998)

    MATH  Google Scholar 

  • Wolsey, L.A.: Solving multi-item lot-sizing problems with an MIP solver using classification and reformulation. Manag. Sci. 48, 1587–1602 (2002)

    Article  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Universidade Estadual Paulista, Sao Jose do Rio Preto, Brazil

    Silvio A. de Araujo

  2. Universidade de São Paulo, Sao Carlos, Brazil

    Marcos N. Arenales

  3. Faculty of Computing, Engineering and Mathematical Sciences, University of the West of England, Bristol, BS16 1QY, UK

    Alistair R. Clark

Authors
  1. Silvio A. de Araujo
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Marcos N. Arenales
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Alistair R. Clark
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Alistair R. Clark.

Rights and permissions

Reprints and permissions

About this article

Cite this article

de Araujo, S.A., Arenales, M.N. & Clark, A.R. Joint rolling-horizon scheduling of materials processing and lot-sizing with sequence-dependent setups. J Heuristics 13, 337–358 (2007). https://doi.org/10.1007/s10732-007-9011-9

Download citation

  • Received:

  • Revised:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s10732-007-9011-9

Keywords

Search

Navigation