  In multi-access wireless networks, transmission scheduling is a key component
that determines the efficiency and fairness of wireless spectrum allocation. At
one extreme, greedy opportunistic scheduling that allocates airtime to the user
with the largest instantaneous channel gain achieves the optimal spectrum
efficiency and transmission reliability but the poorest user-level fairness. At
the other extreme, fixed TDMA scheduling achieves the fairest airtime
allocation but the lowest spectrum efficiency and transmission reliability. To
balance the two competing objectives, extensive research efforts have been
spent on designing opportunistic scheduling schemes that reach certain tradeoff
points between the two extremes. In this paper and in contrast to the
conventional wisdom, we find that in relay-assisted cellular networks, fixed
TDMA achieves the same optimal diversity gain as greedy opportunistic
scheduling. In addition, by incorporating very limited opportunism, a simple
relaxed-TDMA scheme asymptotically achieves the same optimal system reliability
in terms of outage probability as greedy opportunistic scheduling. This reveals
a surprising fact: transmission reliability and user fairness are no longer
contradicting each other in relay-assisted systems. They can be both achieved
by the simple TDMA schemes. For practical implementations, we further propose a
fully distributed algorithm to implement the relaxed-TDMA scheme. Our results
here may find applications in the design of next-generation wireless
communication systems with relay architectures such as LTE-advanced and WiMAX.
