Scheduling on parallel machines considering job-machine dependency constraints

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