Running time sensitive multimedia services such as Voice-over-IP (VoIP) and Video-on-Demand (VoD) on All-IP networks may have lower quality than that on the traditional circuit-switched networks. Influenced by many factors, packets transported on a packet-switched network, may suffer from long delay time, large jitter and high packet loss rate. When a packet arrives its destination late, there is no way to correct the problem. Thus, it will be beneficial if routers could forward packets base on their timeliness and importance, instead of using First-In-First-Out (FIFO) service plan, giving important late packets proper precedence. The overall QoS satisfaction will be improved significantly. In this thesis, we develop a simple and effective scheduling policy based on this concept for the environments where packets have predefined hop-by-hop time schedule. Routers are assumed in two different queue architectures: ideal Single Preemptive Queue router and practical Multiple FIFO Queue router. To forward a packet, a router first assigns a suitable profit function to the packet based on its timeliness and importance as well as the loading status in its succeeding routers along its predefined traveling path, then inserts the packet into an appropriate position in the output queues. Taking the loading status of succeeding routers into account could predict more accurately whether the packet could reach its destination on time or not. We conduct the research for the single service class environments first to learn the characteristics of this new scheduling policy, and then for the multiple service class environments based on the knowledge acquired. The challenge is to find the best way to assign proper profit functions to different classes of packets in order to utilize resources more wisely, e.g. urgent and important packets get precedence. We evaluate the performance of this approach by simulation using NS-2 network simulator. Simulation results show that our approach outperforms our previous version which doesn't take the loading status of succeeding routers into account. Furthermore, our approach can outperform the Simulated Priority Queue by at least 34% under heavy load and our evaluation metrics.