韓豫鑫，顧幸生（華東理工大學化工過程先進控制與優(yōu)化技術教育部重點實驗室，上海 200237）

?

基于特定單元事件點的改進間歇生產(chǎn)調度模型

韓豫鑫，顧幸生
（華東理工大學化工過程先進控制與優(yōu)化技術教育部重點實驗室，上海 200237）

摘要：建立有效的間歇調度模型一直是生產(chǎn)調度問題調度研究的熱點，而連續(xù)時間模型是優(yōu)化短期間歇生產(chǎn)調度問題的有效工具?；谔囟▎卧录c的概念，建立一種改進的間歇調度連續(xù)時間混合整數(shù)線性規(guī)劃（MILP）模型。該調度模型引入了新變量，使模型處理物料在不同設備間的傳輸過程更加靈活。結果表明，提出的改進模型只需要較少的事件點，就可以快速有效處理無限中間存儲（UIS）間歇調度問題。

關鍵詞：間歇調度問題；生產(chǎn)；優(yōu)化；特定單元事件點；模型

DIO: 10.11949/j.issn.0438-1157.20151860

2015-12-08收到初稿，2015-12-22收到修改稿。

聯(lián)系人：顧幸生。第一作者：韓豫鑫（1990—），男，博士研究生。

引 言

在流程工業(yè)生產(chǎn)過程中，間歇生產(chǎn)過程占有重要位置，其在食品、藥品、染料生產(chǎn)過程中廣泛應用。間歇生產(chǎn)過程具有小批量、生產(chǎn)設備功能冗余、生產(chǎn)路線靈活等特點，從而表現(xiàn)出良好的靈活性和適應性[1-3]。間歇生產(chǎn)的結果非常依賴生產(chǎn)調度，通過實施合理的生產(chǎn)調度方案，可以有效提高間歇過程生產(chǎn)能力。

在過去的30年間，間歇調度研究取得很多的研究成果，多種間歇調度建模方法被提出并用于解決間歇調度問題。以時間的表達方式來劃分，這些調度模型主要分為離散時間[4-6]和連續(xù)時間建模方法。其中連續(xù)時間表達方式可以進一步分為全局事件點[7]、基于時間槽[8]、基于特定單元事件點[9-11]和基于順序[12-13]的連續(xù)時間建模方法，而所有的模型都歸結為混合整數(shù)線性規(guī)劃模型（mix integer linear programming，MILP）。經(jīng)過大量研究表明，基于特定單元事件點建模方法可以有效降低間歇調度模型中出現(xiàn)的變量數(shù)量和所需事件點數(shù)量，是非常有效的間歇調度建模方法。

事件點的概念最早由Ierapetritou等[14]提出，主要針對間歇過程短期調度，在生產(chǎn)設備時間軸上采用一系列離散點來表示任務的開始和結束。最初的調度模型存在很大的局限性，之后有很多的研究者針對模型存在的問題進行了改進和研究。Janak等[15]提出了特定單元事件點模型在處理不同存儲策略和資源約束的方法，并首先提出了跨越多個事件點任務的模型表達方式。Shaik等[16]提出了基于資源任務網(wǎng)（RTN）的模型（S&F），用于解決無資源約束的間歇調度問題。之后，他們又提出了含有三參數(shù)變量的模型[17]，結果顯示這種新的概念可以有效解決間歇調度問題。Shaik等[18-19]將這種含有三參數(shù)變量的模型推廣到更加復雜的情況（S&V），提出局部條件順序和嚴格條件順序的概念，使模型使用更少的事件點就可以解決標準算例。

本文主要解決無限中間存儲（UIS）策略的間歇調度問題。以特定單元事件點概念為基礎，主要針對傳統(tǒng)模型存在的缺點，提出新的變量和約束，使模型在不影響調度結果的情況下，能以較快的速度以及較少的事件點得到最優(yōu)解。

1 間歇生產(chǎn)過程調度模型

1.1 問題描述

本文建立的模型以狀態(tài)任務網(wǎng)（STN）為基礎，以Shaik等[16]提出的模型（S&F）和Vooradi等[19]提出的模型為基礎進行改進。

