Excel Modeling for extended Johnson Rule of sequencing

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

Optimizing Equations:

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

 

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s