## 3 Solution Fundamentals  
### Johnson Algorithm for Two Stage Flow Shop Scheduling  
A typical two sequential stages flow shop scheduling problem can be solved by [PERSON] algorithm [6; 7], Johnson scheduling model can be seen in Figure 1. The preconditions of this scheduling problem are that the production jobs always need to be processed by M-A first, then processed by M-B. The production speeds of M-A and B are different. Therefore, a buffer unit has to exist between M-A and B to recover this speed difference. Two kinds of time delay can be found, the first kind is M-B starvation delay, this means that M-B is free but waiting M-A to finish the current job to be able to start processing the same job. This delay must happen at least once at the first job assignment. The second kind of the time delay is the buffer delay. This delay happens when M-A has finished a job (J\({}_{\rm i}\)) while M-B is busy in processing a prior job. Therefore, J\({}_{\rm i}\) has to wait in the buffer till M-B is free and J\({}_{\rm i}\) processing turn comes.  
[PERSON] algorithm tries to minimize the previously mentioned delays. Therefore, it minimizes the makespan of M-B which is the longest makespan of that manufacturing workcell [8]. [PERSON] algorithm can be summarized by the next three steps:  
* Step-1: Find the shortest processing time among all the present non-scheduled standing jobs. If two or more jobs have the same processing time. Select one of them arbitrarily.
* Step-2: If the shortest processing time locates on M-A, schedule the corresponding job as the soonest. If the shortest processing time locates on M-B, schedule the corresponding job as the latest.
* Step-3: Eliminate the job that has been scheduled from the present non-scheduled standing jobs. Repeat steps 1 and 2 till scheduling all the jobs.  
The left section of Table 1 shows a group of unscheduled jobs J\({}_{\text{i}}\). In order to schedule those jobs using Johnson algorithm we should find the shortest Processing Time (T\({}_{\text{P}}\)) which is J\({}_{\text{1}}\) and equals to 5 time units, since this time locates on M-B, therefore it has to be scheduled at the end of the queue. J\({}_{\text{2}}\) comes after with the shortest T\({}_{\text{P}}\) on M-A, therefore it has to be scheduled at the beginning of the queue. Then J\({}_{\text{5}}\) is the job with the shortest T\({}_{\text{P}}\) on M-B, therefore we put it before J\({}_{\text{1}}\). Finally, we find that J\({}_{\text{3}}\) and J\({}_{\text{4}}\) are equal in the shortest T\({}_{\text{P}}\) on M-A, therefore we select one of them arbitrarily to come after J\({}_{\text{2}}\). In this example, we selected J\({}_{\text{4}}\) to be scheduled first then J\({}_{\text{3}}\). In order to prove that Johnson scheduling is the optimum solution, we compared it with the FCFS scheduling method which can also be seen at the middle section of Table 1 and in Figure 2a. By calculating the Operation Time (T\({}_{\text{O}}\)) based on the given T\({}_{\text{P}}\). We can see that the makespan of the FCFS scheduling is 54 time units. While, by applying Johnson algorithm, the makespan is reduced to 49 time units which can be seen at the right section of Table 1 and in Figure 2b.