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

• 作者: 崔倩娜
• 来源期刊: 计算机与数字工程
• 学科: 工学
• 关键词: 多重任务 惩罚费用 排序问题 近似算法 在线算法
• 年，卷（期）: 2019,（1）
• 所属期刊栏目: 算法与分析
• 页码范围: 99-104
• 页数: 6页
• 分类号: TP301.6
• 字数: 5951字
• 语种: 中文
• DOI: 10.3969/j.issn.1672-9722.2019.01.024

摘要

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

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	崔倩娜	云南大学数学与统计学院	2	0	0.0	0.0