In this work we look at extending the work of (Dean et al. 1993) to handle more complicated scheduling problems in which the sources of complexity stem not only from large state spaces but from large action spaces as well. In these problems it is no longer tractable to compute optimal policies for restricted state spaces via policy iteration. We, instead, borrow from operations research in applying bottleneck-centered scheduling heuristics (Adams et al. 1988). Additionally, our techniques draw from the work of (Drummond and Bresina 1990).