Expending Johnson's Rule

Expending Johnson's Rule to M-machines is an algorithmic method to control makespan based
on work by Campbell, Dudek and Smith.

This method creates M-1 possible schedules.

Essentially, collapse the M machines into a series of "2-machine" problems and apply
Johnson's Rule.
i.e: For 5 machines, there are 4 possible schedules. (M-1=5-1=4)

Notes:

for n-jobs and m-machines, the possibilities is (n!)^m

i.e
2-jobs and 2-machines, the possibilities is (2!)² = (2*1)² = 4

Define:

Schedule 1:

ti1 = First machine time
ti2 = Last machine time, M

Schedule 2:

ti1 = Sum of first two machine time
ti2 = Sum of last two machine time, M-1 and M

Schedule K:

ti1 = Sum of first K machine time
ti2 = Sum of last K machine time, M-K to M

Check:
i.e K = 3

then,  ti1 = Sum of first three machine time
         ti2 = Sum of last three machine time

i.e K = 4

then,  ti1 = Sum of first four machine time
         ti2 = Sum of last four machine time

* Remember : Possible schedule is M-1 = K

if M = 5, then M-1 = 4
Meaning, there are 4 possible schedules.



Example: (4-Jobs, 4-Machines)

       M1   M2   M3   M4

J1     5      8     4      3

J2     7      9     5      8

J3     2      3     9      7

J4     6      1     6      4

( J = Job, M = Machine )


Solution:

Then,
Possible Schedule is 3  ( M - 1 = 4 - 1 = 3 )

Schedule 1:

ti1 = First machine time = M1
ti2 = Last machine time = M4

        ti1     t12

J1     5      3

J2     7      8

J3     2      7

J4     6      4

Thus, based on Johnson's Rule, the sequence is J3-J2-J4-J1

Schedule 2:

ti1 = Sum of first two machine time = M1+M2
ti2 = Sum of last two machine time  = M3+M4

             ti1             ti2

J1     5+8= 13      4+3=  7

J2     7+9= 16      5+8= 13

J3     2+3=  5       9+7= 16

J4     6+1=  7       6+4= 10

Thus, based on Johnson's Rule, the sequence is J3-J4-J2-J1


Schedule 3:

ti1 = Sum of first three machine time = M1 + M2 + M3
ti2 = Sum of last three machine time  = M2 + M3 + M4


               ti1                ti2

J1     5+8+4= 17      8+4+3= 15

J2     7+9+5= 21      9+5+8= 22

J3     2+3+9= 14      3+9+7= 19

J4     6+1+6= 13      1+6+4= 11


Thus, based on Johnson's Rule, the sequence is J3-J2-J1-J4


The Gantt Charts is as follows:

Thus, the shortest completion sequence is Schedule 1 (J3-J2-J4-J1)
because the makespan is 38 units.






Notes:

Based on personal observation, to find out the minimum makespan times is by considering
the first machine (M1) and the last machine (M4).
Then, apply the Johnson's Rule to find the sequence.


        M1   M2   M3   M4

J1     5      8     4      3

J2     7      9     5      8

J3     2      3     9      7

J4     6      1     6      4


---------------------------------------------------------------------------

Read More:

Others Method
http://www2.ie.iwi.unibe.ch/forschung/e-learning/lernobjekte/

Machine Scheduling
http://www.math.uwaterloo.ca/~rbutterw/essays/Scheduling/1.8-serial

Heuristic Scheduling
http://books.google.com.my/books?id=6ORuBRNk_Z8C&pg=PA306&lpg=PA306&dq=johnson+rule+1954+three+machines&source=bl&ots=McPD373PXB&sig=qtwptEaJbF4kE_T7a1Uf81ZBg-U&hl=en&sa=X&ei=US8gT4rzAYS5iAez5uzhDQ&redir_esc=y#v=onepage&q=johnson%20rule%201954%20three%20machines&f=true