We consider scheduling problems that are motivated by an optimization of the transmission schedule of a smart antenna. In these problems we are given a set of messages and a conflict graph that specifies which messages cannot be transmitted concurrently. In our model the conflict graph is a unit circular-arc graph.
Two variants of the problem are considered:
, the messages have unit demands, whereas in
demands are arbitrary. We present an optimal algorithm for
and a 3-approximation algorithm for