We found a match
Your institution may have access to this item. Find your institution then sign in to continue.
- Title
PERFORMANCE BOUNDS FOR STATIC MULTIPROCESSOR SCHEDULING OF MULTI-TASK JOBS.
- Authors
MAHESH, S.; MURTHY, C. SIVA RAM; RANGAN, C. PANDU
- Abstract
Job scheduling on multiprocessor systems is studied here as a special case of oriented two-dimensional orthogonal bin packing. Each job has subtasks which can be processed in parallel, requiring multiple processors to be allocated to each job. Then each job corresponds to a rectangle with sides equal to the processor requirement and the processing time. We study two classes of algorithms: (i) Longest processing time first (LPT) algorithms, and (ii) Largest processor requirement first (LPR) algorithms. We obtain improved asymptotic upper bounds for these algorithms compared to the bounds of the corresponding algorithms for the general two-dimensional packing problem. This is due to the discrete nature of the processor requirement (dimension) of jobs. We find that the LPR algorithms have better asymptotic upper bound on the makespan compared to the LPT algorithms. Specifically, the bound is 7/4 for the LPR algorithms whereas it is 2 for the LPT algorithms. Moreover, LPR algorithms are found to be more suited for dynamic job scheduling.
- Publication
Parallel Processing Letters, 1995, Vol 5, Issue 3, p343
- ISSN
0129-6264
- Publication type
Article
- DOI
10.1142/S0129626495000321