Dense open-shop schedules with release times

We study open-shop scheduling problems with job release times. The objective is to minimize the makespan. Dense schedules, easy to construct, are often used as approximate solutions. Performance ratios of the makespans from dense schedules and that of the optimal schedule of the problem are used to evaluate the quality of approximate schedules. It is conjectured (proved for a limited number of machines) that this performance ratio is bounded above by (2−1/m) for m-machine open-shop problems without job release times. In this paper, we extend the conjecture to open-shop problems with job release times. The results proved in this paper are: 1. Dense schedule performance ratio is bounded above by 2 for three-machine open-shop problems with job release times; 2. The conjectured performance ratio upper bound of 5/3 is proved for two special cases of three-machine open-shop problems with job release times; 3. A performance ratio upper bound of 7/4 is proved for three-machine problems.