A hypercube has emerged as an effective and popular network architecture for a large scale parallel computer. Since not every job requires such a large hypercube, a hypercube system should support multiprogramming so that more than one job can be running simultaneously on the system with each job running on a subcube. We consider the problem of nonpreemptive scheduling n independent jobs on am-dimensional hypercube with each job requiring a $d_i$ dimensional subcube ($2^{d_i}$processors) and $t_i$ time. The objective is to minimize the total finish time of the schedule. The problem is NP-Complete and research results have not been found.
This thesis presents heuristic algorithms for the problem. Using experimental results, performance of each algorithm is anynyzed and compared to others.
