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?