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