Minimization of the number of devices under working in systems of identical parallel devices (Q2730554)

The authors consider the following problem. The set \(N=\{1,\ldots,n\}\) of works fits into the system consisting of \(M\leq n\) identical parallel devices at time \(d=0\). Each work \(i\in N\) must be done by some device without interruption during \(t_{i}>0\) time units. It is necessary to find the minimal number \(M^{*}\) of executed devices which provides the fulfillment of all works up to a given time moment \(D\geq \max\limits_{i\in N} t_{i}\). The algorithm which forms a lexicographically increasing sequence of schedules, where every next schedule uses less number of devices than the previous one, is proposed.