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
Política para Periódicos de Acesso Livre
Autores que publicam nesta revista concordam com os seguintes termos:
- Autores mantém os direitos autorais e concedem à revista o direito de primeira publicação, com o trabalho simultaneamente licenciado sob a Licença Creative Commons Attribution que permite o compartilhamento do trabalho com reconhecimento da autoria e publicação inicial nesta revista.
- Autores têm autorização para assumir contratos adicionais separadamente, para distribuição não-exclusiva da versão do trabalho publicada nesta revista (ex.: publicar em repositório institucional ou como capítulo de livro), com reconhecimento de autoria e publicação inicial nesta revista.
- Autores têm permissão e são estimulados a publicar e distribuir seu trabalho online (ex.: em repositórios institucionais ou na sua página pessoal) a qualquer ponto antes ou durante o processo editorial, já que isso pode gerar alterações produtivas, bem como aumentar o impacto e a citação do trabalho publicado (Veja O Efeito do Acesso Livre).
- Esta é uma revista de acesso aberto, o que significa que todo o conteúdo é livremente disponível gratuitamente para o usuário ou sua instituição. Os usuários estão autorizados a ler, baixar, copiar, distribuir, imprimir, pesquisar ou vincular os textos completos dos artigos, ou usá-los para qualquer outro propósito legal, sem pedir permissão prévia do editor ou do autor. Isso está de acordo com a definição de acesso aberto do BOAI.
Todo o conteúdo do periódico está licenciado sob uma Licença Creative Commons do tipo atribuição BY.