Loading…
Single machine parallel-batch scheduling with deteriorating jobs
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 ( n 5 ) time algorithm for minimizing the number of tardy jobs, and an O (...
Saved in:
Published in: | Theoretical computer science 2009-03, Vol.410 (8), p.830-836 |
---|---|
Main Authors: | , , |
Format: | Article |
Language: | English |
Subjects: | |
Citations: | Items that this one cites Items that cite this one |
Online Access: | Get full text |
Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
Summary: | 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
(
n
5
)
time algorithm for minimizing the number of tardy jobs, and an
O
(
n
2
)
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. |
---|---|
ISSN: | 0304-3975 1879-2294 |
DOI: | 10.1016/j.tcs.2008.11.009 |