单机上一个与总完工时间及最大完工时间相关的工件可拒绝的ND双代理排序问题  

An ND two-agent scheduling problem with rejection on a single machine related to the total completion time and makespan

作　　者：葛晴 录岭法 原晋江 张利弄 GE Qing;LU Lingfa;YUAN Jinjiang;ZHANG Liqi(Schoolof Mathematics and Statistics,Zhengzhou University,Zhengzhou 450001,Henan,China;College of Information and Management Science,Henan Agricultural University,Zhengzhou 450003,Henan,China)

机构地区：[1]郑州大学数学与统计学院,河南郑州450001 [2]河南农业大学信息与管理科学学院,河南郑州450003

出　　处：《运筹学学报(中英文)》2024年第4期66-74,共9页Operations Research Transactions

基　　金：国家自然科学基金(Nos.12271491,12471305,12071442,12371318)。

摘　　要：本文我们考虑单机上工件可拒绝的ND双代理排序问题。在该问题中,假设有两个代理A和B他们的工件集合分别记为J^(A)和J^(B)。在经典的CO双代理排序模型中,总是假设两个代理之间是竞争的,即J^(A)∩J^(B)=Ф。而在ND双代理排序问题中,我们允许两个代理有共同的工件,即允许J^(A)∩J^(B)≠Ф。在工件可拒绝排序中,每个工件或者被接收并安排在机器上进行加工,或者被拒绝并支付一个对应的拒绝费用。在本文中,我们研究了工件可拒绝的ND双代理排序问题。特别地,我们考虑了一个约束型排序问题。即在满足代理B接收工件的最大完工时间C_(max)^(B)与拒绝工件的总拒绝费用之和不超过一个给定的正整数Q的前提下,我们的目标是最小化代理A中接收工件的总完工时间∑C_(j)^(A)与拒绝工件的总拒绝费用之和。对该问题,我们给出了一个拟多项式时间算法以及一个全多项式时间近似方案。In this paper,we consider the ND two-agent scheduling problem with rejection on a single machine.In this problem,there are two agents A and B and the job sets of them are denoted by J^(A) and J^(B) respectively.In the classical CO two-agent scheduling,two agents are competitive,i.e.,J^(A)∩J^(B)=Ф.However,in the ND twoagent scheduling,two agents may have common jobs,i.e.,J^(A)∩J^(B)=Ф is allowed.In scheduling problems with rejection,each job is either accepted and processed on the machine,or rejected by paying a corresponding rejection cost.In this paper,we study the ND two-agent scheduling with rejection.In particular,we consider a constrained scheduling problem.That is,the objective is to minimize the sum of the total completion time ∑C_(j)^(A) of accepted A-jobs and the total rejection cost of rejected A-jobs subject to an upper bound Q on the sum of the makespan C_(max)^(B) of accepted B-jobs and the total rejection cost of the rejected B-jobs.For this problem,we provide a pseudo-polynomialtime algorithm and a fully polynomial-time approximation scheme.

关 键 词：排序 ND双代理 拒绝费用 拟多项式时间算法 全多项式时间近似方案 

分 类 号：O221.7[理学—运筹学与控制论]