多因素不確定條件下的間歇生產調度優(yōu)化

鄭必鳴，史彬，鄢烈祥

（武漢理工大學化學化工與生命科學學院，湖北武漢430070）

引 言

間歇生產過程因生產方式靈活，被廣泛應用于過程工業(yè)以生產高附加值的化學品、藥品和生物制品等[1]。在間歇生產過程中，生產調度是一項關鍵決策[2]，合理的調度方案對提升企業(yè)的生產效率和經濟效益至關重要。

對于間歇生產調度問題的許多研究都是在確定條件下進行的，原料成本、產品價格、處理時間和市場需求等是確定參數，在實際中并非如此[3-4]。由于不確定因素的存在，確定條件下的最優(yōu)調度方案在實際生產過程中會變?yōu)榇蝺?yōu)，甚至不可行，如果在調度決策中考慮這些不確定因素將大大增加系統柔性[5]。不確定條件下的間歇化工生產調度問題的研究受到廣泛關注[6-7]。Bonfill 等[8]優(yōu)化了多產品間歇生產過程中需求不確定情況下的調度決策，通過求解多目標優(yōu)化模型最大化利潤并控制需求不滿足的風險；Balasubramanian 等[9]采用離散值描述不確定加工時間，提出了多周期混合整數線性規(guī)劃(mixed-integer linear programming, MILP)模型并求解；王飛等[10]針對多周期間歇生產中產品需求這個不確定因素，使用混合近似求解策略將原大規(guī)模MILP 問題分解并實現了快速求解；耿佳燦等[11]針對多產品間歇生產過程中產品處理時間不確定的情況，使用基于改進粒子群和分布估計的混合算法求解；丁然等[12]針對化工生產調度過程中處理時間不確定問題，提出了一種魯棒調度策略，使用基于遺傳算法的分解算法求解；Janak 等[13]研究了采用概率分布描述的不確定因素情況下的魯棒調度。目前，對于不確定條件下生產調度建模主要有以下三種方法：隨機規(guī)劃[14-15]、模糊規(guī)劃[11,16]以及魯棒優(yōu)化[13,17]。其中，魯棒優(yōu)化方法僅需要獲取參數所屬的區(qū)間范圍，采用不確定集合來描述參數不確定性，是不確定條件下生產調度優(yōu)化的有效方法。傳統的魯棒優(yōu)化方法由于只考慮最惡劣情況，得到的解過于保守[18-19]。如何調整模型保守性，在模型魯棒和解魯棒之間取得平衡是研究的方向。

然而，前人的研究大多只考慮了單因素的不確定性，調度目標中較少關注生產過程中的各項成本。本文考慮了化工生產過程中需求、處理時間和市場價格三種不確定性因素，同時在調度的利潤目標中考慮了操作成本和原料成本。在狀態(tài)任務網絡(state-task-network, STN)[20-21]和特定單元事件點[22-24]的建模方法基礎上，首先建立連續(xù)時間描述[25-26]的間歇生產調度確定性模型，然后用對稱區(qū)間描述不確定參數，引入不確定預算參數建立可調整保守性的魯棒優(yōu)化模型，最后對案例進行求解以驗證優(yōu)化方法的有效性。

1 問題描述與數學模型

對于某間歇生產過程，已知其狀態(tài)任務網絡描述、生產過程的工藝數據和費用數據，生產過程中存在的不確定因素包括：需求不確定、處理時間不確定和市場價格不確定，通過分析歷史數據可以得到這些參數的平均值和不確定波動范圍。對生產資源和操作任務進行調度優(yōu)化，優(yōu)化的目標是要確定一個兼顧可靠性和盈利性的調度方案。具體內容如下：①生產設備中生產任務的加工順序；②每個加工任務的批量大?。虎勖總€加工任務的啟止時間；④生產過程的操作成本、原料成本和凈利潤。

1.1 間歇生產調度的確定性模型

1.1.1 目標函數

調度目標是調度末期的凈利潤最大，具體是指產品銷售收入減去各項成本。其中×Invs,N表示最后一個事件點結束時賣出所有產品的銷售收入，表示原料消耗成本，表示整個調度周期的操作成本，包括固定成本和可變成本兩部分，固定成本只與任務種類相關，而可變成本不僅與任務種類相關，還與物料處理量大小呈正比。

1.1.2 約束條件

（1）分配約束

（2）物料平衡約束

（3）設備加工能力約束

（4）存儲容量約束

（5）持續(xù)時間約束

（6）序列約束

（7）調度期時長約束

（8）市場需求約束

式(2)表示在特定的事件點內，某個設備單元至多進行一個生產任務。式(3)中，Invs,n表示物料s 在第n 個事件點的存儲量，等于物料s 在第n-1 個事件點的存儲量Invs,n-1加上事件點n-1 內的生產量，再減去第n個事件點的消耗量。初始事件點由于沒有物料產生，物料s 的存儲量用式(4)計算。式(5)表示設備的生產能力在有限范圍之內，式(6)表示物料的存儲量受設備存儲能力限制。式(7)表示單臺設備上的任務加工時間約束，式(8)～式(12)表示相同設備、不同設備上的任務處理順序約束，式(13)、式(14)要求所有設備上任務的開始時間和完工時間均在調度時間區(qū)域內。式(15)表明產品在調度期結束時的庫存量應該滿足市場需求。