多目的短期調度間歇生產(chǎn)過程調度問題已知條件如下：①生產(chǎn)配方，即不同任務在生產(chǎn)設備上的加工時間和所需原料；②生產(chǎn)設備及其生產(chǎn)能力；③中間存儲容量和存儲策略；④必要的生產(chǎn)資源及其可用性；⑤初始原料和產(chǎn)品訂單；⑥生產(chǎn)周期。調度需要確定的內容如下：①生產(chǎn)設備中生產(chǎn)任務的加工順序；②每個加工任務的批量大??；③每個加工任務的加工時間；④合適的目標函數(shù)，包括最小加工時間和最大加工利潤。

模型假設：①除了設備以外，沒有其他資源限制；②忽略設備之間的轉移時間；③無限中間存儲（UIS）。

2.2 間歇調度數(shù)學模型

（1）分配約束 式（1）表示在每臺生產(chǎn)設備中，在同一事件點至多有一項加工任務發(fā)生。其中，i表示加工任務，n表示事件點，w(i,n)表示任務i在事件點n是否存在的二進制變量。

（2）批量約束 式（2）表示每次加工批量大小B(i,n)保持在最大和最小限制之內。

（3）物料平衡約束 式（3）與式（4）表示每個事件點產(chǎn)生的物料平衡約束。其中，ST(s,n)表示事件點n存儲量

式（3）適用于首個事件點的物料平衡，式（4）適用于其他事件點。在式（4）中，等號右側包含每個事件點加工任務產(chǎn)生的中間物料以及加工任務消耗的物料。

（4）加工時間約束 式（5）表示在每個加工任務開始時間Ts(i,n)、結束時間Tf(i,n)以及加工時間之間的約束。加工時間包含了加工時間的常量αi和變量βi。

如果設備限制加工后設備等待時間，則采用式（6）來進行約束。其中，UWi表示等待時間的限制。

（5）加工順序約束

① 同一任務在同一設備上 在相同設備上的相同任務，采用式（7）來約束加工任務的先后順序。

② 不同任務在相同設備上 在同一設備上的不同任務，采用式（8）來約束加工任務的先后順序。

③ 不同任務在不同設備上 不同任務在不同設備上的順序約束，表示使用相同中間存儲的加工任務之間加工順序約束。一般確定物料傳輸時間主要的處理方法是統(tǒng)一進行規(guī)范，即在事件點統(tǒng)一進行，如式（9）所示。

其中，M是足夠大正數(shù)，即大M約束。式（9）用于限制加工過程中物料傳輸過程中時間約束。

如果中間儲罐存儲適量的加工原料，消耗中間存儲的加工任務可是適當改變開始時間，使調度需要事件點數(shù)量減少。針對使用中間存儲和物料傳輸過程中存在限制，在V&S模型[19]的基礎上，本文對原變量進行修改并提出新變量對模型進行改進：be(i,i′,n)表示生產(chǎn)物料任務i向消耗物料任務i′在事件點n提供的批量；ze(i,i′,n)是二進制變量，表示生產(chǎn)物料任務i向消耗物料任務i′在事件點n是否提供物料，0和1分別表示提供和不提供；新變量ST(s,i′,n)表示中間儲罐s向任務i提供的批量大小。根據(jù)對變量的定義，式（10）～式（16）表示使用相同中間存儲的加工任務之間加工順序約束。

其中，式（10）～式（12）表示物料傳輸?shù)奈锪掀胶饧s束；式（13）表示傳輸批量約束，與式（2）相似；式（14）、式（15）是對二進制變量ze(i,i′,n)進行約束，若加工任務w(i′,n)與w(i,n?1)都為1，則ze(i,i′,n)才為1，否則為0；式（16）是時間順序約束，是一個大M約束，當w(i,n?1)與ze(i,i′,n)同時為1時，此約束才生效。式（10）～式（16）表示只有當消耗原料任務i使用前一事件點的物料時，時間約束式（16）才生效。

同時，由于物料是否能傳遞，取決于是否加工和生產(chǎn)任務的存在，因此式（17）、式（18）用于對物料傳遞的約束。

由于模型以事件點單位進行時間上和物料上的約束，而且二進制變量用來表示任務發(fā)生的先后順序，與連續(xù)變量時間并無直接關系，式（19）用來防止出現(xiàn)實時沖突。

在式（19）中，當前事件點消耗任務應當比兩個事件點前生產(chǎn)物料任務的結束時間晚。但是，上一個事件點的是以消耗任務的結束為止，因此本文提出式（20）用以防止出時間沖突。

式（21）同式（19）、式（20）相同，為防止出現(xiàn)實時沖突，及同一事件點加工任務和消耗任務之間的時間約束。

