Compact scheduling in open shop with zero–one time operations

A problem of no-wait scheduling of zero–one time operations in an open shop without allowing inserted idle times is considered. We show that this problem is equivalent to the problem of consecutive coloring the edges of a bipartite graph, which is NP-hard. Since such colorings are not always possible when the number of processors m > 3, we concentrate on special families of scheduling graphs, e.g.: complete bipartite, trees and cacti, Δ- and (2, Δ)-regular, subcubic and grid graphs, which can be optimally colored in polynomial time.