A Hybrid Simulated Annealing for Job Shop Scheduling Problem

  • Leonor Hernández-Ramírez TECNM / Instituto Tecnológico de Ciudad Madero
  • Juan Frausto Solis
  • Guadalupe Castilla-Valdez TECNM / Instituto Tecnológico de Ciudad Madero
  • Juan Javier González-Barbosa TECNM / Instituto Tecnológico de Ciudad Madero
  • David Terán-Villanueva TECNM / Instituto Tecnológico de Ciudad Madero
  • María Lucila Morales-Rodríguez TECNM / Instituto Tecnológico de Ciudad Madero
Keywords: JSSP, Simulated Annealing, Ant Colony System, Genetic Algorithm, OpenMP

Abstract

The Job Shop Scheduling Problem (JSSP) arises in the context of high-performance computing and belongs to the NP-hard combinatorial optimization problems. The purpose of JSSP is to find the order of execution of a set of jobs on a group of machines, subject to certain precedence and resource availability constraints. The objective in this problem is minimizing the makespan that is the time elapsed from the starting time of the first job until the completion time of the last job. In this paper, a novel hybrid algorithm named AntGenSA for solving JSSP is proposed. AntGenSA uses Ant Colony System (ACS), Simulated Annealing (SA), and Genetic Algorithm (GA). To assess the performance of this algorithm, it is executed in a parallel computer, using a set of instances proposed by Fisher-Thompson, Yamada-Nakano, Taillard, Lawrence, and Applegate-Cook. The evaluation of this algorithm was performed mainly by the quality of the solution but the execution time was measuring as well. The experimental results show that the performance of the parallel execution of AntGenSA is highly competitive with the state-of-the-art algorithms.

Published
2018-08-10
How to Cite
Hernández-Ramírez, L., Frausto Solis, J., Castilla-Valdez, G., González-Barbosa, J. J., Terán-Villanueva, D., & Morales-Rodríguez, M. L. (2018). A Hybrid Simulated Annealing for Job Shop Scheduling Problem. International Journal of Combinatorial Optimization Problems and Informatics, 10(1), 6-15. Retrieved from https://ijcopi.org/index.php/ojs/article/view/111
Section
Articles