叶飞浪,刘　丽,陈光亭

(杭州电子科技大学理学院，浙江 杭州 310018)



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

叶飞浪,刘丽,陈光亭

(杭州电子科技大学理学院，浙江 杭州 310018)

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

排序；外包；动态规划；近似算法

0　引　言

设有n个工件、一台本地机器及一个外部承包商，工件既可以在本地机器上加工，又可以选择外包加工，上述问题称为带外包选择的排序问题[1].文献[1]提出并对问题进行定性分析，文献[2-5]研究本地机器为多台平行机的情形，文献[6-8]研究本地机器为单台机情形.这些文献都假设本地机器的费用为工件的最大完工时间，而本文考虑本地加工的费用为总误工工件数，并假定外包加工的费用与外包工件相关.研究目标为极小化总加工费用的排序问题，由于在外包费用足够大时该问题等价于经典背包问题，因此显然是NP-困难的.假设工件Jj的加工时间为pj(正整数)，交工期为dj，外包费用为qj.记Jj的完工时间为Cj，如果Cj>dj，此时工件延误，记Uj=1；否则工件不延误，记Uj=0.若以I和O分别表示本地和外包加工工件的集合，……