帶批處理機的多階段柔性流水車間調(diào)度優(yōu)化

王君妍, 王薛苑, 軒 華

(鄭州大學 管理工程學院，河南 鄭州 450001)

帶批處理機的多階段柔性流水車間調(diào)度優(yōu)化

王君妍, 王薛苑, 軒 華

(鄭州大學 管理工程學院，河南 鄭州 450001)

從鋼鐵行業(yè)的煉鋼—連鑄—熱軋過程提煉出中間階段有多臺批處理機，其它階段為離散機的多階段柔性流水車間調(diào)度問題.首先，結(jié)合工件動態(tài)到達、各階段間的運輸時間以及機器的調(diào)整時間等生產(chǎn)特征，對問題進行描述，建立以最小化總加權完成時間為目標的數(shù)學模型.然后，針對該問題提出了改進的自適應遺傳算法,使遺傳參數(shù)隨其迭代及適應函數(shù)值調(diào)節(jié).對150個工件的大量隨機數(shù)據(jù)進行測試，結(jié)果表明，與常規(guī)遺傳算法相比，所提出的自適應遺傳算法能在較短的計算時間內(nèi)得到更好的解；與拉格朗日松弛算法相比，求解大規(guī)模問題時，所提算法在解的質(zhì)量方面優(yōu)勢較為明顯.

柔性流水車間調(diào)度；批處理機；總加權完成時間；自適應遺傳算法；自適應調(diào)節(jié)

0 引言

在鋼鐵行業(yè)，煉鋼、連鑄、熱軋作為煉鋼的主要工序，在整個流程中起著重要作用.在煉鋼—連鑄—熱軋過程中，轉(zhuǎn)爐生產(chǎn)出來的鋼水經(jīng)過精煉爐精煉后，要鑄造成不同類型、不同規(guī)格的板坯；將裝有鋼水的鋼包運至回轉(zhuǎn)臺，回轉(zhuǎn)臺轉(zhuǎn)動到澆鑄位置后，鋼水被注入中間包，鋼水分配到各個結(jié)晶器中結(jié)晶成各種鑄件，之后鑄件經(jīng)過切割機的連續(xù)切割成為板坯[1].使用同一中間包的多個爐次(稱為一個澆次)要按一定順序連續(xù)生產(chǎn).進而，板坯由保溫車運送到加熱爐進行加熱，直至達到熱軋加工的溫度要求，然后，先由高壓水槍祛除板坯表面的氧化鱗片，再經(jīng)定寬壓力機對板坯進行側(cè)壓以調(diào)整其寬度，并依次通過粗軋機進行多道次可逆軋制[2-3].

上述生產(chǎn)過程中，各階段由多臺同構(gòu)并行機組成，并且在連鑄階段一個澆次內(nèi)的所有爐次都要在同一臺連鑄機上進行無間斷的加工，因此該結(jié)構(gòu)可看作是中間階段具有串行批處理機的柔性流水車間.考慮到鋼鐵生產(chǎn)中各個加工階段的運輸時間、機器的調(diào)整時間以及工件的釋放時間，提出筆者所研究的多階段柔性流水車間問題(flexible flowshop scheduling problem, FFSP).

對于兩機流水車間批調(diào)度，文獻[4]提出了一種分解啟發(fā)式算法用來求解工件的總加權拖期費用；文獻[5]提出以最小化加工時間跨度為目標的蟻群優(yōu)化算法；文獻[6]以最小化完工期makespan為目標，考慮工件動態(tài)到達，構(gòu)建了一種最優(yōu)化算法以求解各批次加工時間為定值的流水車間批調(diào)度問題；文獻[7]針對差異工件批處理機調(diào)度，設計了一種基于LPT規(guī)則和批調(diào)度近似規(guī)則的算法用以最小化制造跨度和總完工時間.

就FFSP的串行批問題，文獻[8]研究了任意一個階段有串行批處理機且其它階段為離散機的多階段FFSP，提出了改進的拉格朗日松弛(Lagrangian relaxation, LR)算法，目標為總加權完成時間最小.就FFSP的并行批問題，文獻[9]提出了一個新的遺傳算法(genetic algorithm, GA)最小化makespan；文獻[10]利用啟發(fā)式搜索GA求解一個階段含并行批處理機的情況，目標分別為最小化makespan及最小化總加權拖期費用.

