Uma proposta de heurísticas e meta-heurísticas aplicadas ao problema de flow shop scheduling / A proposal of heuristics and metaheuristics for solving the flow shop scheduling problem

Authors

  • Diego Moah Lobato Tavares
  • Leonardo dos Santos Lourenço Bastos
  • Kamila Almeida dos Reis

DOI:

https://doi.org/10.34117/bjdv6n6-390

Keywords:

Programação da produção, Sequenciamento de Tarefas, Flow Shop, Meta-heurísticas.

Abstract

Este trabalho trata do problema de Flow Shop Scheduling Problem (PFSP), onde um conjunto de tarefas devem ser sequenciadas numa quantidade de máquinas, objetivando a minimização do Total Completion Time (TCT) do processo. A proposta é, portanto, solucionar o problema através da aplicação das meta- heurísticas Variable Neighborhood Descent (VND) e Iterated Local Search (ILS). Para a construção da solução inicial, utilizou-se um algoritmo aleatorizado e o NEH, proposto por (Newaz Enscore e Ham 1983), e as buscas locais foram incorporadas nas meta-heurísticas para refinamento de resultados. Os métodos foram aplicados ao conjunto de instâncias proposto por (Taillard 1993) e tiveram seus respectivos desempenhos comparados às melhores soluções conhecidas na literatura a fim de conferir sua eficácia. Verificou-se, então, que o método NEH garante uma solução inicial de alta qualidade e, associado ao ILS, gera melhores resultados finais com tempo computacional razoável.

 

References

AGARVAL A, COLAK S, ERYARSOY E. Improvement heuristic for the flow-shop scheduling problem: an adaptive-learning approach. European Journal of Operational Research, 169:801–15, 2006.

ARENALES M, ARMENTANO V. A, MORABITO, R. YANASSE H. H. Pesquisa Operacional para cursos de engenharia, 2° ed. Elsevier, 2015.

Dannenbring, D.G. An Evaluation of flow-shop sequencing heuristics. Management Science, Providence, v.23, n.11, p.1174-1182, 1977.

FERNANDEZ-VIAGAS, V., FRAMINAN J. M. A new set of high-performing heuristics to minimize flowtime in permutation Flow Shops. Copmuters & Operations Research, 53:68-90, 2015.

FRAMINAN, J.M., GUPTA J.N.D, LEISTEN R. A. Review and classification of heuristics for permutation flow-shop scheduling with makespan objective. Journal of the Operational Research Society, 55:1243–55, 2004.

FUCHIGAMI, H. Y. E RANGEL, S. Métodos heurísticos para maximização do número de tarefas just-in-time em Flow Shop permutacional, Em: Simpósio Brasileiro de Pesquisa Operacional, Porto de Galinas, Brasil, 25-28 de Agosto de 2015.

GAREY, M. R., JOHNSON, D. S., SETHI, R. The Complexity of Flow Shop and Jobshop Scheduling. Mathematics of Operations Research, 1, 117-129, 1976.

GLOVER, F.; KOCHENBERG, G. A. Handbook of Metaheuristics. International Series. Operations Research & Management Series, Kluwer's International Series, Stanford University, 2003.

GLOVER, F. Future Paths for Integer Programming and Links to Artificial Intelligence, Computers and Operations Research, Vol. 13, pp. 533-549, 1986.

GRABOWSKI J., WODECKI M. A very fast tabu search algorithm for the permutation Flow Shop problem with makespan criterion. Computers & Operations Research, 31:1891–1909, 2004.

GUPTA J. N. D., KOULAMAS, C., KYPARISIS G. J. Perfomance guarantees for Flow Shop heuristics to minimize makespan. European Journal of Operational Research, 169:865–72, 2006.

HAOUARI M., LADHARI T. A branch-and-bound-based local search method for the Flow Shop problem. Journal of the Operational Research Society, 54:1076–84, 2003.

KALCZYNSKI P. J., KAMBUROWSKI J. An improved NEH heuristic to minimize makespan in permutation Flow Shops. The International Journal of Management Science, 35(1):53–60, 2008.

LADHARI T, HAOUARI M. A. computational study of the permutation Flow Shop problem based on a tight lower bound. Computers & Operations Research, 32:1831–47, 2005.

LUGO, P. L. M, TEIXEIRA R. F., MARTÍNEZ K. P. Um modelo de programação inteira mista para a programação da Produção em Flow Shop híbrido com buffers limitados. Em: Simpósio Brasileiro de Pesquisa Operacional, Natal, Brasil, 16-19 de Setembro de 2013.

