Resource Scheduling With Variable Requirements Over Time

摘要

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 Ri 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_(j+k-1)~j and R_k~j are the 7th 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 O(n(1/2)m log m) 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: O(n). 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.