New heuristics for flow shop problem to minimize makespan

This paper investigates the flow shop problem with the objective to minimize makespan. New algorithms are designed: one is off-line heuristic, Single Job First, for problem Fm∥Cmax; and the other is on-line heuristic, Dynamic Single Job First (DSJF), for problem Fm|ri|Cmax and its on-line version. It is proved that the two heuristics are asymptotically optimal when the size of the problem is large enough. In addition, the asymptotical optimality of First-Come, First-Served manner is obtained as a byproduct of the asymptotical analysis of DSJF heuristic. At the end of the paper, a new lower bound with performance guarantee is provided for problem Fm∥Cmax, and computational experiments show the effectiveness of these heuristic algorithms.