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
相关论文
共 50 条
  • [1] Scheduling with job rejection and nonsimultaneous machine available time on unrelated parallel machines
    Jiang, Dakui
    Tan, Jiayin
    THEORETICAL COMPUTER SCIENCE, 2016, 616 : 94 - 99
  • [2] Two-machine job shop scheduling with optional job rejection
    Chen, Ren-Xia
    Li, Shi-Sheng
    OPTIMIZATION LETTERS, 2024, 18 (07) : 1593 - 1618
  • [3] Parallel-Machine Scheduling Problem under the Job Rejection Constraint (Extended Abstract)
    Li, Weidong
    Li, Jianping
    Zhang, Xuejie
    Chen, Zhibin
    FRONTIERS IN ALGORITHMICS, FAW 2014, 2014, 8497 : 158 - 169
  • [4] Parallel-machine scheduling with job-dependent cumulative deterioration effect and rejection
    Li, Shi-Sheng
    Chen, Ren-Xia
    Feng, Qi
    Jiao, Cheng-Wen
    JOURNAL OF COMBINATORIAL OPTIMIZATION, 2019, 38 (03) : 957 - 971
  • [5] New approximation algorithms for machine scheduling with rejection on single and parallel machine
    Liu, Peihai
    Lu, Xiwen
    JOURNAL OF COMBINATORIAL OPTIMIZATION, 2020, 40 (04) : 929 - 952
  • [6] Scheduling parallel machines with inclusive processing set restrictions and job rejection
    Ou, Jinwen
    Zhong, Xueling
    Qi, Xiangtong
    NAVAL RESEARCH LOGISTICS, 2016, 63 (08) : 667 - 681
  • [7] On Parallel Machine Scheduling with Rejection
    Cao, Li-si
    Liu, Zi-xian
    Jiang, Da-kui
    PROCEEDINGS OF THE 22ND INTERNATIONAL CONFERENCE ON INDUSTRIAL ENGINEERING AND ENGINEERING MANAGEMENT: CORE THEORY AND APPLICATIONS OF INDUSTRIAL ENGINEERING (VOL 1), 2016, : 845 - 851
  • [8] An improved heuristic for parallel machine scheduling with rejection
    Ou, Jinwen
    Zhong, Xueling
    Wang, Guoqing
    EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 2015, 241 (03) : 653 - 661
  • [9] Improved approximation algorithms for parallel machine scheduling with release dates and job rejection
    Zhong, Xueling
    Ou, Jinwen
    4OR-A QUARTERLY JOURNAL OF OPERATIONS RESEARCH, 2017, 15 (04): : 387 - 406
  • [10] Improved approximation algorithms for parallel machine scheduling with release dates and job rejection
    Xueling Zhong
    Jinwen Ou
    4OR, 2017, 15 : 387 - 406
12345