工件可拒绝的两个代理排序问题的全多项式时间近似方案

A Full Polynomial-time Approximation Scheme of Two-agent Scheduling with Job Rejection

本文研究单处理机上工件可拒绝的两个代理的排序问题.在此问题中,有两个代理A和B,分别有各自的工件集和费用函数.代理A的工件可以被接收,也可以被拒绝,但要支付一定的拒绝费用.代理B的工件要全部接收.代理A的费用函数是他的接收工件的最大完工时间与拒绝工件的拒绝费用之和,代理B的费用函数是他的工件的最大延迟.排序问题的目标是在满足代理B的费用函数不超过一定数量的前提下,使得代理A的费用函数达到最小.对于该问题给出了一个全多项式时间近似方案.

We consider a two-agent scheduling problem with rejection on a single machine.For the problem, we have two agents A and B and each agent has its own job set and cost function. A job of agent A is either accepted or rejected with a certain rejection penalty having to be paid. The jobs of agent B must be accepted. The cost function of agent A is the sum of the makespan of the accepted jobs and the total rejection penalty of the rejected jobs. The cost function of agent B is the maximum lateness. The objective of the scheduling problem is to minimize the cost function of agent A, given that the cost function of agent B does not exceed a fixed value. For this problem, we give a full polynomial-time approximation scheme.