带惩罚费用的多重任务排序问题

摘要

提出带惩罚费用的多重任务排序问题,即每个用户提交多个加工时间和惩罚费用相同的任务.每个用户提交的任务要么全部被接受,并被安排在平行机上处理,或者全部被拒绝,并产生惩罚费用.目标是寻找一个排序方案,使得机器的最大完工时间与所有被拒绝用户的惩罚费用之和最小.设计了一般情形下的一个强多项式时间2-近似算法和机器数为固定常数时的一个全多项式时间近似方案.特别地,当机器数为2时,设计了一个竞争比为1.618的最优在线算法.