Aplicação e análise de métodos heurísticos para a resolução de problemas de job shop

Abstract

More than ever companies are looking to increase their efficiency and productivity by eliminating waste in order to better allocate their material, human and productive resources. To allow this there are a number of apt tools, one of which is scheduling. It assists in reducing costs by ordering production to maximize the utilization of its resources. The application of heuristic methods to solve job sequencing problems becomes extremely feasible as the amount of variables increases due to its ability to present good quality solutions in a small amount of time. The purpose of this paper is to apply and analyze the following heuristics methods: Shortest Processing Time (SPT), Longest Processing Time (LPT) e Earliest Due Dates (EDD) for solving job ordering problems in a job shop production environment and verifying their performance to minimize makespan and delay fee cost. Two algorithms were developed, named as Method 1 and Method 2. The results obtained through the computational experiments show advantage of the SPT heuristic in the makespan minimization in both methods applied. For the delay fee minimization, method 1 shows better results with the SPT heuristic, while method 2 works better with EDD solution for the delay fee cost.