OPTIMAL SCHEDULING POLICIES FOR A CLASS OF QUEUES WITH CUSTOMER DEADLINES TO THE BEGINNING OF SERVICE.

Summary form only given, as follows. Many problems can be modeled as single server queues with impatient customers. An example is that of the transmission of voice packets over a packet-switched network. If the voice packets do not reach their destination within a certain time interval of their transmission, they are useless to the receiver and considered lost. It is therefore desirable to schedule the customers such that the fraction of customers served within their respective deadlines is maximized. For this measure of performance it is shown that the shortest time to extinction (STE) scheduling policy is optimal for a class of queues. It is also shown, for a wider class of queues, that the optimal scheduling policy belongs to the class of shortest time to extinction with inserted idle times, or STEI scheduling policies. For one of these queues we compute the expected customer loss using an STE policy and compare its performance with that of the FCFS scheduling policy.