带有退化工件和机器维修区间的单机排序问题.PDFVIP

第 卷 第 期 沈阳师范大学学报 自然科学版 ３１ 　 ３ （ ） Ｖｏｌ．３１Ｎｏ．３ 年 月 ２０１３ 　７ Ｊｏｕｒｎａｌ　ｏｆ　Ｓｈｅｎｙａｎｇ　Ｎｏｒｍａｌ　Ｕｎｉｖｅｒｓｉｔｙ （Ｎａｔｕｒａｌ　Ｓｃｉｅｎｃｅ） Ｊｕｌ．２０１３ 文章编号 ：１６７３－５８６２（２０１３）０３－０３４８－０５ 带有退化工件和机器维修区间的单机排序问题 张敏娇，罗成新 沈阳师范大学 数学与系统科学学院 沈阳 （ ， 　１１００３４） 摘 要 考虑的是机器需要维护 且需要对若干个退化工件进行加工的单机排序问题 所谓 　　　 ： ， 。 退化情况是指每个工件的加工时间是关于它本身的开始时间的一个线性单增函数。该问题中工 件允许被拒绝，如果工件被拒绝，那么需要支付拒绝惩罚；如果被加工，那么工件被排在机器上（机 器需要在某一个固定的时间段内进行维修以提高其加工速度，且在这段时间内机器不能加工任何 工件）进行加工。目标是寻找一个最优排序使得被加工工件的总完工时间与被拒绝工件的总惩罚 之和最小。对于单机情形，利用划分程序的方法给出了一个全多项式近似方案，并得出该近似 方 案的时间复杂性 说明该问题是一般意义下 难的 ， ＮＰ－ 。 关 键 词 拒绝工件 退化 全多项式近似方案 维修区间 排序 　 　 ： ； ； ； ； 中图分类号 文献标志码 ：Ｏ２２３　　　　 ：Ａ ｄｏｉ：１０．３９６９／ｊ．ｉｓｓｎ．１６７３－５８６２．２０１３．０３．００８ 在经典排序问题［ ］中 工件的加工时间都是常值且机器连续加工 但在实际生产中 工件的加工时 １－２ ， ， ， 间可能会因等待时间过长而使工件退化，或是机器需要在一段时间内进行维修以提高他的工作效率。 对于带有拒绝工件和释放时间的单机排序问题已由文献 给出全多项式近似方案 并且有较好 ［３－４］ ， 的时间复杂性 带有退化工件的排序问题由文献 利用文献 的方法在较好的时间复杂性下给出 。 ［５－６］ ［７］ 一全多项式近似方案 文献 对此排序问题也进行了相应的研究 并给出相应的算法 文献 对 ， ［５－１５］