Job Scheduling Techniques for Grid Systems withemporal Constraints
Date Issued
2009
Date
2009
Author(s)
Lin, Ping-Yi
Abstract
This paper introduces techniques in scheduling jobs with dependency constraint to processors whose available time are fragmented into time slots. We discuss two job dependency patterns – tree and chains. We show that it is NP-complete to schedule jobs with a tree dependency pattern. Then we propose a dynamic programming algorithm to get the optimal schedule for assigning jobs with linear dependency. The dynamic programming can be generalized to heterogeneous environment and tree-like dependency structure. In order to reduce the time of scheduling we also propose three different heuristics. Experimental results indicate that these heuristics do provide near optimal schedules even when compared against the optimal solution found by the dynamic programming.
Subjects
Temporal constraints
Job dependency
dynamic programming.
Type
thesis
File(s)![Thumbnail Image]()
Loading...
Name
ntu-98-R96922123-1.pdf
Size
23.32 KB
Format
Adobe PDF
Checksum
(MD5):13248a05b301084445ff2bd374a44862