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, Delta- and (2, Delta)-regular, subcubic and grid graphs, which can be optimally colored in polynomial time.
compact schedule no-wait schedule bipartite graph consecutive edge-coloring np-completeness