# A specific version of a job scheduling problem

I'm looking for a solutions or book references to a given variation of a job scheduling problem:

Given $n$ machines (let's denote it by $m_1, m_2, \ldots, m_n$) and $r$ tasks ($t_1, t_2, \ldots, t_r$). Each task $t$ can be described as a tuple $\left( (a_1, b_1), (a_2, b_2), \ldots, (a_k, b_k) \right)$, where $a_i$ is a number of some machine and $b_i$ is a required time to complete task $t$ on machine $a_i$. To complete the task, you need to start it on the first machine in the sequence ($a_1$) for a given amount of time ($b_1$), then start it on the second ($a_2$) and so on, until you finish your job on all of the given machines. It could be possible that number of machines in job description is smaller than $n$.

We will assume that tasks are atomic and one machine can do only one task in the same time, so it's possible that some task need to wait for a moment when a given machine is free. Finally, we want to find the ordering of tasks to given machines to minimize the total time of all tasks.

• "$a_i$ is a number of some machine" means? Is it the sequence of machines $t_j$ needs to complete its task? – Alwyn Mathew Oct 23 '16 at 10:08
• What makes your variant special? (Edit the title to highlight that!) Which standard approaches have you tried and why don't they work? Are you aware that you seem to have entered flow-shop territory? – Raphael Oct 23 '16 at 12:53
• Once a question is posted, it belongs to the community. (You own the content, but you have given Stack Exchange the right to use it.) We do not delete open, answered questions. Please do not vandalize a post, even if it's your own. – Gilles 'SO- stop being evil' Oct 24 '16 at 21:10

This scheduling problem is called non-preemptive job shop scheduling. The classic reference is

Edward G Coffman, Jr, and Peter J Denning: Operating Systems Theory, Prentice-Hall, 1973.

Job-shop scheduling is discussed in Section 3.7 and 3.8 (although they mainly focus on a restricted version of the problem called the flow shop problem where the $a_i$ are in the same order for every task.)

It is called job shop scheduling because most of the early work on it was done by industrial engineers who were trying to optimize work schedules for machines in a factory, rather than computers.

Two machines : $m_1,m_2$

Four Tasks: $t_1,t_2,t_3,t_4$

$t_1=((m_1,2),(m_2,3))\implies$ 5 instance of time

$t_2=((m_2,1),(m_1,2))\implies$ 3 instance of time

$t_3=((m_2,3),(m_1,1))\implies$ 4 instance of time

$t_4=((m_1,1),(m_2,4))\implies$ 5 instance of time

where $(m_2,1)$ and $(m_1,2)$ are subtasks of $t_1$ denoted as $t_{11}$ and $t_{12}$ respectively.

Considering all tasks arrives to the system at the same time.

Approach 1:

Schedule subtasks $t_{ij}$ on the basis of its burst time (running time) such that no subtask $t_{sj}$ is scheduled, if any unscheduled subtask $t_{dj}$ exist where $d<s$.

i.e., all subtask $t_{1j}$ should schedule before all $t_{2j}$

\begin{array} {|r|r|} \hline Machine \hspace{0.2cm} m_1 &t_{41} &t_{11} &t_{11} &t_{32} &t_{22} &t_{22} &- &- &- &- &- \\ \hline Machine \hspace{0.2cm} m_2 &t_{21} &t_{31} &t_{31} &t_{31} &t_{12} &t_{12} &t_{12} &t_{42} &t_{42} &t_{42} &t_{42} \\ \hline Time &1 &2 &3 &4 &5 &6 &7 &8 &9 &10 &11\\ \hline \end{array}

Approach 2:

Consider $t_{hj}$ and $t_{gj}$ be two subtask to be scheduled and $h>g$.

Schedule subtasks $t_{ij}$ on the basis of its burst time (running time).

Once $t_{hj}$ completes its task, $t_{h(j+1)}$ is also considered to be scheduled even if other $t_{gj}$ is still not scheduled (on the condition that burst time of $t_{h(j+1)} < t_{gj}$).

i.e., if subtask $t_{11}$ is finished, $t_{12}$ can be scheduled before $t_{21}$ where burst time $t_{12}<t_{21}$

\begin{array} {|r|r|} \hline m_1 &t_{41} &t_{11} &t_{11} &t_{22} &t_{22} &t_{32} &- &- &- &- &- \\ \hline m_2 &t_{21} &t_{12} &t_{12} &t_{12} &t_{31} &t_{31} &t_{31} &t_{42} &t_{42} &t_{42} &t_{42}\\ \hline Time &1 &2 &3 &4 &5 &6 &7 &8 &9 &10 &11\\ \hline \end{array}

Approach 2 is better than Approach 1, since we achieve better turnaround time for each task $t_i$ .