How to use max flow to schedule machines? (building a network)

Question

Suppose you manage a machine shop with $k$ machines and have $n$ jobs to process today. Each job $i=1,2,3,4,5,\ldots,n$ requires $p_i>0$ minutes of processing time on any machine and has a processing windows $[a_i,d_i]$ with $a_i+p_i\le d_i$.

We have a job become available at time $a_i$ and must be completed by $d_i$.

A job can only be processed on one machine at a time, but it can be preempted; that is, its processing on one machine can be paused and later resumed on the same or another machine, as long as it finishes by its deadline.

I have to solve this problem by first creating a network with nodes and arcs, and then using a linear system to solve it.

I am not sure how to build the network. I know I have a source node and a sink node. The first nodes are the $n$ job, and the capacity of these arcs that connect source to the job nodes is $p_i$; but beyond that I am stuck.

If I have $k=3$ this is what the problem would look like:

job  1    2    3    4 
pi   2.5  1.5  2    4
ai   2    0    0.5  1
di   5    3    4    6

Can anyone tell me how to build this network?

Answer 1

When you have to model a problem as a flow problem, you can often interpret it as an 'assignment' or 'selection' problem. Here, your scheduling problem is equivalent to assigning jobs to machines. In other words, for every machine $m_1, m_2,\dots,m_k$ and for every point in time $t_1,t_2,\dots,t_h$ you need to determine which task gets executed (i.e. which task to assign to a machine/time combination). Conveniently, your jobs can be pre-empted. This simply means that you can start executing some job $j_1$ on a machine, pause it, execute some other tasks, and then continue executing $j_1$.

Since this sounds like a home-work assignment, I'll not disclose the full solution. As per your suggestion you indeed need to have a source node $s$ which is connected to the $n$ job nodes. The capacity of an arc from source node $s$ to job node $j_i$ is $p_i$. Next you'll need time-indexed machine nodes, namely one node for every machine and time pair: $(m_1,t_1),\dots,(m_1,t_h),(m_2,t_1),\dots,(m_2,t_h),\dots,(m_k,t_1),\dots,(m_k,t_h)$. I'll leave it up to you to decide (1) how to connect the $n$ job nodes to the machine nodes, (2) how to connect the machine nodes to the sink, and (3) how to set the arc capacities. Note that a machine can only perform 1 job at a time.