A PTAS for parallel batch scheduling with rejection and dynamic job arrivals

In the parallel batch scheduling model, a group of jobs can be scheduled together as a batch while the processing time of this batch is the greatest processing time among its members; in the model of scheduling with rejection, any job can be rejected with a corresponding penalty cost added to the ob...

Full description

Saved in:
Bibliographic Details
Published in:Theoretical computer science 2009-06, Vol.410 (27), p.2732-2745
Main Authors: Cao, Zhigang, Yang, Xiaoguang
Format: Article
Language:English
Subjects:
Applied sciences
Calculus of variations and optimal control
Computer science
control theory
systems
Computer systems performance. Reliability
Dynamic job arrivals
Exact sciences and technology
Mathematical analysis
Mathematics
Miscellaneous
Parallel batch
PTAS
Rejection
Scheduling
Sciences and techniques of general use
Software
Theoretical computing
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:In the parallel batch scheduling model, a group of jobs can be scheduled together as a batch while the processing time of this batch is the greatest processing time among its members; in the model of scheduling with rejection, any job can be rejected with a corresponding penalty cost added to the objective value. In this paper, we present a PTAS for the combined model of the above two scheduling models where jobs arrive dynamically. The objective is to minimize the sum of the makespan of the accepted jobs and the total penalty of the rejected ones. Our basic approaches are dynamic programming and roundings.
ISSN:0304-3975
1879-2294
DOI:10.1016/j.tcs.2009.04.006