USING JOHNSON'S ALGORITHM TO APPROXIMATE SOME FLOW SHOP SCHEDULING PROBLEMS WITH UNAVAILABILITY PERIODS

Johnson’ algorithm (JA) is perhaps the most classical algorithm in the scheduling area. JA gives the optimal solution to the two machine flow shop to minimize the makespan in a polynomial time. Researchers have tried to extend this celebrated result to obtain polynomial time algorithms for more general cases. Such importance motivated us to devote this paper to JA applied to three flow shop problems with unavailability periods to minimize the makespan. First we focus on the optimality condition of JA. Then we propose an extension of JA. Last we calculate new performances of JA as a heuristic.