（6）生產(chǎn)期限約束 同一臺設備上所有加工任務的加工時間之和不能超過生產(chǎn)期限H。

（7）變量限定 變量限定主要對二進制變量和連續(xù)變量進行限制，用式（23）、式（24）表示。在實際計算過程中，某些變量也可以通過經(jīng)驗來確定其具體值[14]。

（8）目標函數(shù)

①以利潤最大為目標

式（25）表示最終產(chǎn)品利潤最大的目標函數(shù)。對于所有的含有大M的約束，其M均可由生產(chǎn)期限H替換。

② 最小加工時間

式（26）與式（27）為最小加工時間的目標函數(shù)，包括最終產(chǎn)品的需求量和加工時間的要求。在以最小加工時間為目標時，以上模型中的H變量全部替換為加工時間MS。

2 實例仿真及分析

2.1 仿真算例

為驗證模型的有效性，本文采用3個算例進行仿真計算，STN圖如圖1所示。

圖1 算例的STN圖Fig.1 State-task network representation for examples

算例1采用Vooradi等[19]提出的算例，該算例只參與計算利潤最大的無限中間存儲目標，生產(chǎn)期限H=4。算例2采用Shaik等[17,19]提出的算例，包含加工過程并且含有循環(huán)加工過程。算例3采用Sundaramoorthy等[19-20]提出的算例，其中S6和S7的初始存料分別為50。

算例在CPU 2.33GHz、內存4GB的計算機上，使用GAMS/CPLEX軟件進行仿真，全部計算結果如表1～表3所示。

2.2 最大利潤仿真結果

以利潤最大為目標進行計算，算例1的生產(chǎn)周期H=4，算例2與算例3的生產(chǎn)周期分別為H=8、H=10、H=12、H=16。本文提出的模型的計算結果將與S&F[16]、V&S1[18]以及V&S2[19]模型的計算結果對比。V&S1和V&S2模型允許加工任務跨越多個事件點，在求取最優(yōu)值的基礎上默認跨越事件點數(shù)量為0。計算結果對比內容包括事件點數(shù)量(events)、松弛規(guī)劃(RMILP)、0-1混合規(guī)劃(MILP)、二進制變量數(shù)量(binary variables)、連續(xù)變量數(shù)量(continuous variables)、約束數(shù)量(constraints)以及計算節(jié)點數(shù)(nodes)和計算時間(CPU time)。

算例1、2的計算結果見表1。從算例1的計算結果看到，本文提出的模型僅需要2個事件點就可以得到最優(yōu)值，而S&F與V&S1模型至少需要3個事件點才可得到最優(yōu)解，與V&S2模型相同，都可以有效減少時間點數(shù)量。圖（2）為算例1 的甘特圖。從圖2（a）中可以看出，由于使用約束式（9），使任務3與任務5的在事件點N2開始時間必須比任務1開始時間晚，因此任務3或5不能在事件點N2使用s2。只有當任務3與任務1同在事件點N2時，任務3或5才能使用初始存料。而使用本文提出的模型，與V&S2模型相同，消耗物料任務的開始時間更加靈活，因此任務3開始時間可以比任務1的開始時間早，只需要2個事件點就可以取得最優(yōu)解。

圖2 算例1甘特圖Fig.2 Gantt chart for example 1

如表1所示不同生產(chǎn)期限算例2計算結果中，H=10的情況下，相比于模型S&F和V&S1調度模型，本文的模型改進在不需要跨越事件點的情況下就可得到最優(yōu)解，并且松弛規(guī)劃（RMILP）的結果更好。相比V&S2模型，本文模型求解所需的計算節(jié)點數(shù)量（nodes）和計算時間都相對較少，而且所需的二進制變量數(shù)量并未增加。由于需要更多的0-1變量和連續(xù)變量來表示物料傳輸過程中出現(xiàn)的情況，因此本文所需的變量和約束數(shù)目相比于S&F和V&S1模型，需要的變量和約束更多。在其他條件下，本文模型也可有效計算出調度結果。

表1 算例1、2最大利潤仿真結果Table 1 Computational results for examples 1, 2 under maximization of profit with UIS

算例3的計算結果見表2。在H=10情況下，S&F和V&S1模型需要8個事件點，且加工任務需要跨越一個事件點（Δn=1）才可以得到最優(yōu)解，本文提出的改進模型僅需7個事件點即可，且需要的二進制變量數(shù)量更少。相比于V&S2模型，本文的調度模型計算時間和計算節(jié)點數(shù)量更少，即計算速度更快。圖3為算例3（H=10）使用本文模型的甘特圖。

