Volume 12 Number 3 (Jul. 2022)
Home > Archive > 2022 > Volume 12 Number 3 (Jul. 2022) >
IJAPM 2022 Vol.12(3): 22-33 ISSN: 2010-362X
DOI: 10.17706/ijapm.2022.12.3.22-33

Single Machine Scheduling with Job Rejection and Generalized the Number of Rejected Jobs

Ruiqing Sun, Mingyao Li, Bin Deng
Abstract—In this paper, we consider the single machine scheduling with job rejection and generalized the number of rejected jobs. More specifically, each job is either accepted and processed on the single machine, or is rejected by paying a rejection cost, but the total number of rejected jobs are strictly upper bounded by given thresholds. Two problems are considered: (1) minimize total weighted completion time and the sum of rejection cost, and (2) minimize total weighted completion time under the job rejection constraint. For the first scheduling problem, we provide a 2.618-approximation algorithm, a pseudo-polynomial time algorithm and a full polynomial-time approximation scheme (FPTAS) for this problem. In additions, we also discuss some special cases and provide two polynomial-time algorithms for them. For the latter problem, we provide a pseudo-polynomial time dynamic programming algorithm. Furthermore, we develop the dynamic programming into a fully polynomial time approximation scheme.

Index Terms— Scheduling, rejection, dynamic programming, fully polynomial time approximation scheme.

Ruiqing Sun, Mingyao Li, and Bin Deng are with School of Mathematics and Statistics, Yunnan University, Kunming, China.

Cite:Ruiqing Sun, Mingyao Li, Bin Deng, "Single Machine Scheduling with Job Rejection and Generalized the Number of Rejected Jobs ," International Journal of Applied Physics and Mathematics vol. 12, no. 3, pp. 22-33, 2022.

Copyright © 2022 by the authors. This is an open access article distributed under the Creative Commons Attribution License which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited (CC BY 4.0).

PREVIOUS PAPER
First page
NEXT PAPER
Last page

General Information

ISSN: 2010-362X (Online)
Abbreviated Title: Int. J. Appl. Phys. Math.
Frequency: Quarterly
DOI: 10.17706/IJAPM
Editor-in-Chief: Prof. Haydar Akca 
Abstracting/ Indexing:  Index Copernicus, IET INSPEC, CNKI, Chemical Abstracts Services (CAS), Nanowerk Database, Google Scholar, EBSCO, etc.
E-mail: ijapm@iap.org
  • Dec 27, 2021 News!

    IJAPM Vol 9 & Vol 10 have been indexed by Inspec   [Click]

  • Sep 23, 2022 News!

    IJAPM Vol 12, No 4 has been published with online version   [Click]

  • Jun 16, 2022 News!

    IJAPM Vol 12, No 3 has been published with online version   [Click]

  • Mar 23, 2022 News!

    IJAPM Vol 12, No 2 has been published with online version   [Click]

  • Dec 27, 2021 News!

    IJAPM Vol 12, No 1 has been published with online version   [Click]

  • Read more>>