Decomposition Based on Models that use Bandwidth Minimization Heuristics in Matrices for Scheduling Problems

Abstract

Scheduling Activity (SA) is a highly complex optimization problem that is relevant nowdays, both in the private sector and in the public sector. In state of the art are reported several approaches for SA. However, the number of jobs that involve decomposition strategies in their solution is very limited. According to the literature, the decomposition of a problem favors the efficient use of computing resources, improving execution time and reaching competitive solutions compared to those reported in the literature. This paper proposes a new model-based decomposition method, which uses bandwidth minimization algorithms (BMA) in scattered matrices for the generation of angular structures in linear programming models. The study seeks to demonstrate that, depending on the BMA, there is a difference in the results obtained by the proposed method. The results obtained from the proposed experiment demonstrate that there are differences in the decomposition obtained by the method, using two particular heuristics that minimize the bandwidth in scattered matrices. The differences are regarding the reduction in the number of additional variables generated, when the bandwidth is lower. This fact suggests to look for better BMA, and to compare its effects under the proposed method, against other strategies of decomposition.