圖3 算例3甘特圖Fig.3 Gantt chart for example 3

2.3 生產(chǎn)周期最短仿真結果

算例2、3生產(chǎn)周期最短的計算結果見表3。算例2采用兩種不同產(chǎn)品需求量計算。從表中可以看出，在第2種情況下（D8=500，D9=400），V&S1模型需要跨越兩個事件點得到最優(yōu)解。而本文在無需跨越事件點的情況下就可得到最優(yōu)解。而且相比于V&S2模型，本文提出的模型計算速度更快，結算所需要的計算節(jié)點數(shù)量更少。

算例3也采用兩種情況進行計算，3種模型結果相同。在不考慮跨越多個事件點的情況下，本文的改進模型相比于V&S2模型，計算效率更高。

表2 算例3最大利潤仿真結果Table 2 Computational results for example 3 under maximization of profit with UIS

表3 算例2、3生產(chǎn)周期最短仿真結果Table 3 Computational results for examples 2, 3 under minimization of production cycle with UIS

3 結 論

本文研究的是間歇生產(chǎn)過程調度建模問題，建立的改進間歇生產(chǎn)調度模型，針對設備之間物料傳輸約束進行修改，提出了連續(xù)變量以及相應的約束條件，對于物料傳輸和時間約束可能存在的多種情況進行定義。實驗結果表明，在處理無限中間存儲（UIS）間歇調度問題中，相比于Vooradi等[19]所提出的調度模型，本文建立的模型可以有效提升模型求解速度，并且不影響調度結果。但是由于新變量的引入，模型復雜度也相應提高。針對間歇生產(chǎn)調度建模問題仍需要進一步研究，如模型需要更適應多種存儲策略以及設備等待策略等。

符 號 說 明

I ——加工任務集合

Ij——可在設備j中加工任務

J ——加工設備集合

N ——事件點集合

S ——存儲設備集合

SI——與任務I相關存儲

References

[1] 李慧芳, 李人厚, 陳浩勛. 化工批處理過程調度綜述[J]. 信息與控制, 1999, 28(2): 127-135. DOI: 10.3969/ j.issn. 1002-0411. 1999. 02. 010

LI H F, LI R H, CHEN H X. The survey of scheduling of batch chemical process [J]. Information and Control, 1999, 28(2): 127-135. DOI: 10.3969/ j.issn. 1002-0411. 1999. 02. 010

[2] 耿佳燦, 顧幸生. 不確定條件下中間存儲時間有限多產(chǎn)品間歇生產(chǎn)過程調度[J]. 化工學報, 2015, 66(1): 357-365.

GENG J C, GU X S. Time-constrained intermediate storage multiproduct batch process scheduling with uncertainty [J]. CIESC Journal, 2015, 66(1): 357-365.

[3] 楊玉珍, 顧幸生. 多目標零等待間歇生產(chǎn)過程多任務調度 [J]. 化工學報, 2013, 64(2):4978-4584. DOI: 10.3969/j.issn. 0438-1157. 2013. 12. 046

YANG Y Z, GU X S. Multi-objective no-wait multi-task scheduling problem of batch process [J]. CIESC Journal, 2013, 64(2):4978-4584. DOI: 10.3969/j.issn. 0438-1157. 2013. 12. 046.

[4] CARLOS A M, JAIME C, GROSSMAN I E. State-of-the-art review of optimization methods for short-term scheduling of batch processes [J]. Computers and Chemical Engineering, 2006, 30(6): 912-946

[5] MARAVELIAS C T. A general framework and modeling approach classification for chemical production scheduling [J]. AIChE Journal, 2012, 58(6): 1812-1834.

[6] NIE Y S, LORENZ T B, JOHN M W. Integrated scheduling and dynamic optimization of batch processes using state equipment networks [J]. AIChE Journal, 2012, 58(11): 3416-3434.

[7] CASTRO P M, BARBOSA-POVOA A P, Matos H A, et al. Simple continuous-time formulation for short-term scheduling of batch and continuous processes [J]. Ind. Eng. Chem. Res., 2004, 43(1): 105-120

[8] SUNDARAMOORTHY A, KARIMI I A. A simpler better slot-based continuous-time formulation for short-term scheduling in multipurpose batch plants [J]. Chem. Eng. Sci., 2005, 60(10): 2679-2691

