基于啟發(fā)式優(yōu)化算法的鋼化玻璃加工車間調(diào)度優(yōu)化

王 璐 張小寧 楊學(xué)男 吳 輝

（1.上海民航職業(yè)技術(shù)學(xué)院，上海 200232；2.同濟(jì)大學(xué)經(jīng)濟(jì)與管理學(xué)院，上海 200092）

基于啟發(fā)式優(yōu)化算法的鋼化玻璃加工車間調(diào)度優(yōu)化

王 璐1張小寧2楊學(xué)男2吳 輝1

（1.上海民航職業(yè)技術(shù)學(xué)院，上海 200232；2.同濟(jì)大學(xué)經(jīng)濟(jì)與管理學(xué)院，上海 200092）

在對鋼化玻璃加工車間調(diào)度問題分析研究基礎(chǔ)上，將鋼化玻璃加工車間調(diào)度問題歸結(jié)為混合流水車間調(diào)度問題。建立了以總完工時間最短為目標(biāo)，并考慮了在鋼化爐中存在加工批量約束的整數(shù)規(guī)劃模型，同時設(shè)計(jì)了基于ECT（完工時間最早先加工）規(guī)則和FCFS（先到先服務(wù)）規(guī)則的啟發(fā)式算法求解該模型。通過將所設(shè)計(jì)算法的求解結(jié)果與Cplex求解結(jié)果進(jìn)行比較，驗(yàn)證了模型和算法的高效性。同時測試結(jié)果表明，在求解大規(guī)模調(diào)度問題時，本文所設(shè)計(jì)的算法的求解速度遠(yuǎn)遠(yuǎn)優(yōu)于精確算法。

鋼化玻璃加工；混合流水車間；啟發(fā)式優(yōu)化算法

1 問題描述

鋼化玻璃的生成主要包括3個階段：切割、印刷、鋼化，典型的鋼化玻璃加工的基本流程如圖1所示。在切割車間將普通的玻璃按照最終產(chǎn)品尺寸進(jìn)行切割后，進(jìn)入印刷車間進(jìn)行印刷，由于不同顏色的印刷效果不同，因而不同顏色所需的印刷次數(shù)存在差異，所有印刷完成的玻璃最后都要進(jìn)入鋼化爐進(jìn)行鋼化。

圖1 鋼化玻璃加工的基本流程

在實(shí)際鋼化玻璃生產(chǎn)過程中，雖然切割車間、印刷車間有多條生產(chǎn)線，但是產(chǎn)線之間還是存在一定的差異，因而各條產(chǎn)線上所能加工的產(chǎn)品的個產(chǎn)線上的makespan；

Step4將印刷完成的工件從list2中移除，轉(zhuǎn)至step2，若list2中沒有待印刷工件，停止；

Stage2計(jì)算的時間復(fù)雜度為O(n log n)；

Stage3（鋼化爐）主要遵循先湊成整批的先加工，也即先到先服務(wù)規(guī)則（FCFS）：

Step1根據(jù)N個工件在印刷車間完工時刻的先后順序生成一個序列（list3）；

Step2選擇list3里面第一個能湊成整批的工件進(jìn)行加工，若list3中無待加工的工件，轉(zhuǎn)至Step6，若list3仍有工件且不能湊成整批，轉(zhuǎn)至Step4；

Step3更新makespan，將已加工的工件從list3中移除，并轉(zhuǎn)至step2；

Step4若list3還有未湊成整批的工件，則將使makespan增加最少的工件先加工，若list3中無待加工的工件，轉(zhuǎn)至Step6；

Step5更新makespan，將已加工的工件從list3中移除，并轉(zhuǎn)至step4；

Step6輸出makespan并停止；

Stage3計(jì)算的時間復(fù)雜度為O(n)。

圖2 啟發(fā)式算法流程圖

4 數(shù)值實(shí)例測試

為了驗(yàn)證本文設(shè)計(jì)算法的有效性，本文將從計(jì)算結(jié)果和計(jì)算時間兩個方面與相同參數(shù)設(shè)置下用Cplex計(jì)算出的結(jié)果進(jìn)行比較。

4.1 實(shí)驗(yàn)設(shè)置

以Matlab為開發(fā)環(huán)境，采用的InterCore i52.5GHz，4GBRAMPC機(jī)，驗(yàn)證本文所提出的啟發(fā)式算法的性能，問題規(guī)模從5～11個工件逐步擴(kuò)大到25～31和45～51個工件，在各個問題規(guī)模下均隨機(jī)產(chǎn)生5個測試數(shù)據(jù)，并計(jì)算出5次運(yùn)行結(jié)果中makespan的最大、最小值和平均值，以及求解時間的最大、最小值和平均值。由于Cplex求解問題的規(guī)模有限制，因此在求解小規(guī)模問題設(shè)定讓Cplex求出精確解，在求解中、大規(guī)模問題時，設(shè)定Cplex運(yùn)行的時間（設(shè)定為600s），超過設(shè)定時間沒有計(jì)算出精確結(jié)果即結(jié)束運(yùn)行并輸出當(dāng)前的求解結(jié)果。

定義為Cplex運(yùn)行結(jié)果與本算法計(jì)算結(jié)果中makespan之間的差距，即

表2 兩種算法的測試結(jié)果（小規(guī)模）

表3 兩種算法的測試結(jié)果（中規(guī)模）

4.2 運(yùn)行結(jié)果分析

表2～表4分別列出了在不同規(guī)模下Cplex計(jì)算結(jié)果和本文提出的啟發(fā)式算法計(jì)算結(jié)果的對比。

