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 (...

Full description

Saved in:
Bibliographic Details
Published in:Theoretical computer science 2009-03, Vol.410 (8), p.830-836
Main Authors: Qi, Xianglai, Zhou, Shiguo, Yuan, Jinjiang
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!
Description
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