PGP ’11 student, Kapil Vaish, An Operations enthusiast shares his insight on Excel Modeling
Excel Modeling for extended Johnson Rule of sequencing
Johnson Rule as of 1954 is used for optimal solution for sequencing n jobs on two machines. Extended Johnson rule for more than two machines club the problem and make it two machine problem to again carry out same algorithm.
Johnson rule algorithm has a specified rule of allocation of job on machine. Least processing time job on first machine will go first in sequence, Least processing time job on second machine will go last in sequence and hence on. It looks easy for small no of job and only two machines but becomes time consuming and complex n jobs and n machine.
Here I have attempt to develop a Mix integer linear programming model for Johnson rule and extended Johnson rule on more than two machines.
2 Machine “n” job sequencing:
Basic assumptions are:
1.) A job must follow the sequence over machine i.e. before moving to second machine it has to go through 1st machine
2.) Job will have same sequence on 1st as well as on 2nd machine
In sequencing problem we can get the optimal solution by minimizing either of the below three attribute. Deciding which one to minimize is solely depends on the management i.e. on what they want to minimize.
Here one thing is to be noted that scheduling sequence could be different for different optimizing equation used. Sequencing could also be different from Johnson rule solution.
An excel example is attached with this article. I have taken a hypothetical example to illustrate how to use MILP for sequencing n job. Sheet 1 have an example of “n” Job on 2 machine and sheet 2 have an example of “n” job “n” machine sequencing.
Hope you have enjoyed the article and gained out of it. Please feel free for any comment and clarification.
You can download the Excel here MILP model for sequencing