A new lower bound for flow shop makespan with release dates

In the paper, we consider the flow shop makespan problem with release dates. A new lower bound of the problem is presented. The new lower bound is asymptotically equivalent to the optimality solution, when the size of the problem goes to infinity. And a tight worst case performance ratio, m, of the optimal solution to the new lower bound is obtained. Specially, when the processing times of jobs are all equal, the new lower bound is just the optimal solution. At the end of the paper, computational results show the effectiveness of the new lower bound on a set of random test problems.