Some preemptive open shop scheduling problems with a renewable or a nonrenewable resource (Q1186309): Difference between revisions

The authors investigate relations between an edge coloring problem and a preemptive open shop scheduling problem with constraints generated by one resource \(R\). In particular, they consider two complementary cases: when \(R\) is renewable and when \(R\) is nonrenewable. Each of these constraints causes that the general problem becomes NP-complete. Therefore they present some special cases which can be solved efficiently. Though the authors do not give any particular scheduling algorithm, they claim that those special cases lead to polynomial-time algorithms.