摘要
提出带惩罚费用的多重任务排序问题,即每个用户提交多个加工时间和惩罚费用相同的任务。每个用户提交的任务要么全部被接受,并被安排在平行机上处理,或者全部被拒绝,并产生惩罚费用。目标是寻找一个排序方案,使得机器的最大完工时间与所有被拒绝用户的惩罚费用之和最小。设计了一般情形下的一个强多项式时间2-近似算法和机器数为固定常数时的一个全多项式时间近似方案。特别地,当机器数为2时,设计了一个竞争比为1.618的最优在线算法。
Multi-task scheduling problem with rejection is proposed,in which each user submits multiple tasks with the same processing time and penalty cost.All tasks submitted by each user are either accepted and processed by the machines,or rejected,in which case its penalty cost is paid.The objective is to minimize the sum of the makespan and the total penalty cost of the rejected tasks.A 2-approximation algorithm is presented in strongly polynomial time for the general case and a full polynomial time approximation scheme when the number of machines is fixed.Especially,when the number of machines is 2,an optimal online algorithm is designed with a competitive ratio of 1.618.
作者
崔倩娜
CUI Qianna(School of Mathematics and Statistics,Yunnan University,Kunming 650000)
出处
《计算机与数字工程》
2019年第1期99-104,共6页
Computer & Digital Engineering
基金
国家自然科学基金(编号:61662088)
云南省自然科学基金(编号:2014FB114)
IRTSTYN资助
关键词
多重任务
惩罚费用
排序问题
近似算法
在线算法
multiple tasks
rejection
scheduling problem
approximate algorithm
online algorithm
