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).