The next decade will see increasing levels of integration of all kinds of communication needs in a common network. There has been a marked interest in packet-switched networks as a means to attain that goal. While the performance of data traffic is measured in terms of delay, real-time traffic such as voice and video is measured in terms of packet losses. Besides giving real-time traffic priority over data traffic, little work has been done in determining scheduling policies which minimize packet losses. This research models nodes in the network as queues with customers (packets), each of which has a deadline for service which, if exceeded, leads to a packet loss. A scheduling policy, called the shortest time to extinction (STE) policy, is shown to be optimal for a class of queues. These results are extended to a larger class of queueing systems, including multi-server and multi-class queues. To aid the analysis and design of queues with such scheduling policies, methods of computing losses for such queues are developed.