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

  • Mayra S. Hernández G. Tecnológico Nacional de México, Instituto Tecnológico de Ciudad Madero
  • Federico Gamboa R. Tecnológico Nacional de México, Instituto Tecnológico de Ciudad Madero
  • Nelson Rangel V. Catedrático CONACyT, División de Estudios de Posgrado e Investigación, Tecnológico Nacional de México, Instituto Tecnológico de Ciudad Madero
  • Laura Cruz Reyes Tecnológico Nacional de México, Instituto Tecnológico de Ciudad Madero
  • Claudia G. Gómez Santillán Tecnológico Nacional de México, Instituto Tecnológico de Ciudad Madero
  • Daniel A. Martínez V. Tecnológico Nacional de México, Instituto Tecnológico de Ciudad Madero
Keywords: Scheduling Problems, Bandwidth Minimization Heuristics

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.

Published
2018-01-09
How to Cite
Hernández G., M., Gamboa R., F., Rangel V., N., Cruz Reyes, L., Gómez Santillán, C. G., & Martínez V., D. A. (2018). Decomposition Based on Models that use Bandwidth Minimization Heuristics in Matrices for Scheduling Problems. International Journal of Combinatorial Optimization Problems and Informatics, 8(3), 59-63. Retrieved from https://ijcopi.org/index.php/ojs/article/view/19
Section
Articles