A New Branching Rule to Solve the Capacitated Lot Sizing and Scheduling Problem with Sequence Dependent Setups
DOI:
https://doi.org/10.5540/tema.2017.018.03.515Palavras-chave:
Lot Sizing, Scheduling, Mixed Integer Linear Programming, Branch-and-Bound AlgorithmResumo
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
Publicado
Como Citar
Edição
Seção
Licença
Direitos Autorais
Autores de artigos publicados no periódico Trends in Computational and Applied Mathematics mantêm os direitos autorais de seus trabalhos. O periódico utiliza a Atribuição Creative Commons (CC-BY) nos artigos publicados. Os autores concedem ao periódico o direito de primeira publicação.
Propriedade Intelectual e Termos de uso
O conteúdo dos artigos é de responsabilidade exclusiva dos autores. O periódico utiliza a Atribuição Creative Commons (CC-BY) nos artigos publicados. Esta licença permite que os artigos publicados sejam reutilizados sem permissão para qualquer finalidade, desde que o trabalho original seja corretamente citado.
O periódico encoraja os Autores a autoarquivar seus manuscritos aceitos, publicando-os em blogs pessoais, repositórios institucionais e mídias sociais acadêmicas, bem como postando-os em suas mídias sociais pessoais, desde que seja incluída a citação completa à versão do website da revista.
