Johnson’s Rule

The time complexity function for the general JSSP is exponential in nature, i.e., function grows exponentially with an increasing in the problem size. But, for a problem with 2 machines and n jobs, Johnson had developed a polynomial algorithm to get optimal solution in a definite time.^†In general, this rule is used to sequence N jobs through 2 machines in a given order.

References:

†R.Panneerselvam (August 2005), “Operation Research”, 407-419, Prentice-Hall of India Private Limited.

Related Posts:

• JOB SHOP SCHEDULING
• Description of Job Shop Scheduling
• Assumptions in static JSSP
• Algorithm of Johnson’s Rule
• Illustration for Johnson’s rule
• Modified Johnson’s Rule for n x m JSSP
• Limitations of Johnson’s Rule
• What makes scheduling problems hard?

Table of Contents

© 2006 Kumaravel & Project Team