Sun Yat-Sen Management Review 1995/3
Vol. 3, No.1 p.1-9
Department of Business Management National Sun Yat-sen University, Kaohsiang Medical College
Parallel processors problems are among the most difficult combinatorial problems to solve. In this paper we study the problem of scheduling n independent jobs on m unrelated parallel processors with the objective of minimizing the makespan. We propose a branchand-bound algorithm for finding the optimal schedule. This algorithm depends on reducing the set of m constraints to a single diophantine equation, resulting in a knapsack problem. Computational experience indicates that most problems with 5 processors and 30 jobs can be solved in just a few seconds of computer time.
(633621990485625000.pdf 25KB)Knapsack, Scheduling, Unrelated Parallel Processors.
Parallel processors problems are among the most difficult combinatorial problems to solve. In this paper we study the problem of scheduling n independent jobs on m unrelated parallel processors with the objective of minimizing the makespan. We propose a branchand-bound algorithm for finding the optimal schedule. This algorithm depends on reducing the set of m constraints to a single diophantine equation, resulting in a knapsack problem. Computational experience indicates that most problems with 5 processors and 30 jobs can be solved in just a few seconds of computer time.
(633621990485625000.pdf 25KB)Knapsack, Scheduling, Unrelated Parallel Processors.