Using Graphical Processing Units in Scheduling Problems

Abstract

Scheduling problems exist everywhere in the so-called “real world”. They are there in manufacturing, transportation and logistics as well. The main object of these problems is to find an optimal sequence of tasks to be able to fulfil predefined objectives. There are efficient methods to solve complex scheduling problems in science and industry, which methods can be divided into several classes, like heuristic algorithms, genetic algorithms, etc. Even if these methods allow reducing significantly the computational time of the solution search space exploration, this latter cost remains exorbitant when very large problem instances are to be solved. Some of these methods are not designed for parallel computing; they are using a CPU as an arithmetical unit. From this point of view the bottleneck is the number of processed commands. Meanwhile the capabilities of specialized Graphical Processing Units (GPUs) have been extremely increased and they can provide an efficient platform for developing graphical algorithms. Nowadays there are new programming languages and platforms, where these GPUs can be used for more generic problems, using its hardwired parallel processing resources. Our goal is to use this specialized graphical platform for solving scheduling problems. This paper is an initial research of the existing platforms and solutions in general and describes the existing solutions in fact of scheduling problems.