The Coffman–Graham algorithm solves scheduling N jobs (with unit length and DAG dependency) on K=2 machines with minimal span in polynomial time. When K is not a constant, the problem is known to be NPC. However, when K is a constant like 3, the problem is not known to be in P or NPC.