| Article ID | Journal | Published Year | Pages | File Type |
|---|---|---|---|---|
| 436207 | Theoretical Computer Science | 2009 | 7 Pages |
Abstract
We consider several single machine parallel-batch scheduling problems in which the processing time of a job is a linear function of its starting time. We give a polynomial-time algorithm for minimizing the maximum cost, an O(n5) time algorithm for minimizing the number of tardy jobs, and an O(n2) time algorithm for minimizing the total weighted completion time. Furthermore, we prove that the problem for minimizing the weighted number of tardy jobs is binary NP-hard.
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
