Scheduling unit time open shops to minimize the weighted number of late jobs

What is it about?

We present a polynomial algorithm for the problem of scheduling an open shop with unit time operations for a fixed number of machines such that the weighted number of late jobs is minimized. The algorithm is based on dynamic programming. The complexity of this problem was unknown for open shops with more than two machines.

Featured Image