文摘
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 , where there are independent unit-time jobs, time window constraints, 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 , employing network flow techniques. We develop an algorithm that handles successive nesting of on-time jobs more efficiently, with overall time complexity.