Heurística baseada em PLIM para o sequenciamento de operações de usinagem em máquinas CNC tipo pórtico

Abstract

This work presents a heuristic procedure based on Mixed-Integer Linear Programming, whose objective is to solve a problem of sequencing milling operations performed on gantry computer numerical control machines, to minimize the non-productive time, called auxiliary time. The machine represented in the problem has a magazine that contains multiple tools, wich do drilling and finishing operations that obey precedence constraints. The problem described is similar to Traveling Salesman Problem with Precedence Constraints, since it is not possible to supress any operation neither execute them randomly. The lack of strategies that combine exact and heuristic - called matheuristics - methods and the impossibility of solving models available in the specialized literature justified this dissertation’s elaboration. The developed method uses two commercial mathematical programming solvers and has two distinct phases: in the first phase, a pre-processing procedure is executed by separating the problem, in which each possible path for any tool is calculated to complete the set operations assigned to it. In the second phase, a mathematical model selects one path for each tool and concatenates them, respecting the precedence constraints related to holes specifications, to give a complete solution to the operations sequencing problem. The computational results obtained show that the proposed method is more efficient than the algorithm used for comparison, obtaining better results for the instance tested with considerably less computational effort. Also, it was possible to proove the solution optimality for the instance used in the comparison.