Return to search

ALGORITMOS EVOLUTIVOS PARA O PROBLEMA DE SEQÜENCIAMENTO DE TAREFAS EM MÁQUINAS PARALELAS COM TEMPOS DE PREPARAÇÃO DEPENDENTES DA SEQÜÊNCIA / Evolutionary Algorithms for Parallel Machine Scheduling Problems with Sequence Dependent Setup Times

Coordenação de Aperfeiçoamento de Pessoal de Nível Superior / This work presents three evolutionary strategies to solve the problem of scheduling a given set of n jobs to m identical parallel machines with the objective of minimizing makespan. There is a sequence dependent setup times. We also compares our method with two other well succeeded heuristics, one is a tabu search based heuristic and the second is a memetic approach, which combines a population-based method with local search procedures. As benchmarks for smallsized instances, optimal values are used provide by a dichotomous search. For larger instances, the comparisons try to show the robust behavior in solution quality as well as in computational effort of our evolutionary strategy. / Este trabalho propõe três estratégias evolutivas para resolver o problema de seqüenciamento de n tarefas em m máquinas paralelas idênticas, buscando minimizar o tempo máximo de finalização (makespan). São considerados tempos de preparação dependentes da seqüência. Os métodos propostos são comparados com outras duas heurísticas de qualidade comprovada, uma baseada em Busca Tabu e outra baseada em Algoritmos Meméticos. Para algumas instâncias de pequeno porte, comparações são feitas com o valor ótimo obtido através de uma busca dicotômica. Para instâncias maiores, as comparações demonstram a robustez e a boa qualidade das soluções encontradas pelas estratégias evolutivas através da comparação com as outras heurísticas.

Identiferoai:union.ndltd.org:IBICT/oai:repositorio.ufsm.br:1/8017
Date11 October 2004
CreatorsKöhler, Viviane Cátia
ContributorsMüller, Felipe Martins, Lopes, Luis Felipe Dias
PublisherUniversidade Federal de Santa Maria, Programa de Pós-Graduação em Engenharia de Produção, UFSM, BR, Engenharia de Produção
Source SetsIBICT Brazilian ETDs
LanguagePortuguese
Detected LanguageEnglish
Typeinfo:eu-repo/semantics/publishedVersion, info:eu-repo/semantics/masterThesis
Formatapplication/pdf
Sourcereponame:Repositório Institucional da UFSM, instname:Universidade Federal de Santa Maria, instacron:UFSM
Rightsinfo:eu-repo/semantics/openAccess
Relation300800000005, 400, 500, 300, 500, 71f97871-5101-4fa8-b821-aa730e3775c4, dbce8696-c762-4771-a89d-252408400ca8, 52b4ac9b-ae50-4378-9e6d-d078971edcbc

Page generated in 0.0027 seconds