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

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?

• Is there any relation like precedence constraint between the jobs? Apr 5, 2022 at 4:28
• I think the machine can work only one job at a time. Apr 5, 2022 at 16:51

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.