Malcolm Yoke Hean Low

Category Archives | General | HPC | Research | Science | Teaching | Tech |

Date Archives | September 2009 | July 2009 | June 2009 | May 2009 | April 2009 | March 2009 | February 2009 | January 2009 | December 2008 | November 2008 | October 2008 | September 2008 | August 2008 | July 2008 | June 2008 | May 2008 | April 2008 | March 2008 | February 2008 | January 2008 | February 2007 | December 2006 | November 2006 | October 2006 | September 2006 | August 2006 | May 2006 | February 2006 | January 2006 |

RSS Feed

Enter your search terms

Submit search form

Johnson Algorithm for Two Machines Flow Shop

Posted on Saturday, January 14, 2006 at 1:13 PM by Malcolm

Johnson Algorithm for Two Machines Flow Shop

In the two-machine flow shop model, job i precedes job j in an optimal sequence if min{a_i, b_j} < min{a_j, b_i}. where a_i and b_i are the processing time of job i on the first and second machine respectively. The proof is due to Johnson (1954). One way to implement the rule is to partition the jobs into two sets. Set I contains jobs in which a_j < b_j and set II contains jobs in which a_j > b_j. An optimal schedule consists of the I-jobs, in nondecreasing order of a_j, followed by the II-jobs, in nonincreasing order of b_j.

Reference:

S.M. Johnson, Optimal two- and three-stage production schedules with setup times included, Naval Res. Log. Quart. I(1954)61-68.

Posted in Research (RSS)