Order statistics applications to queueing and scheduling problems |
| |
Authors: | Harel Arie Cheng Hilary |
| |
Institution: | (1) Faculty of Management, University of Toronto, Toronto, Ontario, Canada, M5S 3E6;(2) Graduate School of Management, Yuan-Ze University, 135 Yuan-Tung Road, Chung-Li, Taiwan, R.O.C. |
| |
Abstract: | We prove several basic combinatorial identities and use them in two applications: the queue inference engine (QIE) and earliest
due date rule (EDD) scheduling. Larson (1990) introduced the QIE. His objective was to deduce the behavior of a multiserver
queueing system without observing the queue. With only a Poisson arrival assumption, he analyzed the performance during a
busy period. Such a period starts once all servers are busy with the queue empty, and it ends as soon as a server becomes
idle. We generalize the standard order statistics result for Poisson processes, and show how to sample a busy period in the
M/M/c system. 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 earliness and tardiness penalties. The schedule is without preemption and with 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 total penalty costs of the EDD is linear in n. The mean of the total penalty costs of the EDD is known to be proportional to the square root of n (see Harel (1993)).
This revised version was published online in June 2006 with corrections to the Cover Date. |
| |
Keywords: | order statistics combinatorial identities queues random walk probabilistic analysis heuristic scheduling earliness penalty tardiness penalty |
本文献已被 SpringerLink 等数据库收录! |
|