一类带外包选择的单机排序问题

• 作者: 刘丽 叶飞浪 陈光亭
• 来源期刊: 杭州电子科技大学学报（自然科学版）
• 关键词: 排序 外包 动态规划 近似算法
• 年，卷（期）: 2016,（1）
• 页码范围: 90-92
• 页数: 3页
• 分类号: O221.7
• 语种: 中文
• DOI: 10.13954/j.cnki.hdu.2016.01.018

摘要

研究了一类带外包选择的单机排序问题。假设仅有一台本地机器和一个外包承包商，每个工件既可以在本地机器上加工又可以外包商处加工。本地加工的费用为总误工工件数，外包加工的费用与外包工件有关。对于极小化总加工费用这一 NP 难问题，给出伪多项式时间动态规划算法。如果外包费用正比于外包工件的加工时间，设计出近似算法并给出最坏情况分析。

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	陈光亭	杭州电子科技大学理学院	44	74	5.0	7.0
2	刘丽	杭州电子科技大学理学院	3	6	1.0	2.0
3	叶飞浪	杭州电子科技大学理学院	1	0	0.0	0.0