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

Autores

  • Willy Alves de Oliveira Instituto de Matemática - INMA/Universidade Federal de Mato Grosso do Sul - UFMS Instituto de Ciências Matemáticas e de Computação - ICMC/Universidade de São Paulo - USP
  • Maristela Oliveira dos Santos Instituto de Ciências Matemáticas e de Computação - ICMC/USP

DOI:

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

Palavras-chave:

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

Resumo

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.

Referências

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.

Downloads

Arquivos adicionais

Publicado

2018-01-10

Como Citar

de Oliveira, W. A., & Santos, M. O. dos. (2018). A New Branching Rule to Solve the Capacitated Lot Sizing and Scheduling Problem with Sequence Dependent Setups. Trends in Computational and Applied Mathematics, 18(3), 515. https://doi.org/10.5540/tema.2017.018.03.515

Edição

Seção

Artigo Original