從上述研究現(xiàn)狀可知，對于兩機流水車間問題，多采用一些啟發(fā)式算法或最優(yōu)化算法來求解最大完工時間最小化問題；針對含串行批的FFSP，多采用LR算法最小化總加權完成時間；針對含并行批的FFSP，則多采用啟發(fā)式、GA等最小化makespan.針對具有串行批處理機的FFSP，GA求解總加權完成時間問題的研究較少.

在GA中，pc和pm等遺傳參數(shù)常固定不變，因此，Srinivas等[11]首先提出了用AGA來求解多目標函數(shù)優(yōu)化問題.后來也有一些學者[12-15]對AGA在車間調(diào)度中的應用進行了研究，文獻[12]對流水車間問題進行建模，采用AGA仿真求解出最優(yōu)調(diào)度方案；文獻[13]為了解決置換流水車間調(diào)度問題，提出了基于模擬退火算法的多種群和自適應遺傳算法；文獻[14-15]均利用AGA求解了FFSP，目標為最小化makespan.

綜上可知，針對參數(shù)自適應的研究多集中在流水車間和FFSP上，目標多為最小化makespan.由于筆者所研究的多階段FFSP考慮了批生產(chǎn)方式和批生產(chǎn)階段機器的調(diào)整時間、工件動態(tài)到達以及階段間運輸時間，是一個較為復雜的NP-hard問題，因此，需要合理地設計GA以提高其求解能力.故而，筆者提出遺傳參數(shù)自適應調(diào)節(jié)策略改進遺傳算法(improved adaptive genetic algorithm, IAGA)，旨在擴展GA對該類問題的求解能力.

1 問題描述與建模

1.1 問題描述

