Use este identificador para citar o ir al link de este elemento: http://hdl.handle.net/1843/31901
Tipo: Dissertação
Título: Estudo de heurísticas matemáticas para o problema de escalonamento de máquina simples
Autor(es): Natália Antunes
primer Tutor: Eduardo Gontijo Carrano
primer miembro del tribunal : Ricardo Hiroshi Caldeira Takahashi
Segundo miembro del tribunal: Lucas de Souza Batista
Resumen: Este trabalho apresenta um estudo de heurísticas matemáticas para o problema de sequenciamento de tarefas em uma única máquina com data de entrega comum, onde o objetivo é minimizar penalidades decorrentes de atrasos e adiantamentos nas entregas das tarefas. O problema é NP-difícil, tendo sido tratado por diferentes heurísticas e metaheurísticas ao longo do tempo. A finalidade do trabalho é desenvolver um método que combine metaheurísticas e algoritmos exatos, as chamadas heurísticas matemáticas. No decorrer deste trabalho foram definidos e validados dois modelos matemáticos que representam o problema. Ao todo, cinco vizinhanças com métodos de programação matemática foram implementadas utilizando estratégias de fixação de variáveis forte e fraca. As vizinhanças com estratégia de fixação forte foram inspiradas no algoritmo Fix and Optimize (FixOpt) e no algoritmo Relaxation Induced Neighborhood Search (RINS) . A vizinhança com estratégia de fixação fraca implementada foi baseada no algoritmo Local Branching. Dentre as vizinhanças implementadas, a inspirada no algoritmo RINS foi a que apresentou os melhores resultados, sendo utilizada em conjunto com a metaheurísticas Variable Neighborhood Search (VNS) para obtenção dos resultados finais. Os testes computacionais foram realizados utilizando instâncias benchmark do problema e os resultados obtidos no trabalho foram comparados com diferentes resultados reportados na literatura. As principais contribuições deste trabalho foram o estudo dos modelos matemáticos e a proposição de vizinhanças exatas para o problema de sequenciamento de tarefas em máquina simples com data de entrega comum.
Abstract: This document presents a study of matheuristics for the common due date single machine scheduling problem, where the goal is to minimize earliness and tardiness penalties in the delivery of jobs. The problem is NP-hard, which justifies proposals of heuristics and metaheuristics for solving it over the years. The purpose of the work is to develop a method that combines metaheuristics and exact algorithms, the so-called matheuristics. In the course of this work, two mathematical models for the problem were validated. In all, five exact neighborhoods were implemented using hard fixing and soft fixing. The neighborhoods with hard fixing were inspired in Fix-and-Optimize (FixOpt) and Relaxation Induced Neighborhood Search (RINS). The neighborhood with soft fixing were inspired in Local Branching (LB). Among the implemented neighborhoods, the neighborhood inspired in RINS had the best results and it was combined with Variable Neighborhood Search (VNS) to obtain the final results. Computational tests were performed using benchmark instances of the problem and the results obtained in the work were compared with different results reported in the literature. The main contributions of this work were the study of mathematical models and the proposition of exact neighborhoods for the single machine common due date scheduling problem.
Asunto: Engenharia elétrica
Programação heurística
Modelos matemáticos
Idioma: por
País: Brasil
Editor: Universidade Federal de Minas Gerais
Sigla da Institución: UFMG
Departamento: ENG - DEPARTAMENTO DE ENGENHARIA ELÉTRICA
Curso: Programa de Pós-Graduação em Engenharia Elétrica
Tipo de acceso: Acesso Aberto
URI: http://hdl.handle.net/1843/31901
Fecha del documento: 6-dic-2019
Aparece en las colecciones:Dissertações de Mestrado

archivos asociados a este elemento:
archivo Descripción TamañoFormato 
Dissertacao_versaofinal.pdf891.89 kBAdobe PDFVisualizar/Abrir


Los elementos en el repositorio están protegidos por copyright, con todos los derechos reservados, salvo cuando es indicado lo contrario.