| Article ID | Journal | Published Year | Pages | File Type |
|---|---|---|---|---|
| 4652759 | Electronic Notes in Discrete Mathematics | 2010 | 8 Pages |
Abstract
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.
Related Topics
Physical Sciences and Engineering
Mathematics
Discrete Mathematics and Combinatorics
