考虑了工件有到达时间且拒绝工件总个数不超过某个给定值的单机平行分批排序问题.在该问题中，给定一个工件集和一台可以进行批处理加工的机器.每个工件有它的到达时间和加工时间；对于每个工件来说要么被拒绝要么被接受安排在机器的某一个批次里进行加工；一个工件如果被拒绝，则需支付该工件对应的拒绝费用.为了保证一定的服务水平，要求拒绝工件的总个数不超过给定值.目标是如何安排被接受工件的加工批次和加工次序使得其最大完工时间与被拒绝工件的总拒绝费用之和最小.该问题是NP-难的，对此给出了伪多项式时间动态规划精确算法，2-近似算法和完全多项式时间近似方案.
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.
[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.
