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{ai, bj} < min{aj, bi}. where ai and bi 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 aj < bj and set II contains jobs in which aj > bj. An optimal schedule consists of the I-jobs, in nondecreasing order of aj, followed by the II-jobs, in nonincreasing order of bj.Reference:
S.M. Johnson, Optimal two- and three-stage production schedules with setup times included, Naval Res. Log. Quart. I(1954)61-68.