In this study, the performance of several approximation algorithms for multiprocessor scheduling is considered. Multiprocessor scheduling is an NP-hard problem which means that it may not be possible to design exact algorithms to solve this problem to optimality. Therefore, designing of approximation algorithms to solve this problem appears to be the only option available. The algorithms considered are designed incorporating the gang scheduling approach. An attempt is made to obtain solutions close to optimal using these algorithms. The study shows that these algorithms can be used to solve even large-scale problems occurring in practice.

Even with the advent of the multiprocessor computer systems with lightning speed, computational problems in many practical situations are yet to be solved satisfactorily. These problems are extremely difficult to solve, as they are categorized as NP-hard problems (Papadimitriou, 1993). The main property of NP-hard problems is that the computational burden in solving these problems increases exponentially as the problem size grows. There are many combinatorial optimization problems falling under this category. A combinatorial optimization problem requires an optimal solution to the given problem from a finite set of acceptable solutions. The number of acceptable solutions can be extremely large in many practical situations. Even though the faster processors can speed up the calculations, that alone may not be sufficient to help solve many difficult computational problems arising in practical situations within reasonable amounts of time. The reason is that faster computational ability has to be combined with more efficient software algorithms to make multiprocessor systems more efficient. Therefore, the challenge is to device better and more efficient algorithms to solve these problems. In this study, we consider the multiprocessor scheduling problem, which is an important problem related to multiprocessor computer systems as well as job shop scheduling in multiple machine situations.

For NP-hard problems, it is almost impossible to develop algorithms which give exact optimal solutions in a reasonable amount of time, as these are almost beyond our reach (Woeginger, 2003). Of course, these problems could be solved by exhaustive search. However, it will take more than our lifetime to enumerate all the possible solutions even with the fastest computers around. Therefore, the issue is, as the size of the problem instances grows, the running time of algorithms becomes prohibitively large very soon. In other words, no polynomial time exact algorithms exist for solving them. In a polynomial time algorithm, the number of computational steps grows as power of the number of variables, rather than exponentially. Hence, what we should do is to develop faster polynomial algorithms to reach a solution which is reasonably close to optimal for the relevant problems.

Computer Sciences Journal, Optimization, Gang scheduling, Backfilling, Makespan, Approximation algorithms, Lower bound