A New Branching Rule to Solve the Capacitated Lot Sizing and Scheduling Problem with Sequence Dependent Setups

Willy Alves de Oliveira, Maristela Oliveira dos Santos

Abstract


In this paper, we deal with the Capacitated Lot Sizing and Scheduling Problem with sequencedependent setup times and costs - CLSD model. More specifically, we propose a simple reformulation for the CLSD model that enables us to define a new branching rule to be used in Branch-and-Bound (or Branch-and-Cut) algorithms to solve this NP-hard problem. Our branching rule can be easily implemented in commercial solvers. Computational tests performed in 240 test instances from the literature show that our approach can significantly reduce the running time to solve this problem using a Branch-and-Cut algorithm of a commercial MIP solver.Therefore, our approach can also improve the performance of other approaches that need to solve partial sub problems of the CLSD model in each iteration, such as Lagrangian approaches and heuristics based on the mathematical formulation of the problem.

Keywords


Lot Sizing; Scheduling; Mixed Integer Linear Programming; Branch-and-Bound Algorithm

Full Text:

PDF

References


B. Almada-Lobo, et al. ``Industrial insights into lot sizing and scheduling modeling''. Pesquisa Operacional, 2015.

C. Almeder and B. Almada-Lobo. ``Synchronisation of scarce resources for a parallel machine lotsizing problem''. International Journal of Production Research, v. 49, n. 24, p. 7315-7335, 2011.

S. A. de Araujo, M. N. Arenales and A. R. Clark. ``Lot sizing and furnace scheduling in small foundries''. Computers & Operations Research, 35.3: 916-932, 2008.

H. Chen. ``Fix-and-optimize and variable neighborhood search approaches for multi-level capacitated lot sizing problems''. Omega, 2015.

A. R. Clark and S. J. Clark. ``Rolling-horizon lot-sizing when set-up times are sequence-dependent''. International Journal of Production Research, 38.10: 2287-2307, 2000.

K. Copil, et al. ``Simultaneous lotsizing and scheduling problems: a classification and review of models''. OR Spectrum, 2016.

D. Ferreira, R. Morabito, and Socorro Rangel. ``Solution approaches for the soft drink integrated production lot sizing and scheduling problem''. European Journal of Operational Research, 196.2: 697-706, 2009.

D. Ferreira, R. Morabito, and Socorro Rangel. ``Relax and fix heuristics to solve one-stage one-machine lot-scheduling models for small-scale soft drink plants''. Computers & Operations Research, 37.4: 684-691, 2010.

B. Fleischmann and H. Meyr. ``The general lotsizing and scheduling problem''. Operations-Research-Spektrum, v. 19, n. 1, p. 11-21, 1997.

C. H. Glock, E. H. Grosse, and J. M. Ries. ``The lot sizing problem: A Tertiary study''. International Journal of Production Economics, 155: 39-51, 2014.

L. Guimaraes, D. Klabjan, and B. Almada-Lobo. ``Pricing, relaxing and fixing under lot sizing and scheduling''. European Journal of Operational Research, 230.2: 399-411, 2013.

L. Guimarães, D. Klabjan, and B. Almada-Lobo. ``Modeling lotsizing and scheduling problems with sequence dependent setups''. European Journal of Operational Research, v. 239, n. 3, p. 644-662, 2014.

K. Haase. ``Capacitated lot-sizing with sequence dependent setup costs''. Operations-Research-Spektrum, 18.1: 51-59, 1996.

R. J. W. James and B. Almada-Lobo. ``Single and parallel machine capacitated lotsizing and scheduling: New iterative MIP-based neighborhood search heuristics''. Computers & Operations Research, 38.12: 1816-1825, 2011.

G. M. Kopanos, L. Puigjaner and C. T. Maravelias. ``Production planning and scheduling of parallel continuous processes with product families''. Industrial & engineering chemistry research, 50.3: 1369-1378, 2010.

H. Meyr. ``Simultaneous lotsizing and scheduling by combining local search with dual reoptimization''. European Journal of Operational Research, v. 120, n. 2, p. 311-326, 2000.

H. Meyr. ``Simultaneous lotsizing and scheduling on parallel machines''. European Journal of Operational Research, v. 139, n. 2, p. 277-292, 2002.

H. Meyr and M. Mann. ``A decomposition approach for the General Lotsizing and Scheduling Problem for Parallel production Lines''. European Journal of Operational Research, v. 229, n. 3, p. 718-731, 2013.

W. Wei, et al. ``Tactical production and distribution planning with dependency issues on the production process''. Omega, 2016.

L. A. Wolsey. ``MIP modelling of changeovers in production planning and scheduling problems''. European Journal of Operational Research, v. 99, n. 1, p. 154-165, 1997.

J. Xiao, et al. ``A hybrid Lagrangian-simulated annealing-based heuristic for the parallel-machine capacitated lot-sizing and scheduling problem with sequence-dependent setup times''. Computers & Operations Research, 63: 72-82, 2015.

S. Çgri and B. Bilgen. ``Hybrid simulation and MIP based heuristic algorithm for the production and distribution planning in the soft drink industry''. Journal of Manufacturing Systems, 33.3: 385-399, 2014.




DOI: https://doi.org/10.5540/tema.2017.018.03.515

Article Metrics

Metrics Loading ...

Metrics powered by PLOS ALM

Refbacks

  • There are currently no refbacks.


Trends in Computational and Applied Mathematics

A publication of the Brazilian Society of Applied and Computational Mathematics (SBMAC)

 

Indexed in:

                       

         

 

Desenvolvido por:

Logomarca da Lepidus Tecnologia