Use este identificador para citar ou linkar para este item:
http://www.repositorio.ufop.br/jspui/handle/123456789/2390
Título: | Um algoritmo heurístico híbrido para minimizar os custos com a antecipação e o atraso da produção em ambientes com janelas de entrega e tempos de preparação dependentes da sequência. |
Autor(es): | Penna, Puca Huachi Vaz |
Orientador(es): | Souza, Marcone Jamilson Freitas |
Palavras-chave: | Busca Tabu Reconexão por caminhos Descida em vizinhança variável Sequenciamento em uma máquina Lavra |
Data do documento: | 2009 |
Editora / Evento / Instituição: | Programa de Pós-Graduação em Engenharia Mineral. Departamento de Engenharia de Minas, Escola de Minas, Universidade Federal de Ouro Preto. |
Referência: | PENNA, P. H. V. Um algoritmo heurístico híbrido para minimizar os custos com a antecipação e o atraso da produção em ambientes com janelas de entrega e tempos de preparação dependentes da sequência. 2009. 95 f. Dissertação (Mestrado em Engenharia Mineral) – Universidade Federal de Ouro Preto, Ouro Preto, 2009. |
Resumo: | Este trabalho de dissertação tem seu foco no problema de sequenciamento em uma máquina com penalidades por antecipação e atraso da produção. São considerados tempos de preparação da máquina dependentes da sequência de produção, bem como a existência de janelas de entrega distintas. Para resolução do problema, desenvolveu-se um algoritmo heurístico de três fases. A primeira fase baseada em GRASP e Descida em Vizinhança Variável para a geração da solução inicial, a segunda fase baseada em Busca Tabu para re namento da solução, e por m, a Reconexão por Caminhos como estratégia de pós-otimização, na terceira fase. Para cada sequência gerada pela heurística é utilizado um algoritmo de tempo polinomial para determinar a data ótima de início de processamento de cada tarefa. Os re- sultados computacionais mostraram que houve melhoria em relação a um algoritmo da literatura, tanto com relação à qualidade da solução nal quanto em relação ao desvio médio. |
Resumo em outra língua: | This work deals with the single machine scheduling problem with earliness and tar- diness penalties. Sequence dependent setup times and distinct due windows are con- sidered. To solve this problem, a three-phase heuristic approach was developed. The rst phase is based on GRASP and Variable Neighborhood Descent to generate an initial solution; the second phase is based on a Tabu Search for solution re ning, and nally Path Relinking is used as a mechanism of post-optimization as a third pha- se. For each job sequence generated by the heuristic, an optimal timing algorithm is used to determine the completion time for each job in the job sequence. Computatio- nal experiments carried out show that previous algorithms found in related literature have been improved, regarding the quality of the nal solution and the average gap. |
URI: | http://www.repositorio.ufop.br/handle/123456789/2390 |
Aparece nas coleções: | PPGEM - Mestrado (Dissertações) |
Arquivos associados a este item:
Arquivo | Descrição | Tamanho | Formato | |
---|---|---|---|---|
DISSERTAÇÃO_AlgoritmoHerísticoHíbrido.pdf | 1,11 MB | Adobe PDF | Visualizar/Abrir |
Os itens no repositório estão protegidos por copyright, com todos os direitos reservados, salvo quando é indicado o contrário.