A specific version of a job scheduling problem

Question

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.

Answer 1

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.

Answer 2

Two machines : $m_1,m_2$

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

Tasks are:

$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$ .