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

年 月 重庆师范大学学报 自然科学版 　２０１２ １１ （ ） Ｎｏｖ．２０１２ 第 卷 第 期 ２９ ６ Ｊｏｕｒｎａｌ　ｏｆ　Ｃｈｏｎｇｑｉｎｇ　Ｎｏｒｍａｌ　Ｕｎｉｖｅｒｓｉｔｙ（Ｎａｔｕｒａｌ　Ｓｃｉｅｎｃｅ） Ｖｏｌ．２９ Ｎｏ．６ 运筹学与控制论 ＤＯＩ：ＣＮＫＩ：５０－１１６５／Ｎ ．１６４２．００４ 带有拒绝工件和机器维修区间的单机排序问题＊ 张敏娇，罗成新 沈阳师范大学 数学与系统科学学院 沈阳 （ ， １１００３４） 摘要：考虑带有拒绝工件和机器维修区间的单机排序问题。目标是最小化被加工工件的总完工时间与被拒绝工件 的总惩罚 被拒绝加工的工件需要支付拒绝惩罚 的和 这个问题是一般意义下 难的 因此需要快速寻找满足指 （ ） 。 ＮＰ－ ， 定精确度要求的近似解。为了能在较少的运行时间内得到该问题的较好的近似解，利用削减状态空间方法得到了 一个全多项式时间近似方案 该 是一个具有强多项式运行时间的较优近似方案 其时间复杂性为 （ＦＰＴＡＳ）。 ＦＰＴＡＳ ， 其中 为输入工件的个数 为任意小的实数 Ｏ（ｎ２／ε２）， ｎ ，ε＞０ 。 关键词 单机排序 维修区间 拒绝工件 难 近似算法 ： ； ； ；ＮＰ－ ； 中图分类号 文献标志码 文章编号 ：Ｏ２２１．７ ：Ａ　　　 ：１６７２－６６９３（２０１２）０６－００１５－０５ 在以往的经典排序问题中基本上要求所有工件都被加工，不允许被拒绝，但在实际的生活中，为了满足 某种目的、达到一定利益可能会拒绝一部分工件。本文考虑的是机器在某固定区间需要维修且允许有拒绝 工件的单机排序问题。目标是最小化被加工工件的总完工时间与被拒绝工件的总惩罚的和。该问题在机器 可以连续加工的情况下（单机带有拒绝工件使被加工件的总完工时间与被拒绝工件的总惩罚的和最小的排 序问题即 ，其中 为允许带有拒绝工件）已被证明了是一般意义下 难的［１］，所 １　ｒｅｃｊ ∑Ｃｊ ＋ ∑Ｗｊ ｒｅｃｊ ＮＰ－ 以问题 ， （单机允许有机器维修任务（ ）和拒绝工件（ ），总目标函数为被加工 １ ｈ　ｒｅｃｊ ∑Ｃｊ ＋ ∑Ｗｊ ｈ ｒｅｃｊ 件的总完工时间与被拒绝工件的总惩罚之和