研究了一类工件排序与转包关联的模型, 即工件既可以在制造商的同类机上加工, 也可以较高费用转包给某个承包商加工.需要确定被转包的工件集, 以及未转包工件的加工顺序, 使得工件加工与转包费用在工件最大完工时间满足限制条件下达到极小. 证明了该问题的NP困难性, 用数学规划方法构造多项式时间近似算法, 并分析算法性能比.

In this paper, a model on joint decisions of subcontracting and detailed orders cheduling is considered. In this model an order can be either processed by uniform machinest the manufacturer in-house or subcontracted to one of the several available subcontractors ossibly for processing at a high cost. The manufacturer needs to determine which orders hould be produced in-house and which orders should be subcontracted. Furthermore, it needs to determine a production schedule for orders to be produced in-house. The objective is to minimize the total production and subcontracting cost, subject to a constraint on the maximum completion time of the orders. The computational complexity of the model is analyzed, an approximation algorithm by using mathematical programming is developed and its worst-case and asymptotic performance are given.