OPTIMAL SCHEDULING OF INDEPENDENT JOBS IN MULTIPROCESSOR SYSTEMS

In this paper, we consider the problem of finding an optimal schedule of several independent jobs in multiprocessor systems, i.e. for a give n job list, in what order the jobs should be processed and how to assi gn these jobs to the processors in a multiprocessor system such that t he completion time of the last completed job is minimized. We first di scuss two models of this problem, one in which time and processor requ irements of a job are fixed and the other in which time requirements o f a job varies according to the number of processors allocated to the job for execution. We then present efficient algorithms for solving th ese problem models, which are known to be NP-hard in the strong sense, using a branch and bound strategy. Our algorithms use several new red uction rules to arrive at optimal solutions in an efficient way. Final ly, we demonstrate the effectiveness of our algorithms by experimental results.