A preemptive open shop scheduling problem with one resource (Q2641218)

A preemptive open shop scheduling problem with nonrenewable resource leads to a problem of the following form. We are given a bipartite multigraph with the property that for all \(i=1,...,n\) and \(j=1,...,m\) there are \(p_{ij}\) parallel edges betweeen i and j. Furthermore there are positive integers \(h_ 1,...,h_ q\) with \(\sum^{q}_{i=1}h_ i=\sum^{n}_{i=1}\sum^{m}_{j=1}p_{ij}\). Find an edge coloring with color sets \(H_ 1,...,H_ q\) such that \[ \sum^{i}_{s=1}| H_ s| \leq \sum^{i}_{s=1}h_ s\text{ for } i=1,...,q. \] It is shown that this problem is NP-complete. For the special case that all \(t_{ij}=1\) necessary and sufficient conditions on the sequence \(h_ 1,...,h_ q\) for the existence of a solution of the problem are given.