Scheduling with Rejection to Minimize the Total Weighted Completion Time

被引：0

作者：

Zhang, Shu-Xia ^{[1
]}

Cao, Zhi-Gang ^{[2
]}

Zhang, Yu-Zhong ^{[3
]}

机构：

[1] Zhenjiang Watercraft Coll, Dept Watercraft Command, Zhenjiang 212003, Jiangsu, Peoples R China

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

[3] Qufu Normal Univ, Coll Operat Res & Management Sci, Rizhao 276826, Shandong, Peoples R China

来源：

OPERATIONS RESEARCH AND ITS APPLICATIONS, PROCEEDINGS | 2009年 / 10卷

基金：

中国国家自然科学基金;

关键词：

Scheduling; Rejection; Identical parallel machines; Approximation algorithm;

D O I：

暂无

中图分类号：

C93 [管理学]; O22 [运筹学];

学科分类号：

070105 ; 12 ; 1201 ; 1202 ; 120202 ;

摘要：

In this paper, we address the scheduling problem with rejection in which we can choose a subset of jobs to process. Choosing not to process any job incurs a corresponding penalty. We consider the following problem for the first time: scheduling with rejection, to minimize the total weighted completion time with the constraint of total penalties on identical parallel machines, where the number of identical parallel machines is constant. We show that it is NP-hard and design a pseudo-polynomial time algorithm as well as an FPTAS through dynamic programming.

引用

页码：111 / +

页数：3

共 10 条

[1] 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

[2]

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

[3]

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

[4] On-line scheduling of unit time jobs with rejection: minimizing the total completion time [J].

Epstein, L ;

Noga, J ;

Woeginger, GJ .

OPERATIONS RESEARCH LETTERS, 2002, 30 (06) :415-420

[5]

Graham R. L., 1979, Discrete Optimisation, P287

[6]

He Y, 2000, COMPUTING, V65, P1

[7] Preemptive scheduling with rejection [J].

Hoogeveen, H ;

Skutella, M ;

Woeginger, GJ .

MATHEMATICAL PROGRAMMING, 2003, 94 (2-3) :361-374

[8] Preemptive multiprocessor scheduling with rejection [J].

Seiden, SS .

THEORETICAL COMPUTER SCIENCE, 2001, 262 (1-2) :437-458

[9]

Sengupta S, 2003, LECT NOTES COMPUT SC, V2748, P79

[10]

ZHANG SX, 2007, OR T, V11, P11

← 1 →