Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
419550 | Discrete Applied Mathematics | 2010 | 14 Pages |
Abstract
We study bicriteria problems of minimizing maximum tardiness and total due date assignment cost in various scheduling environments. We assume that each job can be assigned a different due date without any restriction, and that each due date assignment cost is a non-decreasing function of the quoted due date. We settle the complexity of most of the problems studied by either proving that they are NPNP-hard or finding a polynomial time solution for them. We also include approximation and non-approximability results for several parallel-machine problems.
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Dvir Shabtay, George Steiner, Liron Yedidsion,