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.