Simpósio de Pesquisa Operacional e Logística da Marinha - Publicação Online

Agosto 2016, vol.2, num.1 - XVIII Simpósio de Pesquisa Operacional & Logística da Marinha
Artigo Completo - Open Access Idioma principal | Segundo principal

UMA ABORDAGEM BASEADA EM ITERATED LOCAL SEARCH PARA O PROBLEMA DE ESCALONAMENTO EM PROJETOS COM RESTRIÇÃO EM RECURSOS E MÚLTIPLOS MODOS DE EXECUÇÃO

UMA ABORDAGEM BASEADA EM ITERATED LOCAL SEARCH PARA O PROBLEMA DE ESCALONAMENTO EM PROJETOS COM RESTRIÇÃO EM RECURSOS E MÚLTIPLOS MODOS DE EXECUÇÃO

Fernandes, Gustavo Alves; Souza, Sérgio Ricardo de; França Filho, Moacir Felizardo de

Artigo Completo:

Nesse artigo, considera-se o Problema não Preemptivo de Escalonamento em Projetos com Restrição em Recursos e Múltiplos Modos de Execução para a minimização do makespan. Para solucionar esse problema, foi proposta a metaheurística Iterated Local Search (ILS). O método de Descida de Primeira Melhora é a busca local para o ILS, porém, essa busca é realizada em dois estágios, busca por modos de execução e, após, busca por atividade. Os resultados obtidos, para um grupo de instâncias entre 3 classes de problemas da PSPLIB, mostraram que a abordagem proposta foi capaz de encontrar boas soluções em tempo aceitável.

Nesse artigo, considera-se o Problema não Preemptivo de Escalonamento em Projetos com Restrição em Recursos e Múltiplos Modos de Execução para a minimização do makespan. Para solucionar esse problema, foi proposta a metaheurística Iterated Local Search (ILS). O método de Descida de Primeira Melhora é a busca local para o ILS, porém, essa busca é realizada em dois estágios, busca por modos de execução e, após, busca por atividade. Os resultados obtidos, para um grupo de instâncias entre 3 classes de problemas da PSPLIB, mostraram que a abordagem proposta foi capaz de encontrar boas soluções em tempo aceitável.

Download (PDF)

Palavras-chave:

DOI: 10.5151/marine-spolm2015-141100

