4
$\begingroup$

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?

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

1 Answer 1

2
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.