APP下载

带有截止日期和拒绝的单机总加权误工量排序问题

2022-08-22赵玉芳何欣怡陈状状

关键词:排序规划

赵玉芳, 何欣怡, 陈状状

(沈阳师范大学 数学与系统科学学院, 沈阳 110034)

0 引 言

工件有截止日期的约束问题在实际问题中普遍存在[1-3],并且在传统的排序问题中,都假设每一个工件必须被加工。然而,在现实中决策者为了节省加工成本以获得更大的利益,会选择拒绝加工一部分工件而支付一定的费用。张玉忠[4]对工件可拒绝的排序问题进行了综述。Blazewicz[5]首先提出了误工量问题,称其为“信息丢失”,并介绍了极小化总加权误工量的排序模型。Sterna[6]对早期的误工量问题进行了综述。Potts和van Wassenhove[7]证明了单机总误工量排序问题和单机总加权误工量排序问题是一般意义NP-难的,并给出了拟多项式动态规划算法。同年,Potts和van Wassenhove[8]对单机总误工量排序问题又提出了2个FPTAS(fully polynomial time approximation scheme)算法。Wu等[9]研究了带有学习效应的总误工量问题,构造出一个分支定界算法并用遗传算法得到了近似最优解。对于极小化单机总加权误工量的排序问题,Kovalyov等[10]对单机总加权误工量排序问题提出了一个动态规划算法,并设计了一个FPTAS。Hariri等[11]在上述动态规划算法的基础上对这个问题提出了一个算法复杂度为O(n2∑pj)的拟多项式动态规划算法,对于工件的工期都相同的问题可以在O(n)时间内求解,当工件的加工时间相同时构造了一个算法复杂度为O(n3)的最优算法。Chen等[12]研究了工件具有加工位置上限的总加权误工量问题,证明了当工件具有相同工期时,问题是一般意义NP-难的,且构造了一个拟多项式动态规划算法,证明了当工件具有单位权重的时候,问题是强NP-难的。……

登录APP查看全文

猜你喜欢

排序规划
排排序
发挥人大在五年规划编制中的积极作用
恐怖排序
节日排序
刻舟求剑
规划引领把握未来
快递业十三五规划发布
多管齐下落实规划
十三五规划
迎接“十三五”规划