王柏琳等：安装时间和机器受限的订单接受与并行机调度 ·531· n}};Ⅱ={π：li=1,…,m},其中π：为机器i的订单 综上，当ej,≤0仙T时，若π：(k)为机 序列，T:(k)为π：的第k个订单，|T:I为π：包含的 器i的首/末订单或满足△k≥0，则拒绝π：(k)有 订单数量.若y狱=1则T:(k)=方.给定RS,Ⅱ)，完 F' 工时间C可按式计算. 定理2.给定初始调度。={m1},若m C(D)=Pi() {p,}≥max{s}-2min{s}（i),则对于由Ⅱo C)=Crk-)+sim-)m(+Pa因’ j.kem k=2,…,lT:l,i=1,2,…,m (11) 衍生出来的任何决策对RS,Ⅱ)，拒绝满足r©j仙≤ 因此，问题求解的关键在于如何确定决策对 0,T,(困的订单T:(k)均不会使总成本增加，即 F≤F RS,Ⅱ〉，对此本文采用如下策略：首先，不考虑订 单拒绝，生成包含所有工件的初始调度，记为；进 证明：因为RS,T)是由Ⅱ。得到的，有π：二π 而，根据完工时间等参数来确定拒绝订单集合.显 (Hi),因此min{pg}≥min{Pg},marx{st}≤max JcnI jcm jke j.kem 然，一个初始调度能够衍生出2”个决策对RS,Ⅱ)， {s},min{s球}≥min{s},进而min{pg}≥max jkem j.ke jeal jkem 若将其中成本最低的称为°的最好解，则问题最 {s}-2min{s}.所以，对于Vi,当1<k<lπ：I 优解必然存在于所有初始调度的最好解之中.因 时，式(12)成立 此，基于此策略的算法是可行的，而其有效性取决于 基于调度的订单拒绝策略，本节将探讨这一问题 △g=Pm,因-Sia,k-)mt+1)+S,k-1）m因+ 2.1订单拒绝的相关性质 sw:(+w≥min{p}-max{s}+2min{s}≥0 本节将分析拒绝一个订单对总成本的影响.给 (12) 定决策对RS,Ⅱ)，总成本为F:〈RS,Ⅱ〉是拒绝订 根据定理1，当k=1或|π：1或满足△4≥0时，新 单π：(k)的新决策对，即RS=RSU{T:(k)},π= 决策对RS,Ⅱ)满足F≤F,定理2成立 π：1{m:(k)},总成本为F;定义△：=P因+ 2.2列表拒绝与拒绝规则 (s-D,因+5，国=+D一5-=+)），其中k= 对于订单拒绝决策，本节提出一种基于初始调 2,…,lπ：1-1，i=1,2,…,m,则定理1成立 度Ⅱ。的列表拒绝方法，即以加工序列π∈Ⅱ。(i= 定理1.若订单T:（k)满足rejW≤0( 1,…,m)为列表，依次确定是否拒绝当前订单，其 Tw,且π：(k)为机器i的首/宋订单或满足△≥0， 中，针对当前订单的订单拒绝规则是列表拒绝方法 则拒绝π：(k)不会导致总成本增加，即F≤F 的关键 证明：由于rej,仙≤0仙T份’T:(k)满足fW≤ 假设订单π()为当前待定的订单，π：为机器 f·如果jS均满足≤，则有F≤F.下面 i上已确定接受的订单序列，显然π：中的订单均位 于π(k)之前加工，即1π1<k.式(13)(14)定义了 将证明这点 (1)拒绝订单T:()不会影响其他机器的订单， π(k)的当前完工时间C和拖期T9,其中π： 也不影响在其之前加工的订单.即，对于jRSU (Iπ：I)为机器i上最新被接受的订单编号.显然若 π：和j∈{π：(1)，…，π：(k-1)},有f=f 订单π(k)被接受，则其紧前订单为π：(1π：I) (2)l=k+1,…,|T:时f0和f,0关系如下： TC》+sm,lW)+p.因，ifT:≠⑦ C= ①若k=1,则C2)=Pm,0+s,m2)+Pa(2’ Pi.m(因’ otherwise C(2)=Pim(2C(0-C(0)=C(2)-C(2)<0(= (13) 2,,lml).因此f0≤fw,F≤F. T=max (C-d,0} (14) ②若k=|π：1，则拒绝π：()不会影响所有接受 根据定理1，本节提出了订单拒绝规则Rulel.. 订单，因此F-F=f仙-f的≤0. Rle1.若rejP≤0TP,并且以下情况 ③若1<k<|π：1，则Ck+)=Ck-)+ 之一成立，则拒绝订单π(k): Sm,-)r因+Pm,因+sm,(因m,+)+Pmk+),Ck+)= (a)m:=☑：(b)k=|πI:(c)△k=Pw+ C4-)+5a4-+D+Pa+,因此C4+)- （s,rm),9因+S份9k+)-5a山9+1)）≥0 C4+D=-△·当△≥0，有C,4+)≤C,u+),此时 根据定理1可知，给定初始调度Ⅱ。，采用基于 l=k+1,…,1m:1,订单π：(1)完工时间将提前 Rule1的列表拒绝方法，得到的最终决策对RS,I) △k,因而f0≤f0,F≤F. 的总成本必然不大于（⑦，Ⅱ。〉的总成本.此外，根王柏琳等: 安装时间和机器受限的订单接受与并行机调度 n} } ; Π = { πi | i = 1，…，m} ，其中 πi 为机器 i 的订单 序列，πi ( k) 为 πi 的第 k 个订单，| πi | 为 πi 包含的 订单数量． 若 yijk = 1 则 πi ( k) = j． 给定〈ＲS，Π〉，完 工时间 Cj 可按式计算． Cπi ( 1) = piπi ( 1) ; Cπi ( k) = Cπi ( k － 1) + siπi ( k － 1) πi ( k) + piπi ( k) ， k = 2，…，|πi |，i = 1，2，…，m ( 11) 因此，问题求解的关键在于如何确定决策对 〈ＲS，Π〉，对此本文采用如下策略: 首先，不考虑订 单拒绝，生成包含所有工件的初始调度，记为 Π0 ; 进 而，根据完工时间等参数来确定拒绝订单集合． 显 然，一个初始调度能够衍生出 2n 个决策对〈ＲS，Π〉， 若将其中成本最低的称为 Π0 的最好解，则问题最 优解必然存在于所有初始调度的最好解之中． 因 此，基于此策略的算法是可行的，而其有效性取决于 基于调度的订单拒绝策略，本节将探讨这一问题． 2. 1 订单拒绝的相关性质 本节将分析拒绝一个订单对总成本的影响． 给 定决策对〈ＲS，Π〉，总成本为 F; 〈ＲS'，Π'〉是拒绝订 单 πi ( k) 的新决策对，即 ＲS' = ＲS∪{ πi ( k) } ，π' i = πi \ { πi ( k ) } ，总 成 本 为 F'; 定 义 Δk = piπi ( k) + ( siπi ( k － 1) πi ( k) + siπi ( k) πi ( k + 1) － siπi ( k － 1) πi ( k + 1) ) ，其中 k = 2，…，|πi | － 1，i = 1，2，…，m，则定理 1 成立． 定理 1． 若 订 单 πi ( k ) 满 足 rejπi ( k) ≤ wπi ( k) Tπi ( k) ，且 πi ( k) 为机器 i 的首/末订单或满足 Δk≥0， 则拒绝 πi ( k) 不会导致总成本增加，即 F'≤F． 证明: 由于 rejπi ( k) ≤wπi ( k) Tπi ( k) ，πi ( k) 满足 f'πi ( k) ≤ fπi ( k) ． 如果jＲS'均满足 f'j≤fj ，则有 F'≤F． 下面 将证明这点． ( 1) 拒绝订单 πi ( k) 不会影响其他机器的订单， 也不影响在其之前加工的订单． 即，对于 jＲS'∪ πi 和 j∈{ πi ( 1) ，…，πi ( k － 1) } ，有 f'j = fj ． ( 2) l = k + 1，…，|πi |时，f'πi ( l) 和 fπi ( l) 关系如下: ①若 k = 1，则 Cπi ( 2) = piπi ( 1) + siπi ( 1) πi ( 2) + piπi ( 2) ， C'πi ( 2) = piπi ( 2) ，C'πi ( l) － Cπi ( l) = C'πi ( 2) － Cπi ( 2) ＜ 0( l = 2，…，|πi | ) ． 因此 f'πi ( l) ≤fπi ( l) ，F'≤F． ②若 k = |πi |，则拒绝 πi ( k) 不会影响所有接受 订单，因此 F' － F = f'πi ( k) － fπi ( k) ≤0． ③若 1 ＜ k ＜ | πi |，则 Cπi ( k + 1) = Cπi ( k － 1) + siπi ( k － 1) πi ( k) + piπi ( k) + siπi ( k) πi ( k + 1) + piπi ( k + 1) ，C'πi ( k + 1) = Cπi ( k － 1) + siπi ( k － 1) πi ( k + 1) + piπi ( k + 1) ，因 此 C'πi ( k + 1) － Cπi ( k + 1) = － Δk ． 当 Δk≥0，有 C'πi ( k + 1) ≤Cπi ( k + 1) ，此时 l = k + 1，…，| πi |，订单 πi ( l) 完工时间将提前 Δk，因而 f'πi ( l) ≤fπi ( l) ，F'≤F． 综上，当 rejπi ( k) ≤wπi ( k) Tπi ( k) 时，若 πi ( k) 为机 器 i 的首/末订单或满足 Δk ≥0，则拒绝 πi ( k) 有 F'≤F． 定理 2． 给定初始调度 Π0 = { π0 i | i} ，若min j∈π0 i { pij} ≥ max j，k∈π0 i { sijk } － 2 min j，k∈π0 i { sijk } ( i) ，则对于由 Π0 衍生出来的任何决策对〈ＲS，Π〉，拒绝满足 rejπi ( k) ≤ wπi ( k) Tπi ( k) 的订单 πi ( k) 均不会使总成本增加，即 F'≤F． 证明: 因为〈ＲS，Π〉是由 Π0 得到的，有 πiπ0 i ( i) ，因此min j∈πi { pij} ≥min j∈π0 i { pij} ，max j，k∈πi { sijk } ≤ max j，k∈π0 i { sijk } ，min j，k∈πi { sijk } ≥ min j，k∈π0 i { sijk } ，进而min j∈πi { pij} ≥ max j，k∈πi { sijk } － 2 min j，k∈πi { sijk } ． 所以，对于i，当 1 ＜ k ＜ | πi | 时，式( 12) 成立． Δk = piπi ( k) － siπi ( k － 1) πi ( k + 1) + siπi ( k － 1) πi ( k) + siπi ( k) πi ( k + 1) ≥min j∈πi { pij} － max j，k∈πi { sijk } + 2 min j，k∈πi { sijk } ≥0 ( 12) 根据定理 1，当 k = 1 或|πi |或满足 Δk≥0 时，新 决策对〈ＲS'，Π'〉满足 F'≤F，定理 2 成立． 2. 2 列表拒绝与拒绝规则 对于订单拒绝决策，本节提出一种基于初始调 度 Π0 的列表拒绝方法，即以加工序列 π0 i ∈Π0 ( i = 1，…，m) 为列表，依次确定是否拒绝当前订单，其 中，针对当前订单的订单拒绝规则是列表拒绝方法 的关键． 假设订单 π0 i ( k) 为当前待定的订单，πi 为机器 i 上已确定接受的订单序列，显然 πi 中的订单均位 于 π0 i ( k) 之前加工，即|πi | ＜ k． 式( 13) ( 14) 定义了 π0 i ( k) 的当前完工时间 Cπ0 i ( k) 和拖期 Tπ0 i ( k) ，其中 πi ( |πi | ) 为机器 i 上最新被接受的订单编号． 显然若 订单 π0 i ( k) 被接受，则其紧前订单为 πi ( |πi | ) ． Cπ0 i ( k) = Cπi ( |πi|) + si，πi ( |πi|) ，π0 i ( k) + pi，π0 i ( k) ， if πi≠ pi，π0 i { ( k) ， otherwise ( 13) Tπ0 i ( k) = max { Cπ0 i ( k) － dπ0 i ( k) ，0} ( 14) 根据定理 1，本节提出了订单拒绝规则 Ｒule1． Ｒule 1． 若 rejπ0 i ( k) ≤wπ0 i ( k) Tπ0 i ( k) ，并且以下情况 之一成立，则拒绝订单 π0 i ( k) : ( a) πi = ; ( b) k = | π0 i | ; ( c) Δk = piπ0 i ( k) + ( si，πi ( | πi| ) ，π0 i ( k) + siπ0 i ( k) π0 i ( k + 1) － siπi ( | πi| ) π0 i ( k + 1) ) ≥0 根据定理 1 可知，给定初始调度 Π0，采用基于 Ｒule1 的列表拒绝方法，得到的最终决策对〈ＲS，Π〉 的总成本必然不大于〈，Π0〉的总成本． 此外，根 · 135 ·