This paper examines the scheduling of concurrent requests on multimedia storage servers consisting of multiple resources, which is a central issue in processing and optimization of complex queries in multimedia database systems [Chaudhuri 1994]. It introduces a formal model for the demands imposed by multimedia requests on the server resources, described a heuristic algorithm for scheduling the requests that is based on the formal model, and presents a formal result that bounds the performance of the schedule produced by the algorithm compared to the optimal schedule.