Scheduling equal processing time jobs to minimize the weighted number of late jobs (Q853793)

The problem of scheduling \(n\) jobs with equal processing times on \(m\) parallel machine to minimize the weighted number of late jobs is discussed. Where -- as a surprise -- the preemtive version is proved to be an NP-hard problem using a reduction to the numerical matching with target sums problem (stated in Garey and Johnson (1979)). And the non-preemptive version is of complexity \(O(n\log n)\). Beside these two complexity results, extensions and further open problems are stated.