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

赵玉芳, 何欣怡, 陈状状

(沈阳师范大学 数学与系统科学学院, 沈阳 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-难的。Chen等[1]首次研究了工件有截止日期的问题,证明了带有截止日期约束且工件工期相同时,总加权误工量单机排序问题是一般意义NP-难的,并构造了一个拟多项式动态规划算法和一个FPTAS。

拒绝的概念首先由Bartal等[13]提出,此后得到了学者们的广泛关注。Engels等[14]研究了带有拒绝的单机排序问题,目标函数为接受工件的总加权完工时间与拒绝工件的总拒绝惩罚之和,证明了其是NP-难的,并给出了动态规划算法和FPTAS。Cheng和Sun[15]考虑了带有退化和拒绝的单机排序问题,目标函数为接受工件的最大完工时间与拒绝工件的总拒绝惩罚之和,证明了该问题是一般意义NP-难的,并给出了拟多项式时间动态规划算法。国峰和王吉波[16]研究了带有拒绝工件和学习效应的资源约束排序问题,对线性和凸资源分配函数的2种模型给出了最优求解算法,时间复杂度分别为O(n4)和O(n3)。

本文研究在截止日期的限制下,工件是可拒绝且工期都相同的总加权误工量与拒绝惩罚之和的单机排序问题。

1 问题描述

2 可行性检验

3 主要结论

下面构造一个拟多项式算法来求解这个NP-难问题。与文献[7]和[17]中提出的方法类似,可以通过依次选取关键工件或者依次列举关键工件的完工时间,再从所有的可行解中选择最优解。

对于问题P(J(c))的可行排序如图1所示。

图1 可行排序Fig.1 Feasible schedules

性质1 问题P(J(c))存在一个最优排序,排在J(c)之前的工件从0时刻开始以任意顺序连续加工且无空闲时间。

性质2 对于问题P(J(c)),存在一个最优排序σ,排在J(c)之后的工件按截止日期不减的顺序排列,即按照它们的下标顺序排列。

注意到工件Jj共有3种排序情况:

动态规划算法DP1:

Step 1 对于j∈{1,2,…,n-1}和τ∈{0,1,…,d},有

定理2 动态规划算法DP1的时间复杂性为O(n2d)。

证明 因为j∈{1,2,…,n-1},τ∈{0,1,…,d},Step 1的运行时间为O(nd),Step 2计算函数δ时j最多可以取遍{1,2,…,n-1},运行时间为O(n),因此动态规划算法DP1在O(n2d)时间内运行。

引理1 问题P(J(c))的最优解为

(1)

Step 1 将工件按照截止日期的不减顺序重新标号。指定J1∈J作为关键工件,记为问题P(J(1)),k=1。

定理3 动态规划算法DP2的时间复杂性为O(n3d)。

4 数值例子

求得WY(c)=9 ,工件排序为{J4,J2,J3,J(c)}或者{J4,J3,J(c)}。

2) 依次选取J2,J3,J4作为关键工件的情况同上。

5 结 论

本文研究了带有截止日期和工件可拒绝的极小化总加权误工量与拒绝惩罚之和的单机排序问题,该问题是NP-难的,用依次选取关键工件的方法构造了一个拟多项式时间动态规划算法,并证明了该算法的时间复杂度是O(n3d)。对于此问题的后续研究,如考虑不同机器环境下的平行机、恒速机等同一目标函数的其他问题,或者考虑当工件有单位权重时总加权误工量与拒绝惩罚之和的问题,或研究允许中断的情况等问题,都值得进一步探讨。