One of the most basics sequencing algorithms that produce optimal sequence for C_{max} criteria (maximum completion time) on Flow-shop system 2 and 3 processors without bottle neck and Proc2 dominated by 1st or 3rd. It’s complexity is O(N log N).
Version for 2 processors
Input: set filled with jobs. Every job have p_{1} and p_{2}, where p_{n} is defined as processing time on n processor.
Algorithm consist’s of three steps:
1) We divide set into two disjoint subsets A and B:
A = {Z_{i} : p_{i1} <= p_{i2}, i=1,2,…,n}
B = {Z_{i} : p_{i1} > p_{i2}, i=1,2,…,n}
As you see subset A containts all jobs with processing time on 1st processor lesser or equal to processing time on 2nd, and we insert other jobs to B subset.
2) We sort in ascending order A, and B in descending order.
3) If concatenation of A and B passes Johnson Statement:
min ( P_{i,1}, P_{k,2}) <= min (P_{k,1}, P_{i,2})
For all (i,k) (1 <= i < k <= n), where:
P_{K,N} is K job processing time on N processor.
Then sequence is optimal.
Example:
J_{1} | J_{2} | J_{3} | J_{4} | J_{5} | |
p_{1} | 3 | 3 | 1 | 5 | 2 |
p_{1} | 4 | 1 | 1 | 3 | 3 |
A subset is: J_{1}, J_{3}, J_{5}, after sorting J_{3}, J_{5}, J_{1}
B subset is: J_{2}, J_{4} after sorting J_{4}, J_{2}.
Optimal sequence is J_{3}, J_{5}, J_{1}, J_{4}, J_{2}
Version for 3 processors
If:
a) min P_{i,1} >= max P_{i,2}
Or:
b) min P_{i,3} >= max P_{i,2}
2nd processor is dominated by 1st (a) or by 3rd (b) and we can find optimal sequence by Johnson’s Algorithm by solving 2 processors problem with modified job time:
p’_{i,1} = p_{i,1} + p_{i,2}
p’_{i,2} = p_{i,2} + p_{i,3}