Please use this identifier to cite or link to this item:
https://repositorio.ufu.br/handle/123456789/39416
ORCID: | http://orcid.org/0009-0007-1585-9554 |
Document type: | Trabalho de Conclusão de Curso |
Access type: | Acesso Aberto |
Title: | Um estudo sobre a aplicação de heurísticas no problema de job shop |
Alternate title (s): | A study about the application of heuristics in the job shop problem |
Author: | França, Adriel Henrique Beato de |
First Advisor: | Reis, Jorge von Atzingen dos |
First member of the Committee: | Costa, Eugênio Pacceli |
Second member of the Committee: | Rosa, Vanessa Aparecida de Oliveira |
Summary: | O Problema de Job Shop é classificado como um problema NP-hard, ou seja, não existe um algoritmo que encontre a solução ideal em tempo polinomial. Dessa forma a resolução do problema de sequenciamento de tarefas tem fundamental importância na gestão estratégica que afeta diretamente todas as diretrizes de uma companhia, além de se enquadrar nos problemas clássicos dentro do planejamento e controle da produção. O presente trabalho aborda um estudo onde é necessário desenvolver e implementar um modelo matemático capaz de determinar o sequenciamento ótimo da produção, o qual retornará a solução ótima referente a melhor combinação e proporção de produção e fornecimento de determinados produtos ou serviços, porém demanda um tempo elevado para retornar tal solução. O estudo é baseado na formulação do modelo matemático, a utilização de técnicas de otimização para resolução do modelo e análise dos resultados obtidos, com intuito de buscar a maximização de lucros da operação logística, ou seja, buscar o preenchimento de certas lacunas no mercado. O presente trabalho consiste no comparativo de uma nova heurística construtiva e heurística de refinamento que vise a melhoria dos resultados obtidos pelas meta-heurísticas ILS e VNS para problemas de Job Shop implementados na linguagem de programação C++. Esta pesquisa teve início com a resolução do problema através da programação linear com o objetivo deste resultado servir de parâmetro para a qualidade da resposta obtida com as meta-heurísticas ILS e VNS. Posteriormente as meta-heurísticas ILS e VNS foram implementadas utilizando a heurística construtiva de Baker e Trietsch e esses resultados foram analisados junto com as respostas obtidas por programação linear. Foi possível concluir que os jobs com maior tempo total tinham prioridade de execução, resultando na proposição de um meio diferente de montar a heurística construtiva e para determinadas instâncias de maiores dimensões do problema utilizar uma heurística de refinamento. Esse método tem o objetivo de atingir uma resposta otimizada em um tempo menor de execução, de modo a auxiliar na tomada de decisão em um sequenciamento de trabalhos em máquinas. |
Abstract: | The Job Shop Problem is classified as an NP-hard problem, there is no algorithm that finds the ideal solution in polynomial time. The resolution of the task sequencing problem is fundamental in strategic management that directly affects all the guidelines of a company, in addition to fitting into the classic problems within production planning and control. The present work study where it is necessary to develop and implement a mathematical model capable of determining the optimal sequencing of production, which will return the optimal solution referring to the best combination and proportion of production and supply of certain products or services, but it takes time high to return such a solution. The study is based on the formulation of the mathematical model, the use of optimization techniques for solving the model and analysis of the results obtained, with the aim of seeking to maximize profits from the logistics operation, that is, to seek to fill certain gaps in the market. The present work compares a new constructive heuristic and a refinement heuristic that aims to improve the results obtained by the ILS and VNS meta-heuristics for Job Shop problems implemented in the C++ programming language. This research began with the resolution of the problem through linear programming with the objective of this result serving as a parameter for the quality of the response obtained with the meta-heuristics ILS and VNS. Subsequently, the ILS and VNS meta-heuristics were implemented using Baker and Trietsch's constructive heuristic and these results were analyzed together with the responses obtained by linear programming. It was possible to conclude that jobs with greater total time had execution priority, resulting in the proposition of a different way of setting up the constructive heuristic and for certain instances of larger dimensions of the problem to use a refinement heuristic. This method aims to achieve an optimized response in a shorter execution time, in order to assist in decision making in sequencing work on machines. |
Keywords: | Job Shop Programação Linear Otimização combinatória Heurística Job shop Linear programming Combinatorial optimization Heurístic |
Area (s) of CNPq: | CNPQ::ENGENHARIAS::ENGENHARIA DE PRODUCAO::PESQUISA OPERACIONAL |
Language: | por |
Country: | Brasil |
Publisher: | Universidade Federal de Uberlândia |
Quote: | FRANÇA, Adriel Henrique Beato de. Um estudo sobre a aplicação de heurísticas no problema de job shop. 2023. 122 f. Trabalho de Conclusão de Curso (Graduação em Engenharia de Produção) – Universidade Federal de Uberlândia, Ituiutaba, 2023. |
URI: | https://repositorio.ufu.br/handle/123456789/39416 |
Date of defense: | 21-Aug-2023 |
Appears in Collections: | TCC - Engenharia de Produção (Ituiutaba / Pontal) |
Files in This Item:
File | Description | Size | Format | |
---|---|---|---|---|
EstudoAplicacoesHeuristicas.pdf | TCC | 604.03 kB | Adobe PDF | View/Open |
This item is licensed under a Creative Commons License