New heuristics for flow shop problem to minimize makespan

This paper investigates the flow shop problem with the objective to minimizemakespan. New algorithms are designed: one is off-line heuristic, Single JobFirst, for problemF _m ∥C _max ;and the other is on-line heuristic, Dynamic Single Job First (DSJF), for problemF _m |r _i |C _max and its on-line version. It is proved that the two heuristics are asymptoticallyoptimal when the size of the problem is large enough. In addition, theasymptotical optimality of First-Come, First-Served manner is obtained as abyproduct of the asymptotical analysis of DSJF heuristic. At the end of thepaper, a new lower bound with performance guarantee is provided for problemF _m ∥C _max , andcomputational experiments show the effectiveness of these heuristicalgorithms.