计算机与数字工程2019，Vol.47Issue(1)：99-104,6.DOI:10.3969/j.issn.1672-9722.2019.01.024
带惩罚费用的多重任务排序问题∗
Multi-task Scheduling Problem with Rejection
摘要
Abstract
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 approxi?mation 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.关键词
多重任务/惩罚费用/排序问题/近似算法/在线算法Key words
Key Words multiple tasks/rejection/scheduling problem/approximate algorithm/online algorithm分类
信息技术与安全科学引用本文复制引用
崔倩娜..带惩罚费用的多重任务排序问题∗[J].计算机与数字工程,2019,47(1):99-104,6.基金项目
国家自然科学基金(编号:61662088) （编号:61662088）
云南省自然科学基金(编号:2014FB114)和IRTSTYN资助. （编号:2014FB114）