Referências bibliográficas
  • [1] Andreas Drexl e Juergen Gruenewald. Nonpreemptive multi-mode resource-constrained project scheduling. IIE transactions, 25(5): 74–81, 1993.
  • [2] Antonio Lova, Pilar Tormos, Mariamar Cervantes, e Federico Barber. An efficient hybrid genetic algorithm for scheduling projects with resource constraints and multiple execution modes. International Journal of Production Economics, 117(2):302–316, 2009.
  • [3] Arno Sprecher, Sonke Hartmann, e Andreas Drexl. An exact algorithm for project scheduling with multiple modes. Operations-Research-Spektrum, 19(3):195–203, 1997.
  • [4] Arno Sprecher e Andreas Drexl. Multi-mode resource-constrained project scheduling by a simple, general and powerful sequencing algorithm. European Journal of Operational Research, 107(2):431–450, 1998.
  • [5] Asta Shahriar, Daniel Karapetyan, Ahmed Kheiri, Ender Özcan, e A. Parkes. Combining monte-carlo and hyper-heuristic methods for the multi-mode resource-constrained multi-project scheduling problem. In Proceedings of the 6th Multidisciplinary International Scheduling Conference, 836-839, 2013.
  • [6] Bassem Jarboui, Najeh Damak, Patrick Siarry, e A Rebai. A combinatorial particle swarm optimization for solving multi-mode resource-constrained project scheduling problems. Applied Mathematics and Computation, 195(1):299–308, 2008.
  • [7] Erik L Demeulemeester. Project scheduling: a research handbook, volume 102. Springer, 2002.
  • [8] Helena Lourenço, Martin Olivier, e Thomas Stützle. Iterated local search. In “Handbook of metaheuristics”, Ed. Fred Glover e Gary A Kochenberger. Springer Science & Business Media, 2003.
  • [9] Jacek Blazewicz. Scheduling under resource constraints: Deterministic models, volume 7. JC Baltzer, 1986.
  • [10] Javier Alcaraz, Concepcion Maroto, e Ruben Ruiz. Solving the multi-mode resource-constrained project scheduling problem with genetic algorithms. Journal of the Operational Research Society, 54(6):614–626, 2003.
  • [11] Joanna Jozefowska, Marek Mika, Rafal Rózycki, Grzegorz Waligóra, e Jan Weglarz. Simulated annealing for multi-mode resource-constrained project scheduling. Annals of Operations Research, 102(1-4):137–155, 2001.
  • [12] Klein Bouleimen e Housni Lecocq. A new efficient simulated annealing algorithm for the resource-constrained project scheduling problem and its multiple mode version. European Journal of Operational Research, 149(2):268–281, 2003.
  • [13] Najeh Damak, Bassem Jarboui, Patrick Siarry, e Taicir Loukil. Differential evolution for solving multi-mode resource-constrained project scheduling problems. Computers & Operations Research, 36(9):2653–2659, 2009.
  • [14] Peter Brucker, Andreas Drexl, Rolf Mohring, Klaus Neumann, e Erwin Pesch. Resource-constrained project scheduling: Notation, classification, models, and methods. European journal of operational research, 112(1):3–41, 1999.
  • [15] Rainer Kolisch e Andreas Drexl. Local search for nonpreemptive multi-mode resourceconstrained project scheduling. IIE transactions, 29(11): 987–999, 1997.
  • [16] Rainer Kolisch e Arno Sprecher. Psplib - a project scheduling problem library. European Journal of Operational Research, 96(1):205–216, 1997.
  • [17] Rainer Kolisch e Sonke Hartmann. Heuristic algorithms for the resource-constrained project scheduling problem: Classification and computational analysis. Springer, 1999.
  • [18] Rainer Kolisch e Sonke Hartmann. Experimental investigation of heuristics for resourceconstrained project scheduling: An update. European Journal of Operational Research, 174(1):23–37, 2006.
  • [19] Sonke Hartmann. Project scheduling with multiple modes: a genetic algorithm. Annals of Operations Research, 102(1-4):111–135, 2001.
  • [20] Sonke Hartmann e Rainer Kolisch. Experimental evaluation of state-of-the-art heuristics for the resource-constrained project scheduling problem. European Journal of Operational Research, 127(2):394–407, 2000.
  • [21] Tyson R Browning e Ali A Yassine. Resource-constrained multi-project scheduling: Priority rule performance revisited. International Journal of Production Economics, 126(2):212–228, 2010.
  • [22] Vijay S Bilolikar, Karuna Jain, e Mahesha Sharma. An annealed genetic algorithm for multi mode resource constrained project scheduling problem. International Journal of Computers and Applications, 60(1):36–42, 2012.
  • [23] Vincent Van Peteghem e Mario Vanhoucke. A genetic algorithm for the preemptive and nonpreemptive multi-mode resource-constrained project scheduling problem. European Journal of Operational Research, 201(2):409–418, 2010.
  • [24] Vincent Van Peteghem e Mario Vanhoucke. An experimental investigation of metaheuristics for the multi-mode resource-constrained project scheduling problem on new dataset instances. European Journal of Operational Research, 235(1):62–72, 2014.
Como citar:

Fernandes, Gustavo Alves; Souza, Sérgio Ricardo de; França Filho, Moacir Felizardo de; "UMA ABORDAGEM BASEADA EM ITERATED LOCAL SEARCH PARA O PROBLEMA DE ESCALONAMENTO EM PROJETOS COM RESTRIÇÃO EM RECURSOS E MÚLTIPLOS MODOS DE EXECUÇÃO", p-885-895. In: Anais do XVIII Simpósio de Pesquisa Operacinal & Logística da Marinha. São Paulo: Blucher, 2016.
ISSN 21756295, DOI 10.5151/marine-spolm2015-141100

últimos 30 dias

183
downloads

841
visualizações

765
indexações