Open shop scheduling problem to minimize makespan with release dates

The scheduling problem of open shop to minimize makespan with release dates is investigated in this paper. Unlike the usual researches to confirm the conjecture that the tight worst-case performance ratio of the Dense Schedule (DS) is 2 − 1/m, where m is the number of machines, the asymptotic optimality of the DS is proven when the problem scale tends to infinity. Furthermore, an on-line heuristic based on DS, Dynamic Shortest Processing Time-Dense Schedule, is presented to deal with the off-line and on-line versions of this problem. At the end of the paper, an asymptotically optimal lower bound is provided and the results of numerical experiments show the effectiveness of the heuristic.