时间错位限制下最小化总完工时间的继列分批重新排序

郭 晓, 冯密罗, 慕运动

(1.河南工业大学 理学院 河南 郑州 450001； 2.郑州大学 数学系 河南 郑州 450001)

0 引言

工件错位即在原始排序中产生的错位限制下，最小化最大延误时间和总完工时间的单机重新排序问题[1]．Potts等[2-4]考虑了在单机情况下，分批排序的排序方法以及分批排序问题不同情况下的不同算法． Agnetis等[5]主要考虑的是具有两个代理和两个目标函数的最小化加权总完工时间等问题．Baker等[6]考虑了多准则模型的机器排序问题，且给出了多代理目标函数的线性组合时的结果．Yuan等[7-8]考虑了具有到达时间的最大序列或时间错位限制下的最小化最大完工时间的重新排序问题．根据Hall等[1]的描述，单机重新排序问题可表示为：令J0={J1,J2,…,Jn0}为单机上的原始工件集．在模型中，假定J0中的工件已经在最小化某一经典目标函数下最优地安排加工，且π*是一个最优序．令JN={Jn0+1,Jn0+2,…,Jn0+nN}为新工件集,记J=J0∪JN,J中的每一个工件Jj的加工时间为整数且满足pj≥0,π*和σ*分别表示J0和J工件的最优序．对于J的工件的任意排序σ，定义2个变量：Cj(σ)表示J中工件Jj在σ中的完工时间;Δj(π*,σ)=|Cj(σ)-Cj(π*)|表示J0中工件Jj的时间错位．在不引起混淆的前提下，上面的参数可以分别简化为Cj,Δj(π*)．需要说明的是，在继列分批排序中，由于同一批的工件的完工时间相同，因此,在同一批中工件没有先后次序之分．

在研究问题的过程中，主要考虑两个方面：第一，研究分批重新排序问题的可行排序和最优排序的结构性质；第二，基于这些性质设计问题的最优算法．本文证明了这些问题能在拟多项式时间内可解．

1 问题的性质

首先研究1|s-batch,Δmax(π*)≤k|∑Cj和|s-batch,∑Δj(π*)≤k|∑Cj两个问题的结构性质．

引理1对于问题1|s-batch,Δmax(π*)≤k|∑Cj，如果存在一个最优排序，使得J0中的工件在排序π*和σ*中具有相同的次序，那么一定存在工件间没有空闲时间的最优排序，使得排在J0最后一个工件所在批之前的JN中的工件加工时间之和不大于k．

证明因为在排序π*和σ*中J0中的工件具有相同的排序，移走排序σ*中的任何一个空闲时间仍能够保持其可行性，且∑Cj的数值不会增大．那么，该问题存在工件间没有空闲时间的最优排序．优先级指标序列排序原则表明,J0中的工件在排序π*和σ*中具有相同的次序．因此，Δmax(π*)的值是由排在J0最后一个工件之前的工件的加工时间之和决定的．

引理2对于问题1|s-batch,Δmax(π*)≤|∑Cj和1|s-batch,∑Δj(π*)≤k|∑Cj，都存在一个最优排序，满足J0中的工件与排序π*一样按照SPT序排列，JN中工件按照SPT序排列，且所有工件间没有空闲时间．

证明首先分析J0中的工件．假设最优排序σ*中J0的工件并没有与排序π*一样按照SPT序排列．令工件Ji是σ*中比排序π*中相对于J0的其他工件更靠后的具有最小指标的工件，工件Jj(j>i)为σ*中排在工件Ji之前的J0的一个工件，如果它们在同一批次中，显然不会增加∑Cj，所以主要讨论的是它们不在同一个批次中的情况．因为π*是一个SPT序列，所以有pi≤pj．通过相互交换σ*中工件Ji和Jj的位置得到一个新的排序，记为σ′，那么，Ci(σ′)=Cj(σ′)-pj+pi，Cj(σ′)=Ci(σ′)，且σ′中位于Ji和Jj所在批之间的各批工件都比σ*中提早完工pj-pi个单位时间．这样可知，通过这种互换JN中工件的完工时间不会增加，J0中的工件的时间错位不会超过k．如果σ′中工件Jj的位置不比π*中的位置靠前(与工件Ji的情形一样)，若Cj(σ′)≥Ci(σ′)，那么Δj(π*,σ′)<Δi(π*,σ*)；否则Δj(π*,σ′)<Δj(π*,σ*).这两种情形下，Δj(π*,σ′)=Δj(π*,σ*)-h′，Δj(π*,σ′)≤Δj(π*,σ*)+h′，其中,h′=Ci(σ*)-Ci(σ′)，都有Δmax(π*,σ′)≤Δmax(π*,σ*),∑Δi(π*,σ′)≤∑Δj(π*,σ*).因此，排序σ′是可行的且是最优的．重复上述有限次讨论可以说明一定存在与排序π*一样按照SPT序排列的最优序．显然，如果工件之间存在着空闲时间，减去相应的空闲时间，那么∑Ci肯定会减小，因此工件之间不存在空闲时间．

