Two Asymptotically Optimal Lower Bounds for Flow Shop Problem

In this paper, we show that the optimalmakespan of the flow shop problem grows as O(n) whenthe size of the problem is large enough. And two lowerbounds with performance guarantee are presented to dealwith the objectives of minimizing respectively makespanand total weighted completion time. At the end of the paper, the effectiveness of the two lower bounds is showed bycomputational results.