從表2～表4兩種算法的運(yùn)行結(jié)果的對比可以得出以下結(jié)論：

（1）對于小規(guī)模問題(玻璃數(shù)為5～11)，雖然本文提出的啟發(fā)式算法求解結(jié)果與Cplex計(jì)算出的精確解之間的gap超過了將近15%，但是從計(jì)算時間角度來看，與Cplex計(jì)算時間相比，本文提出的啟發(fā)式算法能在相當(dāng)短的時間內(nèi)找到一個令人滿意的近優(yōu)解。

（2）對于中規(guī)模問題（玻璃數(shù)為25～31），本文提出的啟發(fā)式算法結(jié)果與在設(shè)定時間內(nèi)Cplex計(jì)算出的結(jié)果之間的gap已經(jīng)縮小了很多，且求解速度遠(yuǎn)遠(yuǎn)優(yōu)于Cplex的計(jì)算時間，這在一定程度上說明所設(shè)計(jì)算法的高效性。

（3）對于大規(guī)模問題（玻璃數(shù)＞45），測試結(jié)果表明，Cplex在600s內(nèi)計(jì)算出的結(jié)果已經(jīng)比不上本文所設(shè)計(jì)算法在1s不到的時間內(nèi)計(jì)算出的調(diào)度方案。實(shí)際上，通過測試發(fā)現(xiàn)，當(dāng)問題規(guī)模超過30塊玻璃時，用Cplex求解需要花費(fèi)相當(dāng)長的時間，而本文所設(shè)計(jì)的算法在超大規(guī)模（玻璃數(shù)＞10000）時，求解時間也僅需10s左右，考慮到實(shí)際鋼化玻璃加工車間的玻璃數(shù)量很大，因而本文所設(shè)計(jì)的算法在解決實(shí)際鋼化車間調(diào)度問題時仍然具有高效性。

表4 兩種算法的測試結(jié)果（大規(guī)模）

[1]FattahiP,HosseiniSMH,JolaiF,et al.Abranch and bound algorithm for hybrid flow shop scheduling problem with setup time and assembly operations[J].AppliedMathematicalModelling,2014,38(1):119-134.

[2]ChengM,TadikamallaPR,ShangJ,et al.Bicriteria hierarchical optimization of two-machine flow shop scheduling problem with time-dependent deteriorating jobs[J].EuropeanJournal of operational research,2014,234(3):650-657.

[3]MarichelvamMK,PrabaharanT.Performance evaluation of an improved hybrid genetic scatter search(IHGSS)algorithm for multistage hybrid flow shop scheduling problems with missing operations[J].InternationalJournal ofIndustrial andSystemsEngineering,2014,16(1):120-141.

[4]李俊青,潘全科,王法濤.求解混合流水線調(diào)度問題的離散人工蜂群算法[J].運(yùn)籌與管理,2015,1:023

[5]宋代立,張潔.蟻群算法求解混合流水車間分批調(diào)度問題[J].計(jì)算機(jī)集成制造系統(tǒng),2013,19(07):1640-1647.

[6]LinQ,GaoL,LiX,et al.Ahybrid backtracking search algorithm for permutation flow-shop scheduling problem[J].Computers&IndustrialEngineering,2015,85:437-446.

[7]SoltaniSA,KarimiB.Cyclic hybrid flow shop scheduling problem with limited buffers and machine eligibility constraints[J].TheInternationalJournal ofAdvancedManufacturingTechnology,2015,76(9-12):1739-1755.

[8]張其亮，陳永生.基于混合粒子群-NEH算法求解無等待柔性流水車間調(diào)度問題[J].系統(tǒng)工程理論實(shí)踐,2014,34(3):802-809.

Heuristic Optimization Algorithm for Tempered Glass Production shop Scheduling Problem

Wang Lu1Zhang Xiaoning2Yang Xuenan2Wu Hui1
（1. Shanghai Civil Aviation College, Shanghai 200232; 2.School of Economics & Management，Tongji University, Shanghai 200092）

Based on the analysis of tempered glass production shop scheduling problem, it is formulated as a hybrid flowshop scheduling problem. Combined with the scheduling theory, a scheduling model with processing batch of tempering furnace is presented. Based on ECT rule and FCFS rule, a heuristic optimization algorithm is developed to solve the special scheduling model. By comparing the numerical result with the result calculated by Cplex, effectiveness and efficiency of the proposed algorithm and model are verified, also the numerical result also indicated that, the proposed heuristic algorithm has great advantage in solving speed than exact algorithm when solving large scale scheduling problem.

tempered glass processing; hybrid flow-shop; heuristic optimization algorithm

F252

A

1005-9679(2017)02-0079-06

2016-12-17

國家自然科學(xué)基金重點(diǎn)項(xiàng)目（編號71531011）資助

王璐，上海民航職業(yè)技術(shù)學(xué)院，講師，碩士學(xué)位，主要研究機(jī)場物流優(yōu)化；張小寧，同濟(jì)大學(xué)經(jīng)濟(jì)與管理學(xué)院，研究員，博士生導(dǎo)師，主要研究交通管理及物流優(yōu)化；楊學(xué)男，同濟(jì)大學(xué)經(jīng)濟(jì)與管理學(xué)院，研究生，主要研究優(yōu)化調(diào)度問題；吳輝，上海民航職業(yè)技術(shù)學(xué)院，講師，碩士學(xué)位，主要研究機(jī)場物流優(yōu)化。