Multimedia streams such as audio and video require real-time manipulation. Unlike hard real-time tasks, however they have firm deadlines since the loss of a few frames does not lend to a significant degradation in quality. In this paper, we propose a simple but efficient scheduling scheme for multimedia streams using heuristic functions. The proposed heuristic function takes into account the fail ratio and the consecutive fail count in order to avoid consecutive fails of a multimedia task, and at the same time, to meet the given quality of all the accepted multimedia tasks in the system. By gracefully degrading the quality of the existing multimedia tasks, our scheme can meet the QoS of a newly arriving task accepted by the proposed admission control criteria. Extensive simulation has been performed to validate the effectiveness of the scheme under various multimedia task sets and QoS parameters.