Resource scheduling with variable requirements over time |
| |
Authors: | Martha L Escobar-Molano David A Barrett |
| |
Affiliation: | (1) Asgard Systems, Corinth, TX 76210, USA |
| |
Abstract: | The problem of scheduling resources for tasks with variable requirements over time can be stated as follows. We are given
two sequences of vectors A=A
1,…,A
n
and R=R
1,…,R
m
. Sequence A represents resource availability during n time intervals, where each vector A
i
has q elements. Sequence R represents resource requirements of a task during m intervals, where each vector R
i
has q elements. We wish to find the earliest time interval i, termed latency, such that for 1≤k≤m, 1≤j≤q: A
i+k−1
j
≥R
k
j
, where A
i+k−1
j
and R
k
j
are the jth elements of vectors A
i+k−1 and R
k
, respectively. One application of this problem is I/O scheduling for multimedia presentations.
The fastest known algorithm to compute the optimal solution of this problem has
computation time (Amir and Farach, in Proceedings of the ACM-SIAM symposium on discrete algorithms (SODA), San Francisco,
CA, pp. 212–223, 1991; Inf. Comput. 118(1):1–11, 1995). We propose a technique that approximates the optimal solution in linear time:
.
We evaluated the performance of our algorithm when used for multimedia I/O scheduling. Our results show that 95% of the time,
our solution is within 5% of the optimal. |
| |
Keywords: | Resource scheduling Tasks with variable requirements over time Multimedia Smaller mathcing problem Approximation algorithms |
本文献已被 SpringerLink 等数据库收录! |
|