||Advances in multimedia computing technologies offer new approaches to support on-line accesses to information from a variety of sources such as video clips, audio, images, and text. A client-server- based distributed multimedia system is a natural approach to support such functionalities. Distributed networked multimedia information systems are becoming a critical component of the technology-based information infra-structures. A major component of such systems is an efficient scheduling of multimedia documents to ensure a synchronized, orchestrated, and smooth display of user requests. Scheduling of multimedia information for synchronized delivery over broadband networks with limited resources and quality of service is identified as an NP-hard problem. Traditional static scheduling algorithms cannot achieve an acceptable level of performance since the number and types of requests generated by users varies with time. In dynamic scheduling, on the other hand, the main issue is to ensure that there is a proper trade-off between the quality of service and the cost of scheduling itself (which can affect the response time). We propose a number of fast dynamic scheduling algorithms with the main objective of minimizing the percentage of deadline missing probability. The performance of the proposed algorithms is extensively evaluated using a detailed simulation environment. The results testify the suitability of our algorithms in various system environments.