  This paper considers packet scheduling over a broadcast channel with packet
erasures to multiple receivers with different messages (multiple uni-cast) each
with possibly different hard deadline constraints. A novel metric is proposed
and evaluated: the global deadline outage probability, which gives the
probability that the hard communication deadline is not met for at least one of
the receivers. The cut-set upper bound is derived and a scheduling policy is
proposed to determine which receiver's packets should be sent in each time
slot. This policy is shown to be optimal among all scheduling policies, i.e.,
it achieves all boundary points of cut-set upper bounds when the transmitter
knows the erasure patterns for all the receivers ahead of making the scheduling
decision. An expression for the global deadline outage probability is obtained
for two receivers and is plotted and interpreted for various system parameters.
These plots are not Monte-Carlo simulations, and hence the obtained expression
may be used in the design of future downlink broadcast networks. Future
extensions to per-user deadline outage probabilities as well as to scenarios
with causal knowledge of the channel states are briefly discussed.
