META-HEURÍSTICA MULTIOBJETIVO PARA SEQUENCIAMENTO DE MÁQUINAS PARALELAS NÃO RELACIONADAS COM TEMPOS DE PREPARAÇÃO DEPENDENTES DA SEQUÊNCIA

Júnior César Abreu, Ana Amélia de Souza Pereira

Resumo


Neste trabalho é abordado o problema multiobjetivo de sequenciamento em máquinas paralelas com tempos de preparação dependentes da sequência e da máquina para minimização do tempo de conclusão total e o lateness máximo. Problemas de sequenciamento são extensivamente investigados pela literatura tanto pelo aspecto teórico como pelo prático. Tendo aplicações práticas em várias áreas, principalmente na indústria. Problemas desta classe são frequentemente classificados como sendo NP-difícil, não podendo ser resolvidos em tempo polinomial. Para resolução deste problema será proposto uma adaptação à meta-heurística MOILS (Multiobjective Iterated Local Search) e ao ILSMulti (Multi-Objective Iterated Local Search), baseadas em busca local. A confiabilidade é verificada através de instância com resultados exatos e o desempenho é comparado com o NSGA-II (Non-dominated Sorting Genetic Algorithm II) através do Indicador de Hipervolume. Resultados indicam que as meta-heurísticas propostas ainda não superam o algoritmo da literatura.

Texto Completo:

PDF

Referências


AFZALIRAD, Mojtaba; REZAEIAN, Javad. A realistic variant of bi-objective unrelated parallel machine scheduling problem: NSGA-II and MOACO approaches. Applied Soft Computing, v. 50, p. 109-123, 2017.

ARENALES, M. et al. Otimização Discreta: Problemas de produção. In: _____ Pesquisa Operacional para cursos de Engenharia. Rio de Janeiro: Elsevier, 2007. p. 205–222.

ARROYO, J. E. C. Heurísticas e Metaheurísticas para Otimização Combinatória Multiobjetivo. 2002. 227 f. Tese (Doutorado) - Curso de Engenharia Elétrica, Unicamp, Campinas, 2002

ASSIS, L. P. de et al. Problema de Roteamento de Veículos Multiobjetivo com Coleta Seletiva. In: LOPES, Heitor Silvério; RODRIGUES, Luiz Carlos de Abreu; STEINER, Maria Teresinha Arns. Meta-Heurísticas em Pesquisa Operacional. Curitiba: Omnipax, 2013. Cap. 12. p. 181-202.

BARROS JUNIOR, Antônio Almeida de; ARROYO, Elias Claudio. Aplicações de Heurísticas em Problemas de Planejamento Florestal Multiobjetivo. 2010. 82 f. Dissertação (Mestrado) - Curso de Ciência da Computação, UFV, Viçosa, 2010.

BRUCKER, P. Scheduling Algorithms. 5. ed. Berlin Heidelberg: Springer-Verlag, 2007. 380 p.

CAMPOS, Saulo Cunha; ARROYO, José Elias C.; GONÇALVES, Luciana Brugiolo. Uma heuristica grasp-vnd para o problema de sequenciamento de tarefas num ambiente assembly flowshop com três estágios e tempos de setup dependentes da sequência. In: XLVSBPO, 45., 2013, Natal. Anais SBPO. Natal: SBPO, 2013.

CAMPOS, Saulo Cunha. Aplicação de Metaheurísticas para o Problema de Programação da Produção em um Ambiente Assembly Flowshop com Três Estágios e Tempos de Preparação Dependentes da Sequência. 2014. 140 f. Dissertação (Mestrado) - Curso de Ciência da Computação, UFV, Viçosa, 2014.

CHEN, Bo; POTTS, Chris N.; WOEGINGERP, Gerhard J. A Review of Machine Scheduling: Complexity, Algorithms and Approximability. In: DU, Ding-zhu; PARDALOS, Panos M. Handbook of Combinatorial Optimization. [s.l.]: Springer Us, 1998. p. 21-169

CHYU, Chiuh-Cheng; CHANG, Wei-Shung; LI, Ruei-Chi. Archived Simulated Annealing with Two-phase Matching Improvement for Unrelated Parallel Machine Scheduling to Minimize Fuzzy Makespan and Average Tardiness. In: Second International Conference on Engineering Optimization, Lisboa, Portugal, Setembro. 2010. p. 6-9.

COELLO, C. A C.; LAMONT, G. B.; VELDHUIZEN, D. A VAN. Evolutionary Algorithms for Solving Multi-Objective Problems. Boston, MA: Springer US, 2007.

COTA, Luciano Perdigão; SOUZA, Marcone Jamilson Freitas. Novos Algoritmos para o Problema de Sequenciamento em Máquinas Paralelas Não-Relacionadas com Tempos de Preparacãao Dependentes da Sequência. 2014. 134 f. Dissertação (Mestrado) - Curso de Ciência da Computação, UFOP, Ouro Preto, 2014.

DCOUTHO, Nixon; MORAGA, Reinaldo. Meta-RaPS for a Bi-objective Unrelated Parallel Machine Scheduling Problem. In: Heuristics, Metaheuristics and Approximate Methods in Planning and Scheduling. Springer International Publishing, 2016. p. 127-139.

DEB, K. et al. A fast and elitist multiobjective genetic algorithm: NSGA-II. IEEE Transactions on Evolutionary Computation, [s.l.], v. 6, n. 2, p.182-197, abr. 2002.