中間階段為批處理機的多階段FFSP可描述為：n個工件依次經(jīng)過s個加工階段進行加工，當經(jīng)過某階段k(1

1.2 符號

定義一些基本符號及決策變量，如表1所示.定義參數(shù)如表2所示.

1.3 數(shù)學模型

根據(jù)以上描述及符號定義，將所研究的多階段FFSP建立為整數(shù)線性規(guī)劃模型.由于實際生產(chǎn)中需要節(jié)省整個流程的時間，提高加工效率，所以將目標設為：

(1)

滿足以下約束：

表1 基本符號及決策變量

表2 參數(shù)

Xki+Tk,k+1+Pk+1,i≤Xk+1,i， ?i,k;

(2)

X1i-P1i+1≥ri， ?i;

(3)

Xx,Nbf+Px,Nb,f+1=Xx,Nb,f+1, ?b,f;

(4)

(5)

(6)

約束(2)表示工件只有在完成前一階段的加工且被運送到下一階段，才能開始它的加工；約束(3)定義了工件動態(tài)到達第一階段；約束(4)表示在批生產(chǎn)階段同一批內(nèi)的工件在一臺機器上連續(xù)地進行加工；約束(5)確保在同一時刻進行加工的工件數(shù)不能超過該時刻可用的機器數(shù)；約束(6)表示工件占用機器的時間區(qū)間.

2 IAGA求解算法設計

步驟1種群初始化.對種群進行初始化，設置種群規(guī)模Popsize=100，遺傳代數(shù)G=200.采用實數(shù)編碼方式，用隨機產(chǎn)生的正整數(shù)對工件依次進行編號，初始階段每個工件都有一個釋放時間，先到達先加工，同時到達按照編號順序加工.

步驟2選擇.采用輪盤賭選擇方式，首先對種群內(nèi)個體的適應度函數(shù)值進行評價,令適應值函數(shù)f(i)為總加權完成時間的倒數(shù).f(i)越大，說明經(jīng)函數(shù)優(yōu)化后的個體對應的解越好，從而保留此個體.

步驟3交叉.采用兩點交叉方式.因種群的更新效率是由交叉算子pc決定的，若pc過大，則優(yōu)秀個體被破壞的可能性會增加；反之，則會使算法搜索能力變差.所以動態(tài)設置pc，即可以持續(xù)優(yōu)化種群，又能保留優(yōu)秀個體.在Srinivas等[11]的研究基礎上，令

(7)

(8)

步驟4變異.采用單點變異方式.雖然GA具有全局搜索能力，但也可能陷入局部收斂.有效設計遺傳算子pm，可以增加算法搜索的廣度和深度.將個體進行變異操作的實際概率pm設置如下[11]：

(10)

式中：pmmin和pmmax分別為進行變異操作的最小和最大概率，令pmmax=0.05.

3 試驗測試

3.1 試驗參數(shù)設置

本節(jié)分別對GA和IAGA進行相應設計，并與LR算法進行對比，在Matlab上測試其性能，這3種算法均在Celeron(R)Dual-Core CPU 2.10 GHz微機上運行.公平起見，將IAGA進行200次迭代所需時間作為停止條件，設置最大運行時間為1 000 s.當工件規(guī)模n={30, 60, 90}時，對3種算法的目標值(minZ)和迭代次數(shù)(ItN)進行比較；而當n={120, 150}時，由于LR運行一次迭代所需的計算時間較長致使在較短的計算時間內(nèi)運行的迭代次數(shù)較少，解的質(zhì)量也較差，隨著問題規(guī)模增大這種情況也更明顯，因此未再測試LR求解這2種工件規(guī)模的情況，僅對IAGA和GA的結(jié)果進行了比較.

令GA的交叉概率為0.8，變異概率為0.05.針對每種工件規(guī)模的{n,s,Mk}組合隨機產(chǎn)生10個實例，因此本次試驗共測試了300組實例，測試數(shù)據(jù)隨機產(chǎn)生.

(1)工件數(shù)n∈{30, 60, 90, 120, 150}；階段數(shù)s∈{3, 4, 5}；機器數(shù)Mk∈{3, 4}；

(2)x=2，Lb=5；

(3)工件的權重以及加工時間是滿足[1, 10]之間均勻分布的隨機數(shù)；

(4)工件動態(tài)到達第一階段的時間、各階段間的運輸時間以及批生產(chǎn)階段所需要的調(diào)整時間都是[3, 5]之間均勻分布的隨機數(shù).

3.2 結(jié)果分析

表3、表4為測試結(jié)果.

(1)當工件規(guī)模和階段數(shù)不變時，隨著可用機器數(shù)的增加，3種算法的目標函數(shù)值都會相應降低，求解時間也會有所減少.

(2)當n=30時，LR得到的解的質(zhì)量最好，目標值比IAGA和GA分別改進了10.7%和13.8%.當n=60時，IAGA的優(yōu)勢逐漸顯現(xiàn)，目標值相對LR改進了8.3%.當n=90時，IAGA求得的目標值比LR改進了24.0%.由此可得，LR求解小規(guī)模問題的效果最好，而IAGA更適合求解貼近實際生產(chǎn)的中大規(guī)模問題.

(3)當n={30, 60, 90, 120, 150}時，IAGA所求的目標值相比GA分別改進了2.8%、3.3%、10.4%、12.5%、13.1%.即對于不同規(guī)模問題，IAGA求解該問題的能力一致強于GA，且在大規(guī)模問題時這種優(yōu)勢更加明顯.

(4)在相同的時間內(nèi)，IAGA的迭代次數(shù)多于GA.當n={30, 60, 90, 120, 150}時，IAGA的迭代次數(shù)比GA分別多了5、6、8、10、15.因此，隨著問題規(guī)模增大，兩者迭代數(shù)的差額也越大，IAGA的效率更高.

表3 規(guī)模n={30,60,90}的測試結(jié)果對比

表4 規(guī)模n={120,150}的測試結(jié)果比對

4 結(jié)論

針對鋼鐵行業(yè)的煉鋼—連鑄—熱軋工藝流程，考慮工件的釋放時間、運輸時間以及機器的調(diào)整時間，建立了中間階段有批處理特征的整數(shù)線性規(guī)劃模型，目標為所有工件的總加權完成時間最小.針對該多階段FFSP，設計了遺傳參數(shù)隨迭代次數(shù)和適應值的改變而進行調(diào)節(jié)的自適應遺傳算法.對各種規(guī)模的問題進行仿真試驗結(jié)果顯示，相同時間內(nèi)，無論何種工件規(guī)模，IAGA解的質(zhì)量均明顯優(yōu)于GA，且IAGA的迭代次數(shù)多于GA；與LR算法相比，在求解較大規(guī)模工件時，IAGA的性能更好，更符合實際生產(chǎn)對時間的要求.

[1] 汪恭書, 唐立新. 連鑄—軋制生產(chǎn)中帶有批決策的排序問題的建模與優(yōu)化方法[J]. 自動化學報, 2012, 38(10): 1713-1720.

[2] 洪悅, 唐立新, 張顏顏. 基于數(shù)據(jù)子空間PLS建模技術的熱軋軋制力優(yōu)化設定[J]. 控制與決策, 2014, 29(7): 1199-1204.

[3] YU Y S, JIE J C, ZHANG S. Three-layer Al/Al-B4C composite material prepared by casting and hot rolling[J]. Powder metallurgy and metal ceramics, 2015, 54(7/8): 390-396.

[4] TAN Y, MONCH L, FOWLER J W. Proceedings of winter simulation conference[C]. 2015.

[5] 陳成棟, 陳華平, 朱頎,等. 兩階段流水車間批調(diào)度問題的蟻群優(yōu)化算法[J]. 計算機工程, 2012, 38(19): 137-141.

[6] 黃錦鈿, 劉建軍, 陳慶新,等. 兩機flow-shop類型模具熱處理車間批調(diào)度算法[J]. 計算機集成制造系統(tǒng), 2014, 20(7): 1665-1674.

[7] 程八一, 胡笑旋. 差異作業(yè)批調(diào)度的流水車間問題及近似算法[J]. 系統(tǒng)工程學報, 2011, 26(3): 393-399.

[8] XUAN H, LI B. Scheduling dynamic hybrid flowshop with serial batching machines[J].Journal of the operational research society, 2013(64): 825-832.

[9] COSTA A, CAPPADONNA F A, FICHERA S. A novel genetic algorithm for the hybrid flow shop scheduling with parallel batching and eligibility constraints[J]. International journal of advanced manufacturing technology, 2014, 75(5/8): 833-847.

[10] LI D, MENG X, LIANG Q. A heuristic-search genetic algorithm for multi-stage hybrid flowshop scheduling with single processing machines and batch processing machines[J]. Journal of intelligent manufacturing, 2015(26): 873-890.

[11] SRINIVAS M, PATNAIL K L M. Adaptive probabilities of crossover and mutation in genetic algorithms[J]. IEEE transactions on system, man and cybernetics, 1994, 24(4): 656-667.

[12] XU Y C, TAN W N. The modeling and simulation of flow shop scheduling problem based on adaptive genetic algorithm[J]. RISTI-Revista iberica de sistemas e tecnologias de informacao, 2016(17): 25-40.

[13] SUN H M, YU J W, WANG H L. Proceedings of Chinese intelligent automation conference-intelligent technology and systems[C], 2015.

[14] ZHU H M, ZHAO J F, WANG M L. Adaptive genetic algorithm for Hybrid Flow-Shop scheduling[C]. 3rd international conference on advanced engineering materials and technology, 2013.

[15] ZHAO J F, ZHU X C, WANG B S. Hybrid flow-shop scheduling method and simulation based on adaptive genetic algorithm[C]. Applied mechanics and materials, 2014.

Abstract: Based on steel making-continuous casting - hot rolling production process in iron and steel industry, the problem of schedulingnjobs in a multi-stage flexible flowshop with batching machines at some middle stage was studied. The batching production stage consisted of multiple serial batching machines in parallel, and the other stages contained discrete machines. Firstly, a mathematical model was formulated to minimize the total weighted completion time with the consideration of job dynamic arrival, transportation time between the adjacent stages and machine setup time. Then, an improved adaptive genetic algorithm was developed for this NP-hard problem where the genetic parameters were associated with the iteration number and the fitness function values. Computational experiments tested a large number of random data for up to 150 jobs. The results show that the proposed algorithm could find the better solutions within a shorter period of time, as compared with the general genetic algorithm. The comparison with Lagrangian relaxation showed that the improved genetic algorithm performed better on solution quality for medium and large sized problems.

Keywords: flexible flowshop scheduling;batch machines;total weighted completion time;self-adaptive genetic algorithm;self-adaptive adjustment

Multi-stageFlexibleFlowshopSchedulingwithBatchingMachines

WANG Junyan, WANG Xueyuan, XUAN Hua

(School of Management Engineering, Zhengzhou University, Zhengzhou 450001, China)

王薛苑(1985— )，男，河南鄭州人，鄭州大學講師，博士，主要從事生產(chǎn)調(diào)度等方面的研究，E-mail：wangxueyuan@zzu.edu.cn.

TB49

A

10.13705/j.issn.1671-6833.2017.05.012

2017-01-16；

2017-04-30

國家自然科學基金資助項目(U1604150)；教育部人文社會科學研究基金項目(15YJC630148)；鄭州大學優(yōu)秀青年教師發(fā)展基金項目(1421326092)

1671-6833(2017)05-0086-05