带有拒绝工件的公共窗口指派单机排序问题

徐景孝，吕丹阳，王吉波

(沈阳航空航天大学 理学院,沈阳 110136)

在以往的排序问题中，一般假设所有的工件(也叫任务或作业)都需要被加工。然而，为了降低制造成本，获得更大利润，工件加工商往往选择拒绝加工一些制造时间(成本)长、利润小的工件，这就是具有拒绝工件的排序问题。Bartal等[1]研究了工件可拒绝的平行机排序问题。Chen等[2]证明了带有拒绝工件的流水作业问题中的最大完工时间问题是NP难的。对于此问题，他们给出了3种近似算法，并对复杂性进行了分析。Koulamas等[3]研究了在公共工期条件下带有拒绝工件的单机排序问题，他们对总延误和总加权延误问题分别给出了2个问题的NP-难证明，并给出了一种改进的近似算法和启发式算法。王晓丹等[4]提出了带有恶化和拒绝工件的工期指派的单机排序问题的多项式时间算法。慕迪等[5]研究了带有拒绝和到达时间的单机排序问题，目标函数是最小化接受工件的最大完工时间与所有被拒绝工件的拒绝费用之和，他们给出了一个分支定界算法，并做了数值模拟。张玉忠[6]对各类拒绝工件的排序问题进行了综述。

另一方面，拒绝工件是有限度的，不能无限制拒绝加工。如果经常拒绝加工工件，不仅会使企业效益降低，也会使制造商的信誉下降。因此，为了避免这种情况，制造商希望在被拒绝的工件总拒绝惩罚不能超过给定上限的约束条件下，最小化给定的标准。这时就需要一个上限进行约束，使得拒绝工件总费用不得超过这个上限。刘晓霞等[7]研究了工件有到达时间且拒绝工件总个数受限的单机平行分批排序问题，给出了所有工件到达时间都相同时的近似算法。Zhang等[8]证明了带有拒绝上限的排序问题中的最大延误、总完工时间以及总提前延误都是强NP-难的，并给出了在拒绝上限有限制下的最大延误和最大完工时间问题的拟多项式时间算法。Mor等[9]研究了在共同工期和拒绝上限条件限制下的总提前延误和总加权提前延误的单机排序问题。Gerstl等[10]讨论了一般工期下带有拒绝的单机排序问题中的最大延误问题，并给出了基于二划分问题的NP-难证明。国峰等[11]研究了具有拒绝工件和学习效应的资源分配单机排序问题，在线性资源和凸资源约束下，证明了一类正则目标函数是多项式时间可解的。

本文考虑具有位置权重和可拒绝的公共窗口指派单机排序问题，目标函数包括工件的提前/延误量、窗口开始时间、窗口大小的线性加权和以及拒绝费用，其中权重只与工件被排在序列中的位置有关，即位置权重。本文给出了最优解满足的一些性质，在拒绝工件个数为给定的情况下，证明了最优排序问题可以转化成指派问题进行求解，从而证明这个问题是多项式时间可解的，并做了算法复杂性分析。

1 问题描述

(1)

最小，其中α是窗口开始时间的权重，β是窗口大小的权重。

用三参数表示法，本文所研究的问题可以记为

(2)

2 主要结果

性质1存在一个最优排序，加工的工件集合A中，第一个工件从0时刻开始加工，且工件间无空闲时间。

证明性质1显然成立。

性质2 存在一个最优排序，公共窗口的开始时间d1和公共窗口的结束时间d2分别为某个工件的完工时间，即d1=C[k]，d2=C[l]，其中k和l为最优排序中工件的某个位置，且k≤l。

证明：证明分为以下3种情况。

(1)情况一

存在一个最优排序σ=[J1,J2,…,Jh]，d1不是序列中某个工件的完工时间，而d2是某个工件的完工时间，即C[k]

这就说明窗口开始时间为某个工件的完工时间时，最优排序存在。

(2)情况二

存在一个最优排序σ=[J1,J2,……，Jh]，d2不是序列中某个工件的完工时间，而d1是某个工件的完工时间，即C[l]

这就说明窗口结束时间为某个工件的完工时间时，最优排序存在。

(3)情况三

存在一个最优排序σ=[J1,J2,……，Jh]，d1、d2都不是序列中某个工件的完工时间，即C[k]

(3)

其中

(4)

证明对于任意排序σ=[J1,J2,……，Jh]，由性质1和性质2可知机器没有空闲且d1=C[k]，d2=C[l]，则目标函数可以化简为

(5)

其中

由引理1可知，一旦接受工件集A中的工件数目确定，则提前和延误工件已知，这时候λi就与工件的加工顺序无关，故有以下结论。

证明若接受工件集A中的工件数为h，即|A|=h，由引理2可知k、l的值，从而提前工件和延误工件随之确定。将提前工件排在前k个位置，延误工件排在中间(h-l)个位置，其余工件放最后，由引理2，定义

(6)

为工件Jj,(j=1,2,…,n)排在第r个位置上的费用。假设一个变量Xjr，如果工件Jj排在第r个位置上，则Xjr=1，否则Xjr=0。则问题可归结为如下的指派问题。

(7)

(8)

(9)

Xjr∈{0,1},j=1,2,…n,r=1,2,…,n

(10)

算法1

步骤 1：给定h的值(h=0,1,2,…,n)，根据引理1计算k、l的值；

步骤 2：由引理2求λi的值；

步骤 3：根据定理1求得Wjr的值；

步骤 4：通过求解指派问题得出F(h)。

步骤 5：最优的目标函数值为min{F(h)|h=0,1,2,…,n}。

证明在算法1中，对于每一个给定的h，步骤1、2、3都可以在O(n)时间得到，步骤4(指派问题)的复杂性为O(n3)。h的范围为h=0,1,2,…,n，所以算法1总的时间复杂性为O(n4)。

例1考虑6个工件的集合J={J1,J2,J3,J4,J5,J6}，窗口开始时间权重α为10，窗口大小权重β为30，其他参数见表1。

表1 例1的数据

解

①当h=0时，此时接受工件集中的工件数为0，即所有工件均被拒绝，产生的费用为所有拒绝费用和，F(0)=1 116。

②当h=1时，由步骤1可得k=1,l=0，由步骤2可得λi=[10,0,0,0,0,0]，步骤3得指派问题的系数矩阵，通过求解指派问题得最优排序为[J1]，拒绝工件为J2,J3,J4,J5,J6，目标函数最优值为1 096，详见表2，黑体为最优值解。

表2 指派问题系数矩阵

表3 接受工件数h=2,…,6的结果

由以上实验结果可得，当h=1时，目标函数最优。

3 结论

本文研究了具有公共交货期窗口和工件可拒绝的单机排序问题。所有工件被分成2个工件集，即接受工件集和拒绝工件集。在接受的工件中共享一个公共交货期窗口，在窗口内完工的工件不会产生任何额外费用，否则都将会产生提前或延误惩罚。拒绝工件集里的工件会产生拒绝费用。证明了此问题存在最优的多项式时间算法。以后的研究可以考虑学习效应[12]、恶化效应[13]和拒绝工件结合在一起的情况，目标函数是具有位置权重的窗口排序问题Wang等[14]和Sun等[15])。