Recent enthusiasm in grid computing has resulted in a tremendous amount of research in resource scheduling techniques for tasks in a workflow. Most of the work on resource scheduling is aimed at minimizing the total response time for the entire workflow and treats the estimated response time of a task running on a local resource as a constant. However in a dynamic environment such grid computing, the behavior of resources simply cannot be ensured. In this thesis, thus, we propose a probabilistic framework for resource scheduling in a grid environment that views the task response time as a probability distribution to take into consideration the uncertain factors. The goal is to dynamically assign resources to tasks so as to maximize the probability of completing the entire workflow within a desired total response time. We propose three algorithms for the dynamic resource scheduling in grid environment, namely the integer programming, the max-max heuristic and the min-max heuristic. Experimental results using synthetic data derived from a real protein annotation workflow application demonstrate that the proposed probability-based scheduling strategies have similar performance in an environment with homogeneous resources and perform better in an environment with heterogeneous resources, when compared with the existing methods that consider the response time as a constant. Of the two proposed heuristics, min-max generally yields better performance.
| Identifer | oai:union.ndltd.org:NSYSU/oai:NSYSU:etd-0707107-004933 |
| Date | 07 July 2007 |
| Creators | Lin, Hung-yang |
| Contributors | San-yih Hwang, Bing -chiang Jeng, Wei-bo Lee, Chia-mei Chen |
| Publisher | NSYSU |
| Source Sets | NSYSU Electronic Thesis and Dissertation Archive |
| Language | English |
| Detected Language | English |
| Type | text |
| Format | application/pdf |
| Source | http://etd.lib.nsysu.edu.tw/ETD-db/ETD-search/view_etd?URN=etd-0707107-004933 |
| Rights | campus_withheld, Copyright information available at source archive |
Page generated in 0.002 seconds