[Solved]: Minimize the total execution time of jobs executed by 3 processors in sequence

Problem Detail: 

There are 3 processors: $P_1$, $P_2$, $P_3$. $P_1$ can execute only one job while the other two can execute any number of jobs in parallel.

Each job consists of 3 parts, and each part is processed by their respective processor (eg. part 1 by $P_1$). Furthermore part 2 can be executed only after $P_1$ finishes executing part 1, and part 3 can be executed only after $P_2$ finishes executing part 2.

Suppose there are $n$ jobs, and again each job has 3 parts. The processor $P_k$ takes time $T_{i\,k}$ to complete part $k$ of job $i$. Can anyone suggest an algorithm that takes set of $n$ jobs and determines the the jobs should be processed so that the total time is minimized?

This is a homework problem and I don't know where ti start

Asked By : Anjali Sharma

Answered By : muddy

Well since no one else is giving an answer, here goes:

Assume the jobs are represented as $J=\{x_1,\ldots,x_n\}$

Since $P_1$ must process only one job at a time, it doesn't matter which order the jobs are processed, the time taken by $P_1$ is always the same, $\sum_{i=1}^n t_{i,1}$, each job's 3 parts are represented as $(t_{i,1},t_{i,2},t_{i,3})$. So to minimize the total time, we only need to consider the order that affects $P_2$ and $P_3$. Since both of them can execute any number of jobs in parallel, to minimize their time we want the jobs that need longer time to be processed first. So you arrange the jobs in decreasing order of $t_{i,2}+t_{i,3}$. Now to prove that this is optimal.

We need to show that in any optimal solution to the problem, if the ordering of the jobs is not the same as the ordering described above, we can convert it to our ordering without increasing the total time.

Let $C$ be an optimal ordering. Assume $C$ does not have the same ordering as that given by the algorithm. Which means, there exists jobs $x_i$ and $x_j$ such that $t_{i,2}+t_{i,3}<t_{j,2}+t_{j,3}$ and $x_i$ is listed immediately before $x_j$ in $C$, call such a pair of jobs an inversion. Consider the ordering $C'$ obtained from $C$ by swapping the position of $x_i$ and $x_j$. Thus $x_j$ would appear finish earlier here.

We can see that in $C'$, $P_2$ starts on job $x_i$ exactly when $P_2$ starts on job $x_j$ in $C$. This is independent of how long the first parts of $x_i$ and $x_j$ require. Since $t_{i,2}+t_{i,3}<t_{j,2}+t_{j,3}$, it's clear that in $C'$ job $x_i$ finishes sooner than job $x_j$ in $C$. So the total time taken by $C'$ is no larger than the time taken by $C$.

Repeat the above till all inversions are removed from $C$ and we have an ordering which is the same as that of the algorithm. Thus, the ordering returned by the algorithm is optimal.

Running Time: It's clear that the running time is $O(n\log n)$, I don't think I need to elaborate on that.

Hope this helps! Cheers!

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/10736

3.2K people like this

 Download Related Notes/Documents