Advanced search
Start date
Betweenand
Related content

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

Grant number: 18/08326-6
Support type:Regular Research Grants
Duration: October 01, 2018 - September 30, 2020
Field of knowledge:Engineering - Production Engineering - Operational Research
Principal Investigator:Fabio Henrique Pereira
Grantee:Fabio Henrique Pereira
Home 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)