Since bipartite edge coloring may be performed in polynomial time, the same is true for this restricted case of open shop scheduling.
Mivel a páros élszínezés polinom időben elvégezhető, ugyanez igaz az open-shop ütemezés ezen korlátozott esetére.