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

摘要：

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

关键词：排序、外包、动态规划、近似算法

分类号：O221.7(运筹学)

资助基金：国家自然科学基金资助项目11571252，11201105

在线出版日期：2016-04-11（万方平台首次上网日期，不代表论文的发表时间）

页数：共3页

页码：90-92