2023年5月重庆师范大学学报(自然科学版)May2023第40卷第3期JournalofChongqingNormalUniversity(NaturalScience)Vol.40No.3运筹学与控制论DOI:10.11721/cqnuj20230308带有退化、拒绝和不可用区间的单机排序问题*何欣怡,赵玉芳,陈状状(沈阳师范大学数学与系统科学学院,沈阳110034)摘要:【目的】考虑带有退化工件、拒绝和不可用区间的单机排序问题。【方法】假设工件有不同的基本加工时间和相同的退化率,工件可以被拒绝,被拒绝的工件需要支付拒绝惩罚,机器在给定的时间区间内是不可用的且工件不可恢复。目标是极小化接受工件的总完工时间与被拒绝工件的总拒绝惩罚之和。【结果】对于这个NP-难问题,在不可用区间前、后,工件按照基本加工时间aj的非减顺序排列可以得到最优解,给出一个拟多项式时间动态规划算法和一个完全多项式时间近似策略。【结论】推广了已有文献的模型。关键词:单机排序;退化;拒绝;不可用区间中图分类号:O223文献标志码:A文章编号:1672-6693(2023)03-0008-08当前有关排序问题的理论研究已经涉及到很多实际生产环境中,例如在轧钢调度问题中,铸锭在等待加工时温度会下降,因此它需要被重新加热,让温度达到一定要求再进行轧制,由此导致轧制时间增加;而轧制过程中机器也可能因故障或检修等原因而不可用,此时工厂为了节约成本或按时交货,可能会选择外包一部分货品,进而支付一定费用。事实上,加工过程中由于中途维修机器或者更换工具等原因,导致一台机器在此时不可用的情形在工业中很常见,因此带有不可用区间约束的问题受到了广泛关注。Lee[1]定义了两种情况:可恢复和不可恢复。当工件在不可用区间之前没有完工,机器再次可用时继续加工,则称为可恢复的,反之为不可恢复的。Ma等人[2]对带有机器不可用区间的问题进行了综述。Zhao等人[3]研究了两台平行机排序问题,其中一台机器有一段固定的不可用区间,给出了这个问题的完全多项式时间近似策略(fullypolynomialtimeapproximationscheme,FPTAS)。Zhao等人[4]研究了平行机的情况,每台机器都有一个固定的不可用区间,提出了一个拟多项式时间动态规划算法。Kacem等人[5]研究了两个目标函数为最大延误的单机排序问题,且工件带有释放时间,其中一个问题是机器在一个给定的区间中不可用,另一个问题是与操作员有关的不可用区间,他们分别给出了这两个问题的多项式时间近似策略(polynomial-timeapproximationscheme,PTAS)算法。金苗苗等人[6]研究了机器具有不可用区间且工件可拒绝下的单机重新排序问题,目...
