title: Are all scheduling problems NP-Hard?
body: <p>I know there are some scheduling problems out there that are NP-hard/NP-complete ... however, none of them are stated in such a way to show this situation is also NP.</p>
  
  <p>If you have a set of tasks constrained to a <em>startAfter</em>, <em>startBy</em>, and <em>duration</em> all trying to use a <strong>single resource</strong> ... can you resolve a schedule or identify that it cannot be resolved without an exhaustive search?</p>
  
  <p>If the answer is <em>"sorry pal, but this is NP-complete"</em> what would be the best heuristic(s?) to use and are there ways to decrease the time it takes to a) resolve a schedule and b) to identify an unresolvable schedule.</p>
  
  <p>I've implemented (in prolog) a basic conflict resolution goal through recursion that implements a "smallest window first" heuristic. This actually finds solutions rather quickly, but is exceptionally slow at finding invalid schedules. Is there a way to overcome this?</p>
  
  <p>Yay for compound questions!</p>