1.2 間歇生產調度的魯棒優(yōu)化模型

為解決不確定條件下的間歇生產調度問題，建立了一個可調整保守性的魯棒優(yōu)化模型，其一般形式[27]可表述為：

上述模型中，xj既可以是0-1變量也可以是連續(xù)變量，假設第i 個約束中含有的不確定參數，是一個獨立、對稱、有界的隨機變量，均值為aij，變化范圍是，但是概率分布未知，在[aij-,aij+]中隨機取值，構造不確定參數集合N={1,2,…,n}，j∈N來表示為了避免模型過度保守，引入不確定預算參數Γi。Si代表約束中包含個不確定參數的集合，當Γi不是整數時，新增一個不確定參數，變化的范圍至多為模型通過限制至多有個不確定參數同時取得最壞值來控制解的保守性。

為了求解上述不等式，首先對式(17)中的max項進行等價轉化，得到：

引入對偶變量，根據強對偶性，得到式(19)～式(21)的對偶min問題，并代入到原約束中，得到：

其中zi為約束式(20)的對偶變量，pij為約束式(21)的對偶變量。應用式(16)、式(22)～式(24)可得到間歇生產調度的魯棒對應問題。

在式(15)中添加一個固定值為1 的離散變量到約束中，即：

每個需求約束中只含有一個不確定參數，因此，Γd∈[0,1]，考慮需求不確定的魯棒調度優(yōu)化公式需要添加以下約束：

以上每個約束中只含有一個不確定參數，因此，Γt∈[0,1]，考慮處理時間不確定的魯棒調度優(yōu)化公式需要再添加以下約束：

約束中含有k（原料和產品的種類數）個不確定參數，因此，Γp∈[0,k]，考慮市場價格不確定的魯棒調度優(yōu)化公式需要添加以下約束：

2 案例研究

本節(jié)選取了文獻[28]的間歇生產過程實例進行計算，對應的狀態(tài)任務網絡如圖1所示，生產過程的部分費用數據來自文獻[29]，詳細數據列于表1和表2。在23.8 版本的GAMS 軟件中建模，使用Cplex 12.4 求解器求解（相對最優(yōu)間隙，optimality gap 設置為0.1%）。運行的計算機環(huán)境為Windows10 64位操作系統，酷睿i5處理器，主頻為3.4 GHz，8G RAM。

圖1 本例中狀態(tài)任務網絡圖描述的間歇生產過程Fig.1 State task network for production process instance

表1 案例中與任務相關的工藝和成本數據Table 1 Process and cost data related to tasks in the case

表2 案例中的物料的庫存、初始量、價格和需求量數據Table 2 Inventory，initial amounts，price，and demand data for materials in the case

表3 三種不確定因素的波動范圍和預算參數取值范圍Table 3 Range of fluctuations for three uncertain factors and budget parameters

在本案例（圖1）中，一共有3 種原料（S1,S2,S3）經過5 個任務(H,R1,R2,R3,S)得到2 種產品(S8,S9)，過程有4臺加工設備(HR,RR1,RR2,SR)，調度時長設為12 h。已知需求、處理時間、市場價格可能會在均值附近波動，表3 給出了三種不確定因素在均值處的波動范圍和不確定預算參數取值范圍。事件點的個數對模型求解結果有較大影響，事件點過少會導致次優(yōu)解，過多不但對提高解的質量無益，還會增大問題規(guī)模，為了確定事件點個數，增加事件點的個數直到目標函數值不再增加，得到最佳事件點個數[30]。

經過計算得到確定條件下的最佳事件點個數為5 個，profit=1435.75 USD，求解時間為0.14 s。不確定條件下需要6 個事件點，在此條件下求解魯棒優(yōu)化模型。考慮三種不確定因素單獨存在時對目標函數值的影響，結果如圖2 所示。隨著不確定預算參數的增大，目標函數值均呈現出下降的趨勢，直到不確定預算參數取最大值時，得到最保守的解，說明提出的魯棒優(yōu)化模型可以較好地控制模型的保守程度，避免決策結果的過度保守。

圖2 考慮單一不確定因素的求解結果Fig.2 Solution results with single uncertainty

在實際生產調度中，三種不確定因素往往是同時存在的，因而系統地考慮了多因素不確定性帶來的影響。結合圖2 和表4 可以看出，同時考慮三種不確定因素與單獨考慮的相比，當不確定預算參數取值相同時，目標函數值較小，這是因為不確定因素的增加給生產調度帶來了負面的影響。因而當不確定預算取值Γd=0.7,Γt=0.7,Γp=3.5時，此時的魯棒模型已經無可行解?？梢钥闯?，同時考慮三種不確定因素時，模型的求解時間呈上升趨勢，這是由于隨著不確定預算參數值的增加，模型魯棒性增加，使可行域縮小，模型的求解時間隨之延長。

