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