$NP$-hardness of scheduling problem I have been attempting to show that this problem is $NP$-complete but haven't been successful.  I wonder if anyone has a suggestion for a problem I could reduce to it.  

$CALLS$: Suppose we have nodes $\{0, \ldots, n - 1\}$, with undirected edges between $(i \mod n, i + 1 \mod n)$ for all $i$.  Furthermore, suppose we have a set $C$ of calls, which are the form $(i \mod n, j \mod n)$, and an integer $K$.  The problem is to determine whether it is possible to schedule the set of calls (to schedule a call, one decides whether to go clockwise around the circle or counterclockwise) such that the maximum load (i.e. number of calls going through a given edge) is $\le K$.

I have been able to show that if we assign each call a weight the problem is $NP$-complete by reducing $PARTITION$ to it.  However, I haven't been able to reduce any $NP$-complete problem to unweighted $CALLS$.
Indeed, it can be solved in polynomial time.  This is a result by Frank (1985).