We present part of our work on the capacity upper bound, achievable rates, and scheduling
for the half duplex multiple-relay channel (HD MRC) where every node can either transmit
or listen, but not both, at any time. We derive a capacity upper bound based on the cut-set
argument, and achievable rates based on the decode-forward coding strategy (DF). We
discover that the upper bound and achievable rates are functions of the transmit state
vector (a description of which nodes transmit and which receive). More precisely, they are
functions of the time fraction of different transmit state vectors, which we term a schedule.
We formulate the optimal scheduling problem to find the best schedule, one that
maximizes the DF rate. For the phase fading HD MRC, surprisingly, we show that the
expressions for the capacity upper bound and for DF rate can be transformed into linear
programming problems.