STUDY OF NEIGHBORHOOD STRUCTURES AND LOCAL SEARCH STRATEGIES IN GPU FOR THE CLASSICAL JOB SHOP SCHEDULING PROBLEM.

• Grant number: 18/08326-6
• Support Opportunities: Regular Research Grants
• Start date: October 01, 2018
• End date: December 31, 2020
• Field of knowledge: Engineering - Production Engineering - Operational Research
• Principal Investigator: Fabio Henrique Pereira
• Grantee: Fabio Henrique Pereira
• Host Institution: Universidade Nove de Julho (UNINOVE). Campus Vergueiro. São Paulo , SP, Brazil

Abstract

The job shop scheduling problem has been exhaustively studied in recent years due to itspractical importance and computational complexity. In addition, the practical applications of theseproblems in industry are becoming larger and more complex, requiring more computational power andspecialized methods for a scalable solution. Local search techniques have been the method of choicefor problems of this complexity. The application of local search (LS) techniques in these cases, inparticular, proved to be necessary, but extremely computationally costly. An alternative to overcome thislimitation of computational cost is the parallel programming, with emphasis on the parallelism based onGPUs for general purpose computing. Parallelization in GPU allows an extremely high efficiency gain when compared to a usual processing unit (CPU), since the application has favorable demands on the architecture of those devices, which is more focused on the arithmetic logic unit. On the other hand, traditional neighborhood strategies suffer from a difficulty related to the characteristics of the search space in these problems, the so-called basin of attraction that hinder the convergence of optimization methods. So, the objective of this project is to develop a local search strategy for JSSP with neighborhood features and search strategies less sensitive to the basin of attraction and appropriate to the aspects of parallelism in NVIDIA graphics processors units and CUDA" platform. The obtained results will be analyzed and compared with the same methods developed in a conventional model to minimize the time difference between the start and finish of a sequence of jobs. (AU)

Scientific publications

(References retrieved automatically from Web of Science and SciELO through information on FAPESP grants and their corresponding numbers as mentioned in the publications by the authors)

PEREZ, YURI; PEREIRA, FABIO HENRIQUE. Estimating pandemic effects in urban mass transportation systems: An approach based on visibility graphs and network similarity. PHYSICA A-STATISTICAL MECHANICS AND ITS APPLICATIONS, v. 620, p. 13-pg., 2023-06-15. (18/08326-6)

PEREZ, YURI; PEREIRA, FABIO HENRIQUE. Simulation of traffic light disruptions in street networks. PHYSICA A-STATISTICAL MECHANICS AND ITS APPLICATIONS, v. 582, NOV 15 2021. (18/08326-6)