2 算法设计

对于问题1|s-batch,Δmax(π*)≤k|∑Cj，应用引理2的SPT序可以得到一个最优排序．下面的动态规划算法给出了满足最大时间错位限制下的最优组合方案．

算法1

标号：给JN中所有工件按照SPT规则标号；

值函数：f(i,j,t,δij)表示最大时间错位为δij时，部分排序的总完工时间的最小值，其中,i表示为J0的前i个工件，j表示为JN中的前j个工件，t表示当前工件的完工时间；

初值条件：f(0,0,0,0)=0；

定理1算法1在时间O(n0nNn(ns+PN))内给出了1|s-batch,Δmax(π*)≤k|∑Cj的最优排序．

证明由引理1，2可知，只要通过SPT规则把J0和JN的全部的情况给列出来，算法1通过比较所有的可能出现的情况，就可以得到最优排序．现在考虑算法1的时间复杂性，因为i≤n0,j≤nN,δ≤k≤ns+PN，t的计算次数最多为2n次，而给JN标号所需要的时间为nNlognN，而递推关系的变量所需要的时间为O(n0nNn(ns+PN))，因此算法1的时间复杂性为O(n0nNn(ns+PN)).

对于问题1|s-batch,∑Δj(π*)≤k|∑Cj，应用引理2的SPT序可以得到一个最优排序．下面的动态规划算法给出了满足总时间错位限制下的最优组合方案．

算法2

标号：给JN中所有工件按照SPT规则标号；

值函数：f(i,j,t,δ)表示总时间错位为δ的时候，部分排序总完工时间的最小值．其中i表示为J0的前i个工件，j表示为JN中的前j个工件，t表示当前工件的完工时间；

初值条件：f(0,0,0,0)=0；

其中,u表示工件Ji的时间错位，h0表示当前批中属于J0但是不与Ji在原始排序中分到同一批的工件个数，h1表示当前批中工件个数(不包含工件Ji)，h2表示当前批中属于J0的工件个数，h3表示当前批中工件个数(不包含工件Jj)．

定理2算法2在时间O(n0nNn(ns+min{n0PN,nNP0}))内给出了1|s-batch,∑Δj(π*)≤k|∑Cj的最优排序．

证明由引理2可知，只要通过SPT规则把J0和JN的全部的情况给列出来，算法2通过比较所有可能出现的情况，就可以得到最优排序．现在考虑算法2的时间复杂性，因为i≤n0,j≤nN,δ≤k≤ns+min{n0PN,nNP0}，t的计算次数最多为2n次．而给JN标号所需要的时间为nNlognN，而递推关系的变量所需要的时间为O(n0nNn(ns+min{n0PN,nNP0}))，因此算法2的时间复杂性为O(n0nNn(ns+min{n0PN,nNP0}))．

[1] Hall N G， Potts C N． Rescheduling for new orders[J]． Operations Research， 2004,52(3)：440-453．

[2] Potts C N，Kovalyov M Y． Scheduling with batching：A review[J]． European Journal of Operational Research,2000，120(2)：228-249．

[3] Brucker P，Gladky A,Hoogeveen H,et al． Scheduling a batching machine[J]．Journal of Scheduling,1998,1(1)：31-54．

[4] 赵永刚,李文华,豆俊梅.最小化时间表长和最大加工运输时间的单机继列批在线排序[J].郑州大学学报:理学版,2010,42(4):36-39.

[5] Agnetis A，Mirchandani P B，Pacciarelli D， et al．Scheduling problems with two competing agents[J]．Operations Research,2004,52(2)：229-242．

[6] Baker K R，Smith J C． A multiple-criterion model for machine scheduling[J]． Jounrnal of Scheduling， 2003，6(1)：7-16．

[7] Yuan Jinjiang， Mu Yundong． Rescheduling with release dates to minimize makespan under a limit on the maximum sequence disruption[J]．European Journal of Operational Research，2007，182(2)： 936-944．

[8] Yuan Jinjiang， Mu Yundong， Lu Lingfa，et al． Rescheduling with release dates to minimize total sequence disruption under a limit on the makespan[J]． Asia-Pacific Journal of Operational Research， 2007，24(6)：789-796．

[9] Brucker P．Scheduling Algorithms[M]．Berlin:Springer Verlag，2001．

[10]Graham R L，Lawler E L，Lenstra J K， et al．Optimization and approximation in deterministic sequencing and scheduling: A survey[J]． Annals of Discrete Mathematics,1979,5(2)：287-326．