Sequenciamento de tarefas com tempos de Setup via Branch and Bound

Edilson de Jesus, Maria Teresa Moreia Rodrigues

Resumo


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.


Texto completo:

PDF

Referências


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.




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

Apontamentos

  • Não há apontamentos.


Direitos autorais



__________________________________

ISSN: 2237-0722

A REVISTA GEINTEC possui D.O.I e está cadastrada nos sistemas:

Os trabalhos da Revista GEINTEC - Gestão, Inovação e Tecnologias de www.revistageintec.net está licenciado com uma Licença Creative Commons - Atribuição-NãoComercial 4.0 Internacional.

Licença Creative Commons

Associação Acadêmica de Propriedade Intelectual - Aracaju/SE. Universidade Federal de Sergipe. Cidade Universitária Prof. "José Aloísio de Campos" 

Av. Marechal Rondon, s/n Jardim Rosa Elze - Pólo de Pós-Graduação - Sala 8 - CEP 49100-000 - São Cristóvão/SE. [email protected]