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

被引：31

作者：

Cao, Zhigang ^{[1
]}

Yang, Xiaoguang ^{[1
]}

机构：

[1] Chinese Acad Sci, Key Lab Management Decis & Informat Syst, Acad Math & Syst Sci, Beijing 100190, Peoples R China

来源：

THEORETICAL COMPUTER SCIENCE | 2009年 / 410卷 / 27-29期

基金：

中国国家自然科学基金;

关键词：

Scheduling; Parallel batch; Dynamic job arrivals; Rejection; PTAS; MINIMIZING MAKESPAN; PROCESSING MACHINE; RELEASE TIMES; ALGORITHMS;

D O I：

10.1016/j.tcs.2009.04.006

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

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. (C) 2009 Elsevier B.V. All rights reserved.

引用

页码：2732 / 2745

页数：14

共 24 条

[1]

[Anonymous], P 40 ANN IEEE S FDN

[2] Multiprocessor scheduling with rejection [J].

Bartal, Y ;

Leonardi, S ;

Marchetti-Spaccamela, A ;

Sgall, J ;

Stougie, L .

SIAM JOURNAL ON DISCRETE MATHEMATICS, 2000, 13 (01) :64-78

[3]

Bartholdi J.J., 1988, UNPUB

[4]

Brucker P., 1998, Journal of Scheduling, V1, P31, DOI 10.1002/(SICI)1099-1425(199806)1:1<31::AID-JOS4>3.0.CO

[5]

2-R

[6] Scheduling with rejection and non-identical job arrivals [J].

Cao, Zhigang ;

Zhang, Yuzhong .

JOURNAL OF SYSTEMS SCIENCE & COMPLEXITY, 2007, 20 (04) :529-535

[7]

Cao ZG, 2006, LECT NOTES COMPUT SC, V3959, P90

[8]

DENG X, 2005, J COMB OPTIM, V9, P5, DOI DOI 10.1007/S10878-005-5480-7

[9] Approximation algorithms in batch processing [J].

Deng, XT ;

Poon, CK ;

Zhang, YZ .

JOURNAL OF COMBINATORIAL OPTIMIZATION, 2003, 7 (03) :247-257

[10]

ENGELS DW, 1998, LECT NOTES COMPUT SC, V1461, P490

← 1 2 3 →