This paper examines the problem of scheduling 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. It introduces a formal model for the demands imposed by multimedia requests on the server resources, describes 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.