另外，不確定因素同時取最惡劣值的情況是很少見的。本例在最惡劣的情況下，需求量、處理時間、原料價格取波動范圍內的最大值，而產品價格取波動范圍內的最小值，同時滿足條件的調度方案是不存在的。企業(yè)決策者可以通過設定不確定預算參數值來獲得不確定條件下的較滿意的調度方案。對于風險中性決策者，可以選擇不確定條件（Γd=0.3,Γt=0.3,Γp=1.5）下的調度方案，對于較保守的決策者，可以選擇不確定條件（Γd=0.6, Γt=0.6,Γp=3）下的調度方案，分別如圖3 和圖4 所示。圖中不同顏色的矩形代表設備執(zhí)行不同的任務，矩形的長度代表任務的加工時間(h)，矩形中的數字代表任務的處理量(kg)?？梢钥闯觯c圖5中確定條件下的調度方案相比，兩種不確定條件下任務的數量增加，在圖3的調度方案中生產出更多的產品，從而更好地滿足了需求增加時的情景；兩種不確定條件下反應器RR1 和RR2 未被使用的時間間隙明顯少于確定條件下的，一方面是因為設備上的任務數量增加，另一方面說明魯棒調度方案考慮到了不確定處理時間的影響，因為處理時間的延長會使設備的空閑時間縮短。

表4 同時考慮三種不確定因素的求解結果Table 4 Solution results with all uncertainties

圖3 不確定條件下的最優(yōu)調度方案(Γ d=0.3,Γ t=0.3,Γ p=1.5)Fig.3 Optimal scheduling scheme under uncertain conditions(Γ d=0.3,Γ t=0.3,Γ p=1.5)

圖4 不確定條件下的最優(yōu)調度方案(Γ d=0.6,Γ t=0.6,Γ p=3)Fig.4 Optimal scheduling scheme under uncertain conditions(Γ d=0.6,Γ t=0.6,Γ p=3)

圖5 確定條件下的最優(yōu)調度方案Fig.5 Optimal scheduling scheme under certain conditions

圖6 比較了三種情況下的結果，每種情況下的銷售收入由利潤、操作成本、原料成本三部分構成，各部分的占比如圖7 所示。例如，確定條件下的利潤、操作成本、原料成本分別為1435.75、1588.25、362.25 USD，銷售利潤率、操作成本和原料成本百分比分別為42.4%、46.9%、10.7%。

圖6 三種情況下結果的比較Fig.6 Comparison of results in three cases

可以看出，不確定條件下的利潤值較確定條件下的低，而且隨著不確定預算參數值的增加，操作成本和原料成本百分比增加，銷售利潤率降低，這是由于：為了應對不確定性，決策者會增加生產任務數量，縮短設備空閑時間，適當提高產品的產量，減小不確定因素對生產過程造成的負面影響，操作費用和原料成本費用百分比自然會增加。

圖7 三種情況下的銷售收入構成分析Fig.7 Analysis of sales revenue composition in three cases

3 結 論

（1）本文提出了需求、處理時間和市場價格不確定下的生產調度模型，使用對稱區(qū)間描述了不確定參數并建立了魯棒優(yōu)化模型，在調度的利潤目標中考慮了生產操作成本和原料成本，使決策者可以更加全面地對生產過程做出決策判斷。

（2）應用實例對模型進行求解分析，通過對比發(fā)現考慮不確定性的魯棒優(yōu)化模型較確定性模型利潤更低，且可以通過不確定預算參數調整模型的保守程度，對企業(yè)在不確定條件下的生產調度決策具有一定的指導意義。

（3）在需求、處理時間和市場價格不確定下，魯棒優(yōu)化方法得到的生產調度方案中任務數量增加，設備空閑時間縮短，使得生產操作費用和原料成本費用百分比會適當增加，從而更好地應對不確定性。

符 號 說 明

aij,bi——約束確定性參數

a～ij——不確定系數參數的真值

Bat——物料的處理量，kg

c——目標函數確定性參數

dem——物料的市場需求量，kg

fixc——固定費用單價，USD

H——調度時長，h

Inv——庫存量，kg

i ∈I——操作任務及集合

j ∈J——操作設備及集合

k——原料和產品的種類數

Mi——第i個約束中不確定系數的集合

n ∈N——事件點及集合

pij——對偶變量

pri——物料的市場價格，USD·kg-1

profit——銷售利潤，USD

Si——第i 個約束中包含個不確定參數的集合

Sp——物料的產品狀態(tài)集合

Sr——物料的原料狀態(tài)集合

Sti——物料的初始購買量，kg

s ∈S——物料狀態(tài)及集合

Tf——任務完成時間，h

Ts——任務起始時間，h

ti——當Γi不是整數時增加一個不確定參數所代表的系數

Vmax——最大庫存量，kg

varc——變動費用單價，USD·kg-1

Wi,j,n——二元變量

xj——決策變量

zij——輔助變量

zi——對偶變量

α,β——處理時間波動系數

Γi——不確定預算參數

ρP，ρC——分別為生產與消耗分配系數

σd,σt,σp——分別為需求、處理時間和價格在均值處的波動范圍