ETCHEVERRY, Guilherme Vazquez; ANZANELLO, Michel. Sequenciamento em máquinas paralelas com tempos de setup dependentes da sequência. In: XXXIII Encontro Nacional de Engenharia de Produção, 23., 2013, Salvador. Anais ENEGEP. Salvador: ABEPRO, 2013.

FONSECA, O. P.; ASSIS, L.; VIVAS, A. Abordagem Multiobjetivo para o Problema de Roteamento de Veículos Aberto. In: CLAIO-SBPO, 16., 2012, Rio de Janeiro. Annals XVI CLAIO - XLIV SBPO. Rio de Janeiro: SOBRAPO, 2012.

FRAMINAN, J. M.; LEISTEN, R. A multi-objective iterated greedy search for flowshop scheduling with makespan and flowtime criteria. [S.l.]: OR Spectrum, 2007.

GRIMME, C.; LEPPING, J.; SCHWIEGELSHOHN, U. Multi-criteria scheduling an agent-based approach for expert knowledge integration. Journal of Scheduling, [s.l.], v. 16, n. 4, p.369-383, 5 out. 2011.

HANSEN, P.; MLADENOVIC, N. and PÉREZ, J. A. M. Variable neighborhood search: methods and applications. Quartely journal of the Belgian, French and Italian operations research societies 6, 319-360. 2008.

LI, X. et al. A Multiobjective Optimization Approach to Solve a Parallel Machines Scheduling Problem. Advances in Artificial Intelligence, [s.l.], v. 2010, p.1-10, 2010. Hindawi Publishing Corporation.

LIN, Y. K.; FOWLER, J. W.; PFUND, M. E. Bi-Criteria Heuristic for Scheduling on Unrelated Parallel Machines. In: International Conference on Applied Operational Research - ICAOR, 2., 2010, Turku. Lecture Notes in Management Science (2010) 2. Turku: Icaor, 2010. p. 266 - 274.

LOURENÇO, H. R.; MARTIN, O. C.; STÜTZLE, T. Iterated Local Search. In: GLOVER, F.; KOCHENBERGER, G. A. Handbook of Metaheuristics. Dordrecht: Kluwer Academic Publishers, 2003. Cap. 11. p. 334-366.

NAWAZ, M.; ENSCORE JR., E.E.; HAM, I. A heuristic algorithm for the m-machine n-job flow-shop sequencing problem. Omega, v.11, n.1, p.91-95. 1983.

NOGUEIRA, João Paulo de C. M. et al. Hybrid GRASP Heuristics to Solve an Unrelated Parallel Machine Scheduling Problem with Earliness and Tardiness Penalties. Electronic Notes in Theoretical Computer Science, [s.l.], v. 302, p.53-72, fev. 2014.

PEREIRA, A. A. DE S. et al. Metaheurística para o problema de máquinas paralelas não-relacionadas com penalidades por adiantamentos e atrasos. In: XXXV Iberian Latin American Congress on Computational Methods in Engineering - CILAMCE, 35. Fortaleza. Proceedings of the XXXIV Iberian Latin-American Congress on Computational Methods in Engineering. Fortaleza: ABMEC, 2014.

PINEDO, M. L. Scheduling: Theory, Algorithms, and Systems. Boston, MA: Springer US, 2012. 694 p.

RIBEIRO, F. F. Um algoritmo genético adaptativo para a resolução do problema de sequenciamento em uma máquina com penalização por antecipação e atraso da produção. 2009. 123 f. Dissertação (Mestrado) - Curso de Modelagem Matemática e Computacional, CEFET-MG, Belo Horizonte, 2009.

RUIZ, Rubén; ŞERIFOĞLU, Funda Sivrikaya; URLINGS, Thijs. Modeling realistic hybrid flexible flowshop scheduling problems. Computers & Operations Research, vol. 35, n. 4, pp. 1151-1175. 2008.

SAFAEI, S.; NADERI, R.; SOHRABI, A. Scheduling of unrelated parallel machines using two multi objective genetic algorithm with sequence-dependent setup times and precedent constraints. Int J of Advanced Design and Manufacturing Technology, [s.l.], v. 2, n. 1, p.43-54, 2008.

SOUZA, M., COELHO, I., RIBAS, S., SANTOS, H. and MERSCHMANN, L. A hybrid heuristic algorithm for the open-pit-mining operational planning problem, European Journal of Operational Research 207(2), 1041-1051, 2010.

TAVAKKOLI-MOGHADDAM, R.; BAZZAZI, F.; TAHERI, M. Multi-objective unrelated parallel machines scheduling with Sequence-dependent setup times and precedence constraints. International Journal of Engineering, Transactions A: Basics, [s.l.], v. 21, n. 3, p. 269–278, set. 2008.

VALLADA, E.; RUIZ, R. A genetic algorithm for the unrelated parallel machine scheduling problem with sequence dependent setup times. European Journal of Operational Research, [s.l.], v. 211, n. 3, p.612-622, jun. 2011.

YENISEY, M. M.; YAGMAHAN, B. Multi-objective permutation flow shop scheduling problem: Literature review, classification and current trends. Omega, [s.l.], v. 45, p.119-135, jun. 2014.

ZITZLER, E.; THIELE, L. Multiobjective optimization using evolutionary algorithms: A comparative case study. Lecture Notes in Computer Science, [s.l.], p.292-301, 1998.


Apontamentos

  • Não há apontamentos.