Please use this identifier to cite or link to this item: http://hdl.handle.net/11717/3251
Title: Optimal scheduling of independent jobs in multiprocessor systems
Authors: Ignatius, P.P.
Ram Murthy, C.S.
Keywords: Algorithms; Computational complexity; Multiprocessing systems; Optimization; Resource allocation; Scheduling; Trees (mathematics); Branch and bound; Combinatorial tree; Completion time; Independent job scheduling; Job malleability; Reduction rules; Computer systems programming
Issue Date: 1994
Citation: Microprocessing and Microprogramming, 40(9), 651-672
Abstract: In this paper, we consider the problem of finding an optimal schedule of several independent jobs in multiprocessor systems, i.e. for a given job list, in what order the jobs should be processed and how to assign these jobs to the processors in a multiprocessor system such that the completion time of the last completed job is minimized. We first discuss two models of this problem, one in which time and processor requirements of a job are fixed and the other in which time requirement of a jobs varies according to the number of processors allocated to the job for execution. We then present efficient algorithms for solving these problem models, which are known to be NP-hard in the strong sense, using a branch and bound strategy. Our algorithms use several new reduction rules to arrive at optimal solutions in an efficient way. Finally, we demonstrate the effectiveness of our algorithms by experimental results. ? 1994.
URI: http://dx.doi.org/10.1016/0165-6074(94)90092-2
http://hdl.handle.net/11717/3251
ISSN: 1656074
Appears in Collections:Articles

Files in This Item:
There are no files associated with this item.


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.