ORDER-STATISTICS APPLICATIONS TO QUEUING AND SCHEDULING PROBLEMS

We prove several basic combinatorial identities and use them in two ap plications: the queue inference engine (QIE) and earliest due date rul e (EDD) scheduling. Larson (1990) introduced the QIE. His objective wa s to deduce the behavior of a multiserver queueing system without obse rving the queue. With only a Poisson arrival assumption, he analyzed t he performance during a busy period. Such a period starts once all ser vers are busy with the queue empty, and it ends as soon as a server be comes idle. We generalize the standard order statistics result for Poi sson processes, and show how to sample a busy period in the M/M/c syst em. We derive simple expressions for the variance of the total waiting time in the M/M/c and M/D/1 queues given that n Poisson arrivals and departures occur during a busy period. We also perform a probabilistic analysis of the EDD for a one-machine scheduling problem with earline ss and tardiness penalties. The schedule is without preemption and wit h no inserted idle time. The jobs are independent and each may have a different due date. For large n, we show that the variance of the tota l penalty costs of the EDD is linear in n. The mean of the total penal ty costs of the EDD is known to be proportional to the square root of n. (see Harel (1993)).