Use este identificador para citar ou linkar para este item: https://locus.ufv.br//handle/123456789/2603
Tipo: Dissertação
Título: Metaheurísticas para o problema de programação de tarefas em máquinas paralelas com tempos de preparação dependentes da sequência e de recursos
Título(s) alternativo(s): Metaheuristics for the parallel machines scheduling problem with resource-assignable sequence dependent setup times
Autor(es): Kampke, Edmar Hell
Primeiro Orientador: Arroyo, José Elias Cláudio
Primeiro coorientador: Santos, André Gustavo dos
Segundo coorientador: Rocha, Mauro Nacif
Primeiro avaliador: Santos, Heleno do Nascimento
Segundo avaliador: Souza, Marcone Jamilson Freitas
Abstract: Os problemas de programação de tarefas em máquinas paralelas são importantes na área de otimização combinatória, pois quase sempre envolvem problemas rotineiros em indústrias de pequeno e grande porte. Este trabalho aborda o problema de sequenciamento de tarefas em máquinas paralelas, com tempos de preparação das máquinas dependentes da sequência e do número de recursos utilizados. A característica deste problema é que o tempo de preparação não é determinado apenas pela máquina e pela sequência das tarefas, mas também pela quantidade de recursos associados, que varia entre um valor mínimo e um máximo. Dada a complexidade combinatória do problema, inicialmente propõe-se um algoritmo baseado na metaheurística GRASP, no qual o parâmetro de aleatoriedade utilizado na fase de construção é auto-ajustado de acordo com as soluções previamente encontradas (GRASP Reativo). Em seguida, propõe-se um algoritmo baseado na metaheurística Iterated Local Search (ILS). Esta metaheurística foi proposta recentemente na literatura e está sendo aplicada satisfatoriamente em diversos problemas de otimização combinatória. Em ambos os algoritmos, é utilizada a estratégia de intensificação baseada na técnica de Reconexão de Caminhos, que explora trajetórias que conectam soluções de alta qualidade encontradas pelos algoritmos. Os resultados obtidos pelos algoritmos propostos são comparados entre si e com os melhores resultados disponibilizados na literatura. A análise e a discussão dos resultados mostram que as metaheurísticas aplicadas, apresentaram resultados satisfatórios, sendo possível melhorar, em média, 9,14%, os resultados da literatura, o que comprova a viabilidade do uso destes algoritmos na resolução de problemas práticos existentes nas indústrias.
The problems of scheduling jobs on parallel machines are important problems of combinatorial optimization. They involve routine problems in industries of small and large. This work addresses an unrelated parallel machine problem with machine and job sequence dependent setup times. The characteristic of this problem is that the amount of setup times do not only depend on the machine and job sequence, but also on a number of resources assigned, which can vary between a minimum and a maximum. Due to the combinatorial complexity of this problem, initially we propose an algorithm based on the GRASP metaheuristic, in which the basic parameter that defines the restrictiveness of the candidate list during the construction phase is self-adjusted according to the quality of the solutions previously found (reactive GRASP). Then, we propose an algorithm based on the Iterated Local Search (ILS) metaheuristic. This metaheuristic was proposed recently in the literature and is being applied successfully to several combinatorial optimization problems. In both algorithms, an intensification strategy based on the path relinking technique is used. This consists in exploring paths between elite solutions found by the algorithms. The results obtained by the proposed algorithms are compared with each other and with the best results available in literature. The analysis and discussion of results obtained with the algorithms, leads us to conclude that the metaheuristics show good performance, it is possible to improve, on average, 9,14% the results of the literature, which demonstrates the feasibility of using these algorithms to solve real problems existing in industries.
Palavras-chave: Otimização combinatória
Heurísticas
Metaheurísticas
Programação de tarefas
Máquinas paralelas
Combinatorial optimization
Heuristics
Metaheuristics
Task scheduling
Parallel machines
CNPq: CNPQ::CIENCIAS EXATAS E DA TERRA::CIENCIA DA COMPUTACAO
Idioma: por
País: BR
Editor: Universidade Federal de Viçosa
Sigla da Instituição: UFV
Departamento: Metodologias e técnicas da Computação; Sistemas de Computação
Programa: Mestrado em Ciência da Computação
Citação: KAMPKE, Edmar Hell. Metaheuristics for the parallel machines scheduling problem with resource-assignable sequence dependent setup times. 2010. 112 f. Dissertação (Mestrado em Metodologias e técnicas da Computação; Sistemas de Computação) - Universidade Federal de Viçosa, Viçosa, 2010.
Tipo de Acesso: Acesso Aberto
URI: http://locus.ufv.br/handle/123456789/2603
Data do documento: 9-Mar-2010
Aparece nas coleções:Ciência da Computação

Arquivos associados a este item:
Arquivo Descrição TamanhoFormato 
texto completo.pdf1,04 MBAdobe PDFThumbnail
Visualizar/Abrir


Os itens no repositório estão protegidos por copyright, com todos os direitos reservados, salvo quando é indicado o contrário.