Parallel machine scheduling with restricted job rejection

被引：9

作者：

Zhong, Xueling ^{[1
]}

Ou, Jinwen ^{[2
]}

机构：

[1] Guangdong Univ Finance, Dept Internet Finance & Informat Engn, Guangzhou 510520, Guangdong, Peoples R China

[2] Jinan Univ, Dept Adm Management, Guangzhou 510632, Guangdong, Peoples R China

来源：

THEORETICAL COMPUTER SCIENCE | 2017年 / 690卷

关键词：

Scheduling; Rejection; Approximation algorithms; Worst-case analysis; ORDER ACCEPTANCE; RELEASE DATES; ALGORITHMS;

D O I：

10.1016/j.tcs.2017.05.033

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

In this paper we study parallel-machine scheduling with job rejection, where the total processing time of the rejected jobs is required to be no greater than a predefined bound. The objective is to minimize the makespan of the accepted jobs plus the total penalty cost of the rejected jobs. The scheduling problem is NP-hard in the strong sense. We present a 2-approximation algorithm with a time complexity of O (n logn) by making use of specific data structure. We also develop a polynomial time approximation scheme (PTAS). Due to the job rejection restriction, some techniques for knapsack problems are applied in the development of our PTAS. (C) 2017 Elsevier B.V. All rights reserved.

引用

页码：1 / 11

页数：11