Scheduling n Jobs on Two Machines
The next step up in complexity of job shop types is the nl2 case, where two or more jobs must be processed on two machines in a common sequence. As in then] I case, there is an approach that leads to an optimal solution according to certain criteria. Also, as in the nil case, we assume it is a static scheduling situation. The objective of this approach, termed Johnson s rule not method (after its developer), is to minimize th.t flow time, from the be’ ginning of the first job until the completion of the last. Johnson’s rule consists of the following steps:
1. List the operation time for each job on both machines.
2. Select the job with the shortest operation time.
3. If the shortest time is for the first machine, do that job first; if the shortest time is for the second machine, do that job last.
4. Repeat Steps 2 and 3 for each remaining job until the schedule is complete
solution procedures leading to optimality are not available. The reason for this is that even though the jobs may arrive in static fashion at the first machine, the scheduling problem becomes dynamic, and a series of waiting lines start to form in front of machines downstream.