Scheduling problem with multi-purpose parallel machines

We consider a multi-purpose identical parallel machine scheduling problem, in which jobs should be executed on some machine belonging to a given subset of the set of machines. The problem is PMPM|rj;pj=1|∑wjUj, where there are nn independent unit-time jobs, time window constraints, mm identical parallel multi-purpose machines, and the objective is the minimization of the total weighted number of tardy jobs. The best previous complexity for this problem is O(n2m(n+logm))O(n2m(n+logm)), employing network flow techniques. We develop an algorithm that handles successive nesting of on-time jobs more efficiently, with O(n3)O(n3) overall time complexity.