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.