A heuristic algorithm for open-shop scheduling problems with job priorities

This paper considers the open shop scheduling problems with job priorities and release times. For arbitrary number of machines, a simple algorithm can produce a schedule whose makespan is at most 2 times the optimal one in the worst-case in general. However, we conjecture the tight bound is 2 − 2/(m + 1) (m is the number of machines). The worst-case ratio is proved to be 3/2 for m = 3, and the bound is tight.