Sequenciamento de tarefas com tempos de Setup via Branch and Bound

Authors

  • Edilson de Jesus Universidade Federal de Sergipe
  • Maria Teresa Moreia Rodrigues Unicamp Departamento de Engenharia Química

DOI:

https://doi.org/10.7198/geintec.v4i3.357

Abstract

Este trabalho propõe limitante inferior a ser utilizado no procedimento de busca em árvore para a solução de sequenciamento de produção com tempos de setup em ambiente flowshop visando minimizar o tempo total de execução das tarefas. O problema de sequenciamento consiste em definir a melhor sequência, segundo critério de otimalidade predeterminado, em que N tarefas devem ser desenvolvidas em M máquinas. Neste trabalho, é proposta uma formulação para o cálculo do limitante inferior a ser utilizado na busca em árvore branch and bound para resolver o problema de sequenciamento de tarefas considerando N tarefas e M máquinas, envolvendo tempos de setup. O algoritmo de busca em árvore branch and bound foi implementado em Pascal. As relações de recorrências propostas levaram a obtenção da sequência mínima. Neste trabalho foi detalhado para 4 tarefas e 2 máquinas.

Author Biographies

Edilson de Jesus, Universidade Federal de Sergipe

Departamento de Engenharia Química

Área Planejamento e Processos Químicos

Maria Teresa Moreia Rodrigues, Unicamp Departamento de Engenharia Química

Planejamento de produção

Scheduling

Logística

Controle

References

ALI ALLAHVERDI, C.T. NG B.; CHENG, T.C.E.; KOVALYOV, MIKHAIL Y. A survey of scheduling problems with setup times or costs. European Journal of Operational Research, vol. 187, 2008. p. 985-1032.

BALAS, E. The prize collecting traveling salesman problem. Networks, vol. 19, 1989. p. 621- 636.

Baker, K. R., Introduction to Sequencing and Scheduling. John Wiley, 1974.

CHAVES, A. A.; BIAJOLI, F. L.; MINE, O. M.; SOUZA, M. J. F. A. Metaheurísticas híbridas para resolução do problema do caixeiro viajante com coleta de prêmios. Produção, vol. 17 (2), p. 263-272.

CHEN, W. J. Scheduling with dependent setups and maintenance in a textile company. Computers & Industrial Engineering, vol. 57, 2009. p. 867–873.

GOMES, L.; DINIZ, V.; MARTINHON, C. A. An Hybrid GRASP+VND Metaheuristic for the Prize-Collecting Traveling Salesman Problem. In: XXXII Simpósio Brasileiro de Pesquisa Operacional, 2000. p. 1657-1665.

HEJAZI, S.R.; SAGHAFIAN, S. Flowshop-scheduling problems with makespan criterion: a review. International Journal of Production Research, vol. 43, 2005. p. 2895-2929.

KU, H.; RAJAGOPALAN, D.; KARIMI, I. Scheduling in Batch Process. Chemical Engineering Progress, vol. 83 (8), 1987. p. 35-45.

LEE, Wen-Chiung.; LIN, Jian-Bang.; SHIAU, Yau-Ren. Deteriorating job scheduling to minimize the number of late jobs with setup times. Computers & Industrial Engineering, vol. 61, 2011. p. 782-787.

MELO, V. A. Metaheurísticas para o Problema do Caixeiro Viajante com Coleta de Prêmios. Dissertação de Mestrado, Instituto de Computação, Universidade Federal Fluminense, Niterói. (2001).

MOCCELLIN, J. V.; NAGANO, M. S. Uma propriedade estrutural do problema de programação da produção flow shop permutacional com tempos de setup. Pesquisa Operacional, vol. 27(3), 2007. p. 487-515.

NILSON, N. J. Problem-solving methods in artificial intetelligence. McGraw-Hill Back Company. 1971.

REKLAITIS, G. V. Review of scheduling of Processs operations. AIche Symposium Series. 1982. p. 119.

RIOS-MERCADO, R.Z.; BARD, J.F. Heuristics for the flow line problem with setup costs. European Journal of Operational Research, vol. 110, 1998. p. 76-98.

RODRIGUES, M.T.M.; LATRE, G. Sequenciamento e Alocação de Operações em Flow-Shop na Indústria Química com Restrições sobre os Recursos Compartilhados: Uma Abordagem de Busca Orientada por Restrições. Tese de Doutorado, UNICAMP. 1992.

RONCONI, D. P.; KAWAMURA, M. S. The single machine earliness and tardiness scheduling problem: lower bounds and a branch-and-bound algorithm. Computational & Applied Mathematics. vol. 29, 2010. p. 107-124.

SOLIMANPUR, M.; ELMI, A. A tabu search approach for cell scheduling problem with makespan criterion. International Journal of Production Economics, vol.141(2), 2013, pp.639-645.

SANTOS, E. J.; PEREIRA, J. A. Análise de Tempos de Estabelecimento e Ordem de Manufatura no Sequenciamento de Tarefas em Processos Batelada. Dissertação de Mestrado, UNICAMP, Abril. 1994.

SIMONS Jr., J.V. Heuristics in flow shop scheduling with sequence dependent setup times. Omega, 20, 1986. p. 215-225.

SRIKAR, B. N.; GHOSH, S. A. MILP model for the n-job, m-stage flowshop, with sequence dependent setup times. International Journal of Production Research, 24, 1986, p. 1459-1472.

STAFFORD, E.F.; TSENG, F.T. On the Srikar-Ghosh MILP model for the N X M SDST flowshop problem. International Journal of Production Research, 28, 1990. p. 1817-1830.

USKUP, E.; SMITH, S. B. A branch-and-bound algorithm for two-stage production-sequencing problem. Operations Research, 23, 1975. p. 118-136.

WANG, X.; XIE, X.; CHENG, T.C.E. Order acceptance and scheduling in a two-machine flowshop. International Journal of Production Economics, vol. 141(1), 2013, pp.366-376.

Published

2014-09-28

Issue

Section

Artigos (Ativos de 2011 até 2014)