[9] MARAVELIAS C T, GROSSMAN I E. New general continuous-time state-task network formulation for short-term scheduling of multipurpose batch plants [J]. Ind. Eng. Chem. Res., 2003, 42(19): 3056-3074

[10] CHU Y F, YOU F Q. Integration of production scheduling and dynamic optimization for multi-product CSTRs: generalized benders decomposition coupled with global mixed-integer fractional programming [J]. Computers and Chemical Engineering, 2013, 58(11): 315-333.

[11] CHEN G H, YAN L X, SHI B. Modeling and optimization for short-term scheduling of multipurpose batch plants [J]. Chinese Journal of Chemical Engineering, 2014, 22(6):682-689.

[12] SEID R, MAJOZI T. A robust mathematical formulation for multipurpose batch plants [J]. Chem. Eng. Sci., 2012, 68(1): 36-58

[13] 吳建昱, 何小榮, 陳丙珍, 等. 新的多產(chǎn)品間歇生產(chǎn)調度的MILP模型 [J]. 化工學報, 2003, 59(9):1252-1255. DOI: 10.3321/j.issn: 0438-1157.2003.09.016.

WU J Y, HE X R, CHEN B Z, et al. A new continuous time MILP model for scheduling of multi-product batch Plants [J]. Journal of Chemical Industry and Engineering(China), 2003, 59(9):1252-1255. DOI: 10.3321/j.issn: 0438-1157. 2003.09.016.

[14] IERAPETRITOU M G, FLOUDAS C A. Effective continuous-time formulation for short-term scheduling(Ⅰ): Multipurpose batch processes [J]. Ind. Eng. Chem. Res., 1998, 37(9): 4341-4360.

[15] JANAK S L, LIN X, FLOUDAS C A. Enhanced continuous-time unit-specific event-based formulation for short-term scheduling of multipurpose batch processes: resource constraints and mixed storage policies [J]. Ind. Eng. Chem. Res., 2004, 43(10): 2516-2534.

[16] SHAIK M A, FLOUDAS C A. Unit-specific event-based continuous time approach for short-term scheduling of batch plants using RTN framework [J]. Comput. Chem. Eng., 2008, 32(1): 260-282.

[17] SHAIK M A, FLOUDAS C A. Novel unified modeling approach for short-term scheduling [J]. Ind. Eng. Chem. Res., 2009, 48(6): 2947-2964

[18] VOORADI R, SHAIK M A. Improved three-index unit-specific event-based model for short-term scheduling of batch plants [J]. Comput. Chem. Eng., 2012, 43(10): 148-172

[19] VOORADI R, SHAIK M A. Rigorous unit-specific event-based model for short-term scheduling of batch plants using conditional sequencing and unit-wait times [J]. Industrial and Engineering Chemistry Research, 2013, 52(36): 12950-12972

[20] SUNDARAMOORTHY A, KARIMI I A. A simpler better slot-based continuous-time formulation for short-term scheduling in multipurpose batch plants [J]. Chem. Eng. Sci., 2005, 60(10): 2679-2690.

研究論文

Received date: 2015-12-08.

Foundation item：supported by the National Natural Science Foundation of China (61174040, 61573144) and the Shanghai Commission of Science and Technology(12JC1403400).

Improved unit-specific event based model for scheduling of batch plants

HAN Yuxin, GU Xingsheng
(Key Laboratory of Advanced Control and Optimization for Chemical Processes (Ministry of Education), East China University of Science and Technology, Shanghai 200237, China)

Abstract:Establishing effective model of scheduling for batch processes is the hot spot of the batch processes scheduling research. Continuous-time models are evolved as a promising tool for optimizing problems related to short-term scheduling of batch plants. Short-term scheduling of batch operations is an important part of scheduling problems. Based on the concept of unit-specific event, an improved mixed integer linear programming model for scheduling of batch plants is proposed. Several new variables and constraints are introduced to make stock transfer between units more flexible. The result shows that the new model can deal with scheduling problems of unlimited intermediate storage effectively and faster with less number of events.

Key words:batch plants scheduling; production; optimization; unit-specific event; model

中圖分類號：TP 278

文獻標志碼：A

文章編號：0438—1157（2016）03—0758—07

基金項目：國家自然科學基金項目(61174040，61573144)；上海市科委基礎研究重點項目（12JC1403400）。

Corresponding author：Prof. GU Xingsheng, xsgu@ecust.edu.cn