Job Shop Problem – Estudo de um método heurístico para a sua otimização

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.