带有拒绝工件和机器维修区间的单机排序问题-重庆师范大学学报.PDF

! #$ 年$$ 月 重庆师范大学学报（自然科学版） %’( #$ 第) 卷 第* 期 +,-./0 1 23.456.4 %-7/0 8.6’9-:6; （%/;,-/0 =69.9 ） ?0( ) %( * 运筹学与控制论 @AB ：2%CB ：D# E $$*DF %( #$$$$ ( $*G ( ##G 带有拒绝工件和机器维修区间的单机排序问题! 张敏娇，罗成新 （沈阳师范大学 数学与系统科学学院，沈阳$$##HG ） 摘要：考虑带有拒绝工件和机器维修区间的单机排序问题。目标是最小化被加工工件的总完工时间与被拒绝工件 的总惩罚（被拒绝加工的工件需要支付拒绝惩罚）的和。这个问题是一般意义下%IJ难的，因此需要快速寻找满足指 定精确度要求的近似解。为了能在较少的运行时间内得到该问题的较好的近似解，利用削减状态空间方法得到了 一个全多项式时间近似方案（KILM= ）。该KILM= 是一个具有强多项式运行时间的较优近似方案，其时间复杂性为 !（ # ），其中 为输入工件的个数，N # 为任意小的实数。 ! ! 关键词：单机排序；维修区间；拒绝工件；%IJ难；近似算法 中图分类号： A$( O 文献标志码：M! ! ! 文章编号：$*OJ **)H（#$ ）#*J ##$DJ #D 在以往的经典排序问题中基本上要求所有工件都被加工，不允许被拒绝，但在实际的生活中，为了满足 某种目的、达到一定利益可能会拒绝一部分工件。本文考虑的是机器在某固定区间需要维修且允许有拒绝 工件的单机排序问题。目标是最小化被加工工件的总完工时间与被拒绝工件的总惩罚的和。该问题在机器 可以连续加工的情况下（单机带有拒绝工件使被加工件的总完工时间与被拒绝工件的总惩罚的和最小的排 序问题即 ［$］ $ $%’ ( ) * ，其中$%’ 为允许带有拒绝工件）已被证明了是一般意义下%IJ难的 ，所以 ’ ’ 问题$，+ $%’ ( ) * （单机允许有机器维修任务（+ ）和拒绝工件（$%’ ），总目标函数为被加工件的总 ’ ’ 完工时间与被拒绝工件的总惩罚之和最小的排序问题）也是一般意义下%IJ难的。 在已有的文献中一部分研究的是机器有维修区间的典型单机排序问题，另一部分研究的是带有拒绝工 件的、机器没有维修区间的单机排序问题［JP ］。而本文则将这两种情况结合在一起，即研究带有拒绝工件和 机器维修区间的单机排序问题，对该问题给出了一个KILM= ，而算法运行时间为!（ # ! ）。 $ 问题描述 该问题是对单机上工件集, Q ｛$， ，…， ｝中的 个工件进行排序使得被加工工件的总完工时间与被拒 绝工件总惩罚的和最小。每个工件- , 的加工时间为. ，惩罚为/ 。机器在区间［0 ，0 ］需要维修且机器 # - - $ 在每一时刻至多加工一个工件。不失一般性，考虑所有数据都是正整数，并且将工件先按=IL 规则排好（即