[發明專利]一種基于分布集魯棒并行機調度模型的生產調度方法

有效

• 申請號: 201710695985.8
• 申請日: 2017-08-15
• 公開（公告）號: CN107622338B
• 公開（公告）日: 2019-07-26
• 發明（設計）人: 宋士吉;常志琦
• 申請（專利權）人: 清華大學
• 主分類號: G06F17/15
• 分類號: G06F17/15;G06F17/16;G06Q10/06
• 代理公司: 北京清亦華知識產權代理事務所(普通合伙) 11201
• 代理人: 廖元秋

1.一種基于分布集魯棒并行機調度模型的生產調度方法，其特征在于，包括以下步驟：

1)構建具有風險厭惡特性的分布集魯棒優化模型DR-PMSP-RA，得到初始模型DR-PMSP-RA1的表達式；

在DR-PMSP-RA模型中，系統的性能指標選擇為總流經時間TFT；假定所有工件均在加工開始的時刻釋放，即釋放時間均為0，工件的加工時間具有隨機不確定性，隨機加工時間的分布未知，但屬于一個由支撐集、均值向量和協方差矩陣所確定的分布集中；系統性能指標TFT的隨機度量選取為條件風險價值CVaR；DR-PMSP-RA模型的目標為尋找一個最優的魯棒調度方案，該調度方案的TFT在工件加工時間服從最差分布的情況下具有最小的CVaR；

1-1)確定模型決策變量；

DR-PMSP-RA模型的決策變量為可行的調度方案，設該模型中有J個工件和M個機器，工件和機器的集合分別為J＝{1,2,...,J}和M＝{1,2,...,M}，則一個可行的調度方案由一個三維矩陣X∈{0,1}^J×M×J＝{x_jml∈{0,1}|j∈J,m∈M,l∈L＝J}表示；其中，如果工件j被指派到第m個機器上，并以倒數第l的次序加工，則x_jml＝1，反之x_jml＝0；

1-2)加工時間的隨機向量表示；

所有工件的加工時間為一個隨機向量p，該向量所服從的分布為未知，但屬于一個由支撐集、均值向量和協方差矩陣確定的分布集中，該分布集的表達式如式(2)所示：

式中，表示每個工件的加工時間均為非負的，E[p]和Cov[p]分別表示所有工件加工時間向量的均值向量和協方差矩陣；

1-3)構建DR-PMSP-RA模型目標函數；

在給定一個可行調度方案X和所有工件加工時間向量p時，TFT由式(3)計算得到：

式中，p_j表示工件j的加工時間；

所有工件的TFT是一個隨機變量，采用具有風險厭惡特性的條件風險價值CVaR作為隨機TFT的度量；隨機損失Z的CVaR_α表示其在最差1-α概率下的期望，由式(4)計算得到：

CVaR_α(Z)＝E[Z|Z≥inf{z:P(Z＞z)≤1-α}]， (4)

式中，α∈(0,1)表示CVaR的置信水平，P表示概率取值，inf表示求取集合中的下確界；將在某一分布集上的最大CVaR_α(Z)定義為魯棒CVaR_α(Z)，即RCVaR_α(Z)；

DR-PMSP-RA模型的目標函數表達式如式(5)所示：

式中，的上標p表明RCVaR所屬的所有工件加工時間向量的分布集為D^p，sup表示取集合中的上確界；

1-4)確定DR-PMSP-RA模型的約束條件；

1-4-1)隨機加工時間約束；

所有工件的加工時間向量p的分布未知，但屬于一個由支撐集、均值向量和協方差矩陣確定的分布集中，表達式如式(6)所示：

1-4-2)可行調度方案約束；

可行調度方案X中的每個元素均是0-1變量，表達式如式(7)所示：

1-4-3)工件占用位置約束；

每個工件僅可占用一臺機器上的一個位置，表達式如式(8)所示：

1-4-4)位置被工件占用約束；

每臺機器上的每個位置最多可被一個工件占用，表達式如式(9)所示：

1-4-5)排序緊湊約束；

每臺機器上被占用的位置是連續的，且從1開始，表達式如式(10)所示：

