Please use this identifier to cite or link to this item: https://repositorio.ufu.br/handle/123456789/24078
Document type: Trabalho de Conclusão de Curso
Access type: Acesso Aberto
Title: Job Shop Problem – Estudo de um método heurístico para a sua otimização
Alternate title (s): Job Shop Problem – Study of a heuristic method for optimization
Author: Aguiar, Bruna Bernardes de
First Advisor: Reis, Jorge von Atzingen dos
First member of the Committee: Castillo, Lucio Abimael Medrano
Second member of the Committee: Penteado, Ricardo Batista
Summary: Este trabalho busca pesquisar e desenvolver um método de otimização para problemas de programação de ordem de produção onde cada produto tem sua sequência de ordem de produção, mais especificamente o problema Job Shop Problem (JSP), o mesmo é classificado como um problema NP-hard, ou seja, não há algoritmo que encontre a solução ideal em tempo polinomial. No Planejamento e Controle da Produção (PCP) quanto mais ágil a tomada de decisão mais rápida se tem uma resposta ao cliente, aumentando de certa forma sua competitividade perante o mercado, entretanto a determinação do sequenciamento é uma tarefa complexa devido às diversas restrições que necessitam ser consideradas. O presente trabalho tem como finalidade estudar o comportamento do modelo matemático adaptado da literatura, o qual retorna à solução ótima referente ao melhor sequenciamento de tarefas a ser implementado, porém demanda um tempo elevado para retornar tal solução. Visando diminuir esse tempo foram testados métodos alternativos dentro da Pesquisa Operacional (PO) para a resolução, desenvolvendo uma heurística construtiva e posteriormente uma meta-heurística a Variable Neighborhood Search (VNS), que visa criar conjuntos de soluções e combiná-las entre si para chegar a melhor possível com um menor esforço computacional, ou seja, um tempo menor de resposta. O VNS necessita ainda de uma solução inicial para ser trabalha, logo essa é a razão principal para o desenvolvimento de uma heurística construtiva, utilizar uma solução já viável para buscar uma otimizada, com um esforço computacional menor se comparado ao modelo matemático estudado. Os testes computacionais foram realizados com dados benchmark da literatura. Foi possível constatar que o objetivo proposto foi atingido sendo possível desenvolver uma metodologia para otimização da resolução do JSP, porém o mesmo necessita ser melhorado sendo sugerido para trabalhos futuros uma nova heurística e uma nova busca local.
Abstract: This work researching and developing one optimization method to programming problems of the production order where each product has your sequence of production order, more specific the Job Shop Problem (JSP), the same is rated as a NP-hard Problem, in other words, there are not any algorithm to found the best solution in the polynomial time. In the Planning and Production Control (PCP) as soon as possible to decision more fast the client has the answer, increasing the competition of the company in the your market, but to determine sequence of order production is a complex job because there are many restrictions need to be consider. This work has objective to study of the comportment adapted literature mathematic model, it which return the best solution of the best sequence of order production to implement, but using a long time to return the best solution. Aiming to reduce this time were tested alternative method in the Operation Research (PO) to resolve, developed one constructive heuristic and finally one Meta-heuristic the Variable Neighborhood Search (VNS), aiming to make solutions sets and combining them researching the best possible how the least computer effort, in other words, a least answer time. The VNS needs yet one initial solution to work, then it is the main reason to development of the one constructive heuristic, using one good solution to research an optimization, it with least effort computational if to compare with the mathematic model here studied. The computers tests were held with benchmark data of the literature. It was possible to verify that the proposed objective was reached, and it is possible to develop a methodology for optimizing the JSP resolution, but it needs to be improved and a new heuristic and a new local search is suggested for future work.
Keywords: Programação de Produção
Problema de Programação da Produção
Heurística Construtiva
Busca em Vizinhança Variável
Production Programming
Job Shop Problem
Constructive Heuristic
Variable Neighborhood Search
Area (s) of CNPq: CNPQ::ENGENHARIAS::ENGENHARIA DE PRODUCAO::PESQUISA OPERACIONAL
Language: por
Country: Brasil
Publisher: Universidade Federal de Uberlândia
Quote: AGUIAR, Bruna Bernardes. Job Shopr Problem - Estudo de um método heurístico para a sua otimização. 2018. 75 f. Trabalho de Conclusão de Curso (Graduação em Engenharia de Produção) – Universidade Federal de Uberlândia, Ituiutaba, 2018.
URI: https://repositorio.ufu.br/handle/123456789/24078
Date of defense: 6-Dec-2018
Appears in Collections:TCC - Engenharia de Produção (Ituiutaba / Pontal)

Files in This Item:
File Description SizeFormat 
JobShopProblem.pdf2.57 MBAdobe PDFThumbnail
View/Open


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.