Job Scheduling Techniques for Distributed Systems with Heterogeneous Processor Cardinality
Date Issued
2009
Date
2009
Author(s)
Chang, Hung-Jui
Abstract
This paper proposes scheduling algorithms for assigning jobs with different release time and execution time, to machines with heterogeneous processor cardinality. We show that this scheduling problem is NP-complete, and propose dynamic programming to find the optimal schedules. Since the dynamic programming is time-consuming we propose techniques that improve the efficiency of the dynamic programming. We also propose heuristic algorithms for this scheduling problem. Experimental results suggest that some of the heuristics not only compute the answer efficiently but also provide good solution.
Subjects
Processor cardinality
distributed system
schedule
makespan
dynamic programing
NP-complete
Type
thesis
File(s)![Thumbnail Image]()
Loading...
Name
ntu-98-R96922136-1.pdf
Size
23.32 KB
Format
Adobe PDF
Checksum
(MD5):c5173711555956ae479cd93ead3aa7ef