The problem: Given n jobs with fixed start and end times, and k machines each capable of doing only one job at a time, find if it is possible to schedule all n jobs on these k machines using network-flow.
I know there are many similar questions here but none seem to exactly fit the specifications of this particular problem.
My general idea was to use a graph where each node represents a job and the directed edges out of this node will be connected to a job that starts after it ends. I'm assuming that's the basis but I'm struggling with juggling the 3 constraints:
- Cannot have two jobs on a single machine that intersect.
- Must use a maximum of k machines.
- Max flow possible should be n.
Every solution I tried fails because one of these constraints, would appreciate any help.
You have the right idea about jobs as nodes and directed arcs if the first job ends by the time the next job starts. Now split each node $i$ into two nodes $i'$ and $i''$, with a directed arc from $i'$ to $i''$ that has a lower bound of $1$. Introduce a source node $s$ with supply $k$ and a sink node $t$ with demand $k$, with an arc from $s$ to each $i'$, an arc from each $i''$ to $t$, and an arc from $s$ to $t$. All arcs except $(s,t)$ have an upper bound of $1$. The jobs can all be scheduled if and only if there is a feasible flow.