摘要
研究了一类工件排序与转包关联的模型,即工件既可以在制造商的同类机上加工,也可以较高费用转包给某个承包商加工.需要确定被转包的工件集,以及未转包工件的加工顺序,使得工件加工与转包费用在工件最大完工时间满足限制条件下达到极小.证明了该问题的NP困难性,用数学规划方法构造多项式时间近似算法,并分析算法性能比.
In this paper, a model on joint decisions of subcontracting and detailed orders scheduling is considered. In this model an order can be either processed by uniform machines at the manufacturer in-house or subcontracted to one of the several available subcontractors possibly for processing at a high cost. The manufacturer needs to determine which orders should 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.
出处
《系统科学与数学》
CSCD
北大核心
2012年第1期53-61,共9页
Journal of Systems Science and Mathematical Sciences
基金
国家自然科学基金(70731160015)
江苏省自然科学基金(yw06037)资助课题
关键词
排序
转包
同类机
近似算法.
Scheduling, subcontracting, uniform machine, approxiamation algorithm.
