Home » Algorithms » Johnson’s sequencing Algorithm

Johnson’s sequencing Algorithm

One of the most basics sequencing algorithms that produce optimal sequence for Cmax 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 p1 and p2, where pn 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 = {Zi : pi1 <= pi2, i=1,2,…,n}
B = {Zi : pi1 > pi2, 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 ( Pi,1, Pk,2) <= min (Pk,1, Pi,2)
For all (i,k) (1 <= i < k <= n), where: PK,N is K job processing time on N processor.

Then sequence is optimal.

Example:

J1 J2 J3 J4 J5
p1 3 3 1 5 2
p1 4 1 1 3 3

A subset is: J1, J3, J5, after sorting J3, J5, J1
B subset is: J2, J4 after sorting J4, J2.

Optimal sequence is J3, J5, J1, J4, J2

Version for 3 processors

If:
a) min Pi,1 >= max Pi,2
Or:
b) min Pi,3 >= max Pi,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 = pi,1 + pi,2
p’i,2 = pi,2 + pi,3

Posted in Algorithms and tagged as

Comments are closed.