Open-shop dense schedules: properties and worst-case performance ratio

Dense schedules are easy to construct and can be used as heuristic solutions for open-shop problems. It is conjectured that in the worst-case a dense schedule will result in a makespan no more than $(2-\frac{1}{m})$ times of the makespan of the optimal schedule, where m is the number of machines. Different approaches have been used in proofs for different number of machines. The conjecture has been proved for the number of machines m?6, and for some special types of dense schedules. In this paper, we first summarize some useful properties of dense schedules, and then provide some special types of dense schedules that make the conjecture hold. Finally, we give complete proofs of the conjecture for m=7 and 8.