MIYATA, H. H. Métodos heurísticos para minimização da duração total da programação em ambiente no-wait Flow Shop com políticas de manutenção preventiva. 191 f. Dissertação (Mestrado)- Programa de Pós-Graduação em Engenharia de Produção Escola de Engenharia de São Carlos da Universidade de São Paulo, 2015.

MLADENOVIC, N., HANSEN, P. Variable neighborhood Descent. Computers and Operations Research, v. 24, n. 11, p. 1097–1100, 1977.

NAWAZ M., ENSCORE, J. R. E., HAM I. A heuristic algorithm for the m-machine n-job flow-shop sequencing problem. Omega. The International Journal of Management Science, 11:91–95, 1983.

NOWICKI E, SMUTNICKI C. A fast tabu search algorithm for the permutation flow-shop problem. European Journal of Operational Research, 91:160–75, 1996.

PARK Y. B., PEGDEN C. D. Enscore E.E.A survey and evaluation of static Flow Shop scheduling heuristics. International Journal of Production Research, 22:127–41, 1984.

PEREIRA, A. A. S. Metaheurísticas para o problema de Flow Shop flexível com penalidades de adiantamento e atraso 70f. Dissertação (mestrado) Programa de Pós-Graduação em Ciência da Computação Universidade Federal de Viçosa, 2011.

PINEDO, M. Scheduling: theory, algorithms, and systems. 2 ed. New Jersey: Prentic-Hall, 1995.

RAJENDRAN C., ZIEGLER H. Ant-colony algorithms for permutation Flow Shop scheduling to minimize makespan/total flowtime of jobs. European Journal of Operational Research, 155:426–38, 2004.

Reeves C. R. Genetic algorithm for Flow Shop sequencing. Computers & Operations Research, 15:5–23, 1995.

REIS J. V. A. Meta-heurísticas baseadas em busca em vizinhança variável aplicadas a problemas de operação de transportes. 221f. Tese (Doutorado) Escola Politécnica da Universidade de São Paulo em Engenharia de Transportes, 2013.

REZA HEJAZI S., SAGHAFIAN S. Flow Shop-scheduling with makespan criterion: a review. International Journal of Production Research, 43: 895–929, 2005.

RINNOOY KAN, A. H. G. Machine Scheduling Problems: Classification, Complexity, and Computations. The Hahue: Nijhoff., 1976.

ROSSI, F. L. NAGANO M. S., TAVARES R. F. N. Evaluation of high performance constructive heuristics for the Flow Shop with makespan minimization. The International Journal of Advanced Manufacturing Technology, 2016.

RUIZ R, MAROTO C. A. comprehensive review and evaluation of permutation Flow Shop heuristics. European Journal of Operational Research, 165:479–94, 2005.

RUIZ R., MAROTO C., ALCARAZ J. Two new robust genetic algorithms for the Flow Shop scheduling problem. Omega. The International Journal of Management Science, 34:461–76, 2006.

SOLIMANPOUR M., VRAT P., SHANKAR R. A neuro-tabu search heuristic for the Flow Shop scheduling problem. Computers & Operations Research, 31:2151–2164, 2004.

STÜTZLE T. Applying iterated local search to the Flow Shop problem. Applying iterated local search to the Flow Shop problem. Technical Report, AIDA-98-04, Computer Science Department, Intelictics Group, Darmstadt, Germany. Darmstadt University of Technology, 1988.

TAILLARD E. Some efficient heuristic methods for the Flow Shop sequencing problem. European Journal of Operational Research, 47:65–74, 1990.

TAILLARD E. Benchmark for Basic Scheduling Problems. European Journal of Operational Research, 64(2):278-285, 1993.

TURNER S, BOOTH D. Comparison of heuristics for Flow Shop sequencing. Omega. The International Journal of Management Science, 15:75–85, 1897.

WATSON J. P, BARBULESCU L, WHITLEY L.D, HOWE A. E. Contrasting structured and random permutation flow-shop scheduling problems: search-space topology and algorithm performance. INFORMS Journal on Computing. 14: 98–123, 2002.

YAHYAOUI, H., KRICHEN, S., DERBEL, B., TALBI, E-G. A hybrid ILS-VND based hyper-heuristic for permutation Flow Shop scheduling problem. Knowledge-Based and Intelligent Information & Engineering Systems. 60: 632-641, 2015

Published

2020-06-17

How to Cite

Tavares, D. M. L., Bastos, L. dos S. L., & Reis, K. A. dos. (2020). Uma proposta de heurísticas e meta-heurísticas aplicadas ao problema de flow shop scheduling / A proposal of heuristics and metaheuristics for solving the flow shop scheduling problem. Brazilian Journal of Development, 6(6), 38266–38282. https://doi.org/10.34117/bjdv6n6-390

Issue

Section

Original Papers