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. #R##N##R##N#The fastest known algorithm to compute the optimal solution of this problem has ${\mathcal{O}}(n\sqrt{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: ${\mathcal{O}}(n)$ . #R##N##R##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.
['Martha Escobar-Molano', 'David A. Barrett']
Resource scheduling with variable requirements over time