如式(7)-式(10)所示的后四類約束均是約束調度方案可行性的，將其整合到一起，形成調度方案的可行域X，如式(11)所示：

1-5)建立具有風險厭惡特性的分布集魯棒并行機初始模型DR-PMSP-RA1的表達式，如式(12)所示：

式中，X為調度方案的可行域，的上標p表明RCVaR所屬的分布集為D^p，min表示在可行域X中尋找目標函數的最小值，arg表示求得最小目標函數值所對應的最優解X^*；

2)對DR-PMSP-RA模型的目標函數進行轉化與估計；具體步驟如下：

2-1)轉換決策變量；

DR-PMSP-RA模型的決策變量由三維矩陣X等價轉化為二維矩陣Y，轉換關系如式(13)所示：

Y的可行域表達式如式(14)所示：

將二維矩陣Y表示為向量π，表達式如式(15)所示：

π表示忽略機器序號后工件加工順序的倒序；

π的可行域表達式如式(16)所示：

TFT表示為π與p的內積，表達式如式(17)所示：

f(π,p)＝f(X,p)＝π^Tp； (17)

2-2)將等價轉化為協正定規劃；

的值等于如式(18)所示的協正定規劃問題RCVaR-COP的最優值：

min k+(1-α)^-1[r₀+μ^Tr₁+(Σ+μμ^T)·Z] (18)

r₀∈R,r₁∈R^J,Z∈R^J×J,k∈R₊；

式中，‘·’表示兩個矩陣的內積，s.t.代表約束條件，±_co 0表示±_co 0左側的矩陣是一個協正定矩陣；

2-3)利用半定松弛得到的估計上界；

通過將式(18)中的兩個協正定矩陣約束松弛為正定矩陣約束，RCVaR-COP問題被松弛為一個半正定規劃問題RCVaR-SDP，表達式如式(19)所示：

min k+(1-α)^-1[r₀+μ^Tr₁+(Σ+μμ^T)·Z] (19)

r₀∈R,r₁∈R^J,Z∈R^J×J,k∈R₊，

式中，±0表示±0左側的矩陣是一個半正定矩陣；

令半正定規劃問題RCVaR-SDP的最優值為則根據半定松弛的關系，為的一個上界；

2-4)利用分布集映射關系得到的估計上界；

由于所有工件加工時間向量p的隨機性，對每一個確定的π來說，f(π,p)是一個隨機變量，記為f_π；基于p的均值向量和協方差矩陣，f_π的均值μ_f(π)和方差表達式如式(20)所示：

進而令f_π的分布集為：

對于一維非負隨機變量f_π，其RCVaR通過式(22)計算得到：

對于任意一個D^p中的分布，若隨機向量p服從于分布集D^p中的分布F，則其相應投影隨機變量f_π＝π^Tp的支撐集為[0,∞)，均值為π^Tμ＝μ_f(π)，方差為則f_π的分布在分布集D^f中；因此，在分布集D^f中求得的是在D^p中求得的的一個上界，即：

與之間的關系表達式如式(24)所示：

3)對步驟1)建立的DR-PMSP-RA1模型進行轉化；

3-1)替換

利用步驟2)得到的上界替代DR-PMSP-RA1模型轉化為估計模型DR-PMSP-RA2，表達式如下：

3-2)分解估計模型DR-PMSP-RA2；

將DR-PMSP-RA2模型分解成兩個子模型，分解后的模型表達式如式(26)所示：

式中，DR-PMSP-RA2模型分解后成為DR-PMSP-RA3模型，DR-PMSP-RA3模型包含R₁和R₂兩個子模型，子模型R₁的最優解為子模型R₂的最優解

4)對DR-PMSP-RA模型進行求解，得到最優的生產調度方案；

對步驟3-2)分解得到的子模型R₁和子模型R₂求解，分別得到兩個子模型的最優解；其中，更小的一個最優解即為DR-PMSP-RA模型的最優解；DR-PMSP-RA模型的最優解為一個最優的向量π值，其對應的忽略機器序號后所有工件加工順序的倒序即為最優的生產調度方案。