Formulações monoestágio para o problema de programação da produção de bebidas dois estágios com sincronia
Mono-stage formulations for the soft drink production process with two synchronized stages
Ferreira, Deisemara; Almada-Lobo, Bernardo; Morabito, Reinaldo
http://dx.doi.org/10.1590/S0103-65132011005000068
Prod, vol.23, n1, p.107-119, 2013
Resumo
Neste trabalho, apresentamos formulações monoestágio para o problema integrado de dimensionamento e sequenciamento de lotes de produção de bebidas dois estágios com sincronia. O problema envolve múltiplos produtos, múltiplas máquinas e tempos e custos de troca dependentes da sequência de produção. As formulações monoestágio apresentadas não têm perda de generalidade para representar o problema e, em geral, reduzem as dimensões da formulação dois estágios com sincronia apresentadas em Ferreira, Morabito e Rangel (2009) em termos dos números de variáveis e restrições. Experimentos computacionais preliminares realizados com exemplares baseados em dados reais de uma fábrica de bebidas mostram que os modelos monoestágio propostos são competitivos, quando comparados com o modelo anterior dois estágios com sincronia.
Palavras-chave
Problemas integrados de dimensionamento e sequenciamento da produção. Programação da produção de bebidas. Programação inteira mista. Programação matemática.
Abstract
In this work we present single-stage formulations for the integrated soft drink lot-sizing and scheduling problem with two-stage synchronization. It is a multi-product, multi-machine problem, with sequence-dependent setup times and costs. Without loss of generality, these single-stage reformulations address the problem correctly and, in general, reduce the size of the synchronized two-stage model of Ferreira, Morabito e Rangel (2009), regarding the number of variables and constraints. The preliminary computational experiments on real-world instances from a soft-drink company show the competitiveness of the single-stage models against other formulations and solution approaches reported in the literature.
Keywords
Integrated lot-sizing and sequencing. Soft drink production scheduling. Mixed integer programming. Mathematical programming.
References
ALMADA-LOBO, B. et al. Multiple machine continuous setup lotsizing with sequence-dependent setups. Computational Optimization and Applications, v. 47, n. 3, p. 529-552, 2010. http://dx.doi.org/10.1007/s10589-009-9235-8
ALMADA-LOBO, B.; OLIVEIRA, J. F.; CARRAVILLA, M. A. Production planning and scheduling in the glass container industry: A VNS approach. International Journal of Production Economics, vol. 114, n. 1, p. 363-375, 2008. http://dx.doi.org/10.1016/j.ijpe.2007.02.052
ARAUJO, S. A.; ARENALES, M. N.; CLARK, A. R. Lot-sizing and furnace scheduling in small foundries. Computers and Operations Research, v. 35, p. 916-932, 2008. http://dx.doi.org/10.1016/j.cor.2006.05.010
BRAHIMI, N. et al. Single item lot sizing problems. European Journal of Operational Research, v. 168, p. 1-16, 2006. http://dx.doi.org/10.1016/j.ejor.2004.01.054
CASTRO, J. G.; PIZZOLATO, N. D. A programação de lotes econômicos de produção (ELSP) com tempos e custos de setup dependentes da sequência: um estudo de caso. Revista Gestão Industrial, v. 1, 70-80, 2005.
CHENG, T. C. E.; DING, Q.; LIN; B. M. T. A concise survey of scheduling with time-dependent processing time. European Journal of Operational Research, v. 152, p. 1-13, 2004. http://dx.doi.org/10.1016/S0377-2217(02)00909-8
CLARK, A. R. Hybrid heuristics for planning lot setups and sizes. Computers & Industrial Engineering, v. 45, p. 545-562, 2003. http://dx.doi.org/10.1016/S0360-8352(03)00073-1
CLARK, A. R.; CLARK, S. J. Rolling-horizon lot-sizing when set-up times are sequence-dependent. International Journal of Production Research, v. 38, p. 2287-2307, 2000. http://dx.doi.org/10.1080/00207540050028106
CLARK, A. R.; MORABITO, R.; TOSO, E. Production setup-sequencing and lot-sizing at an animal nutrition plant through ATSP subtour elimination and patching. Journal of Scheduling, v. 13, p. 111-121, 2010. http://dx.doi.org/10.1007/s10951-009-0135-7
DREXL, A.; KIMMS, A. Lot sizing and scheduling - survey and extensions. European Journal of Operational Research, v. 99, p. 221-235, 1997. http://dx.doi.org/10.1016/S0377-2217(97)00030-1
FERREIRA, D. Abordagens para o problema integrado de dimensionamento e sequenciamento de lotes da produção de bebidas. Tese (Doutorado)–Universidade Federal de São Carlos, 2006.
FERREIRA, D. et. al. Heuristics and metaheuristics for lot sizing and scheduling in the soft drinks industry: a comparison study, Studies in Computational Intelligence. Springer-Verlag Berlin Heidelberg, v. 128, p. 169-210, 2008.
FERREIRA, D.; MORABITO, R.; RANGEL, S. Um modelo de otimização inteira mista e heurísticas relax and fix para a programação da produção de fábricas de refrigerantes de pequeno porte. Produção, v. 18, n. 1, p. 76-88, 2008. http://dx.doi.org/10.1590/S0103-65132008000100006
FERREIRA, D.; MORABITO, R.; RANGEL, S. Solution approaches for the soft drink integrated production lot sizing and scheduling problem. European Journal of Operational Research, v. 196, n. 2, p. 697-706, 2009. http://dx.doi.org/10.1016/j.ejor.2008.03.035
FERREIRA, D.; MORABITO, R.; RANGEL, S. Relax and fix heuristics to solve one-stage one-machine lot-scheduling models for small-scale soft drink plants. Computers & Operations Research, v. 37, p. 684-691, 2010. http://dx.doi.org/10.1016/j.cor.2009.06.007
FLEISCHMANN, B.; MEYR, H. The general lotsizing and scheduling problem. OR Spektrum, v. 19, p. 11-21, 1997. http://dx.doi.org/10.1007/BF01539800
FOURER, R.; GAY, M. D.; KERNIGHAN, B. W. AMPL - a modeling language for mathematical programming. Danvers, Massachusetts: The Scientific Press, 1993.
FRANÇA, P. M; ARMENTANO, V. A.; TOLEDO, F. M. B. A network flow model for capacitated lot sizing problem. Omega-International Journal Of Management Science, v. 27, n. 2, p. 275-284, 1999. http://dx.doi.org/10.1016/S0305-0483(98)00045-0
ILOG. Using the CPLEX Callable Library. Copyright, ILOG, 2008.
KARIMI, B.; GHOMI, S. M. T. F.; WILSON, J. M. The capacitated lot sizing problem: a review of models and algorithms. Omega International Journal of Management Science, v. 31, n. 5, p. 365-378, 2003. http://dx.doi.org/10.1016/S0305-0483(03)00059-8
LUCHE, J. R.; MORABITO, R.; PUREZA, V. Combining process selection and lot sizing models for production scheduling of electrofused grains. Asia-Pacific Journal of Operational Research, v. 26, n. 3, p. 421-443, 2008. http://dx.doi.org/10.1142/S0217595909002286
MANNE, A. S. On the job-shop scheduling problem. Operations Research, v. 8, p. 219-223, 1960. http://dx.doi.org/10.1287/opre.8.2.219
PINEDO, M. Scheduling - theory, algorithms and systems. Prentice Hall, 1995.
RANGEL, S.; FERREIRA, D. Um modelo de dimensionamento de lotes para uma fábrica de refrigerantes. TEMA – Tendências em Matemática Aplicada e Computacional, v. 4, n. 2, p. 237-246, 2003.
SANTOS-MEZA, E.; SANTOS, M. O.; ARENALES, M. N. A lot-sizing problem in an automated foundry. European Journal of Operational Research, v. 139, p. 490-500, 2002. http://dx.doi.org/10.1016/S0377-2217(01)00196-5
TOLEDO, F. M. B.; ARMENTANO, V. A. A lagrangian-based heuristic for the capacitated lot-sizing problem in parallel machines. European Journal of Operational Research, v. 175, p. 1070-1083, 2006. http://dx.doi.org/10.1016/j.ejor.2005.06.029
TOLEDO, C. F. M. et al. Multi-population genetic algorithm to solve the synchronized and integrated two-level lot sizing and scheduling problem. International Journal of Production Research, v. 47, n. 11, p. 3097-3119, 2008. http://dx.doi.org/10.1080/00207540701675833
TOLEDO, C. F. M. et al. Um modelo de otimização para o problema integrado de dimensionamento de lotes e programação da produção em fábrica de refrigerantes. Pesquisa Operacional, v. 27, p. 155-186, 2007.
TOSO, E. V.; MORABITO, R.; CLARK, A. R. Lot sizing and sequencing optimization at an animal-feed plant. Computers & Industrial Engineering, v. 57, n. 3, p. 813-821, 2009. http://dx.doi.org/10.1016/j.cie.2009.02.011
WOLSEY, L. A. Valid inequalities for 0-1 knapsack and MIPs with generalized upper bound constraints. Discrete Applied Mathematics, v. 29, p. 251-261, 1990. http://dx.doi.org/10.1016/0166-218X(90)90148-6
ALMADA-LOBO, B.; OLIVEIRA, J. F.; CARRAVILLA, M. A. Production planning and scheduling in the glass container industry: A VNS approach. International Journal of Production Economics, vol. 114, n. 1, p. 363-375, 2008. http://dx.doi.org/10.1016/j.ijpe.2007.02.052
ARAUJO, S. A.; ARENALES, M. N.; CLARK, A. R. Lot-sizing and furnace scheduling in small foundries. Computers and Operations Research, v. 35, p. 916-932, 2008. http://dx.doi.org/10.1016/j.cor.2006.05.010
BRAHIMI, N. et al. Single item lot sizing problems. European Journal of Operational Research, v. 168, p. 1-16, 2006. http://dx.doi.org/10.1016/j.ejor.2004.01.054
CASTRO, J. G.; PIZZOLATO, N. D. A programação de lotes econômicos de produção (ELSP) com tempos e custos de setup dependentes da sequência: um estudo de caso. Revista Gestão Industrial, v. 1, 70-80, 2005.
CHENG, T. C. E.; DING, Q.; LIN; B. M. T. A concise survey of scheduling with time-dependent processing time. European Journal of Operational Research, v. 152, p. 1-13, 2004. http://dx.doi.org/10.1016/S0377-2217(02)00909-8
CLARK, A. R. Hybrid heuristics for planning lot setups and sizes. Computers & Industrial Engineering, v. 45, p. 545-562, 2003. http://dx.doi.org/10.1016/S0360-8352(03)00073-1
CLARK, A. R.; CLARK, S. J. Rolling-horizon lot-sizing when set-up times are sequence-dependent. International Journal of Production Research, v. 38, p. 2287-2307, 2000. http://dx.doi.org/10.1080/00207540050028106
CLARK, A. R.; MORABITO, R.; TOSO, E. Production setup-sequencing and lot-sizing at an animal nutrition plant through ATSP subtour elimination and patching. Journal of Scheduling, v. 13, p. 111-121, 2010. http://dx.doi.org/10.1007/s10951-009-0135-7
DREXL, A.; KIMMS, A. Lot sizing and scheduling - survey and extensions. European Journal of Operational Research, v. 99, p. 221-235, 1997. http://dx.doi.org/10.1016/S0377-2217(97)00030-1
FERREIRA, D. Abordagens para o problema integrado de dimensionamento e sequenciamento de lotes da produção de bebidas. Tese (Doutorado)–Universidade Federal de São Carlos, 2006.
FERREIRA, D. et. al. Heuristics and metaheuristics for lot sizing and scheduling in the soft drinks industry: a comparison study, Studies in Computational Intelligence. Springer-Verlag Berlin Heidelberg, v. 128, p. 169-210, 2008.
FERREIRA, D.; MORABITO, R.; RANGEL, S. Um modelo de otimização inteira mista e heurísticas relax and fix para a programação da produção de fábricas de refrigerantes de pequeno porte. Produção, v. 18, n. 1, p. 76-88, 2008. http://dx.doi.org/10.1590/S0103-65132008000100006
FERREIRA, D.; MORABITO, R.; RANGEL, S. Solution approaches for the soft drink integrated production lot sizing and scheduling problem. European Journal of Operational Research, v. 196, n. 2, p. 697-706, 2009. http://dx.doi.org/10.1016/j.ejor.2008.03.035
FERREIRA, D.; MORABITO, R.; RANGEL, S. Relax and fix heuristics to solve one-stage one-machine lot-scheduling models for small-scale soft drink plants. Computers & Operations Research, v. 37, p. 684-691, 2010. http://dx.doi.org/10.1016/j.cor.2009.06.007
FLEISCHMANN, B.; MEYR, H. The general lotsizing and scheduling problem. OR Spektrum, v. 19, p. 11-21, 1997. http://dx.doi.org/10.1007/BF01539800
FOURER, R.; GAY, M. D.; KERNIGHAN, B. W. AMPL - a modeling language for mathematical programming. Danvers, Massachusetts: The Scientific Press, 1993.
FRANÇA, P. M; ARMENTANO, V. A.; TOLEDO, F. M. B. A network flow model for capacitated lot sizing problem. Omega-International Journal Of Management Science, v. 27, n. 2, p. 275-284, 1999. http://dx.doi.org/10.1016/S0305-0483(98)00045-0
ILOG. Using the CPLEX Callable Library. Copyright, ILOG, 2008.
KARIMI, B.; GHOMI, S. M. T. F.; WILSON, J. M. The capacitated lot sizing problem: a review of models and algorithms. Omega International Journal of Management Science, v. 31, n. 5, p. 365-378, 2003. http://dx.doi.org/10.1016/S0305-0483(03)00059-8
LUCHE, J. R.; MORABITO, R.; PUREZA, V. Combining process selection and lot sizing models for production scheduling of electrofused grains. Asia-Pacific Journal of Operational Research, v. 26, n. 3, p. 421-443, 2008. http://dx.doi.org/10.1142/S0217595909002286
MANNE, A. S. On the job-shop scheduling problem. Operations Research, v. 8, p. 219-223, 1960. http://dx.doi.org/10.1287/opre.8.2.219
PINEDO, M. Scheduling - theory, algorithms and systems. Prentice Hall, 1995.
RANGEL, S.; FERREIRA, D. Um modelo de dimensionamento de lotes para uma fábrica de refrigerantes. TEMA – Tendências em Matemática Aplicada e Computacional, v. 4, n. 2, p. 237-246, 2003.
SANTOS-MEZA, E.; SANTOS, M. O.; ARENALES, M. N. A lot-sizing problem in an automated foundry. European Journal of Operational Research, v. 139, p. 490-500, 2002. http://dx.doi.org/10.1016/S0377-2217(01)00196-5
TOLEDO, F. M. B.; ARMENTANO, V. A. A lagrangian-based heuristic for the capacitated lot-sizing problem in parallel machines. European Journal of Operational Research, v. 175, p. 1070-1083, 2006. http://dx.doi.org/10.1016/j.ejor.2005.06.029
TOLEDO, C. F. M. et al. Multi-population genetic algorithm to solve the synchronized and integrated two-level lot sizing and scheduling problem. International Journal of Production Research, v. 47, n. 11, p. 3097-3119, 2008. http://dx.doi.org/10.1080/00207540701675833
TOLEDO, C. F. M. et al. Um modelo de otimização para o problema integrado de dimensionamento de lotes e programação da produção em fábrica de refrigerantes. Pesquisa Operacional, v. 27, p. 155-186, 2007.
TOSO, E. V.; MORABITO, R.; CLARK, A. R. Lot sizing and sequencing optimization at an animal-feed plant. Computers & Industrial Engineering, v. 57, n. 3, p. 813-821, 2009. http://dx.doi.org/10.1016/j.cie.2009.02.011
WOLSEY, L. A. Valid inequalities for 0-1 knapsack and MIPs with generalized upper bound constraints. Discrete Applied Mathematics, v. 29, p. 251-261, 1990. http://dx.doi.org/10.1016/0166-218X(90)90148-6
Facebook
Google+
Twitter
LinkedIn
Mendeley
StumbleUpon
CiteULike
Reddit
Email