In this paper, we consider the single machine parallel-batch scheduling problem with release dates and the number of rejected jobs not exceeding a given threshold. In this problem, we are given a set of jobs and a parallel batch processing machine. Each job has its release date and processing time; for each job, it is either to be rejected or to be accepted and processed in some batch on the machine. If one job is rejected then its corresponding rejection cost should be paid. To keep a certain service level, it is required that the number of rejected jobs is not greater than a given threshold. The task is how to partition the rejected jobs and the accepted jobs with the given constraint, and determine the batches and the orders for the accepted jobs on the machine to minimize the sum of the makespan and the total rejection cost. Since the studied problem is NP-hard, we propose a pseudo-polynomial time dynamic programming exact algorithm, a 2-approximation algorithm and a fully polynomial time approximation scheme.
LIU Xiaoxia, YU Shanshan, LUO Wenchang
. Approximation algorithms for single machine parallelbatch scheduling with release dates subject to the number of rejected jobs not exceeding a given threshold[J]. Operations Research Transactions, 2020
, 24(1)
: 131
-139
.
DOI: 10.15960/j.cnki.issn.1007-6093.2020.01.010
[1] Graham R L, Lawler, E L, Lenstra J K, et al. Optimization and approximation in deterministic sequencing and scheduling:a survey[J]. Annals of Discrete Mathematics, 1979, 5:236-287.
[2] Lee C Y, Uzsoy R, Martin-Vega L A. Efficient algorithms for scheduling semiconductor burn-in operations[J]. Operations Research, 1992, 40(4):764-775.
[3] Brucker P, Glladky A, Hoogeveen H, et al. Scheduling a batching machine[J]. Journal of Scheduling, 1998, 1:31-45.
[4] Lee C Y. Minimizing makespan on a single batch processing machine with dynamic job arrivals[J]. International Journal of Production Research, 1999, 37(1):219-236.
[5] Cheng T C E, Liu Z, Yu W. Scheduling jobs with release dates and deadlines on a batching processing machine[J]. IIE Transactions,2001, 33:685-690.
[6] Liu Z, Yuan J, Cheng T C E. On scheduling an unbounded batch machine[J]. Operations Research Letters, 2003, 31:42-48.
[7] 王珍, 曹志刚, 张玉忠. 极小化最大完工时间及拒绝费用的单机可拒绝分批排序[J]. 曲阜师范大学学报(自然科学版), 2007, 33(2):35-38.
[8] Lu L, Zhang L, Yuan J. The unbounded parallel batch machine scheduling with release dates and rejection to minimize makespan[J]. Theoretical Computer Science, 2008, 396(1-3):283-289.
[9] Lu L, Cheng T C E, Yuan J, et al. Bounded single-machine parallel-batch scheduling with release dates and rejection[J]. Computers & Operations Research, 2009, 36(10):2748-2751.
[10] Cao Z, Yang X. A PTAS for parallel batch scheduling with rejection and dynamic job arrivals[J]. Theoretical Computer Science, 2009, 410(27):2732-2745.
[11] He C, Leung Y T, Lee K, et al. Scheduling a single machine with parallel batching to minimize makespan and total rejection cost[J]. Discrete Applied Mathematics, 2016, 204:150-163.
