考慮準(zhǔn)備時間和加工速度的紡織纖維實驗加工調(diào)度

黃基誕，李 楠，晏愛敏，黃曉虎

（東華大學(xué)a.旭日工商管理學(xué)院；b.信息科學(xué)與技術(shù)學(xué)院，上海200051）

0 引 言

在平行機調(diào)度研究中，準(zhǔn)備時間（安裝時間）分兩大類，一是準(zhǔn)備時間與次序無關(guān)［1］，準(zhǔn)備時間可視為實驗任務(wù)加工時間的一部分來考慮；二是準(zhǔn)備時間與次序相關(guān)時［2］，準(zhǔn)備時間（安裝時間）就會對調(diào)度結(jié)果產(chǎn)生影響，無法忽略。如何解決準(zhǔn)備時間（安裝時間）與次序相關(guān)的調(diào)度問題引起了學(xué)術(shù)界廣泛的研究興趣。具有與次序相關(guān)的準(zhǔn)備時間（安裝時間）的加工調(diào)度問題作為一類較為復(fù)雜的問題，在制造與實驗領(lǐng)域中有著廣泛的應(yīng)用。Ozcan［3］考慮了一類安裝時間與次序相關(guān)的裝配調(diào)度。Sarahi等［4］考慮了安裝時間與次序相關(guān)的平行機調(diào)度問題，并建立了混合整數(shù)規(guī)劃模型。Shen等［5］在柔性車間模型中考慮了安裝時間與次序相關(guān)的調(diào)度問題并討論了問題的下界。

紡織纖維實驗中制造或加工各類新型纖維需要有準(zhǔn)備時間，而且該準(zhǔn)備時間與纖維有關(guān)［6］，故安裝時間與加工的材料次序相關(guān)；當(dāng)他屬于同種產(chǎn)品加工的時候，準(zhǔn)備時間較少；否則具有復(fù)雜的準(zhǔn)備時間，比如更換和清洗組件等操作。機器更換組件造成的準(zhǔn)備時間是本文討論實驗的特征，可以視為依賴于任務(wù)序列的準(zhǔn)備時間。金輝等［7］研究了滌綸短纖維制造過程中的管理優(yōu)化，并提出基于TS/VDS算法對該調(diào)度問題進行優(yōu)化。金輝等［8］繼續(xù)針對紡絲組件更換比較耗時特點，提出了用數(shù)學(xué)動態(tài)規(guī)劃法求解組件更換調(diào)度問題。隨后陸晨［9］對化纖的制造特點和特征進行分析。

隨著科技的發(fā)展及新問題的不斷出現(xiàn)，近些年又出現(xiàn)一批新的算法，如灰狼優(yōu)化算法［10］、煙花算法［11］，螢火蟲算法［12］等.這些算法的優(yōu)點是能夠在很短的時間內(nèi)給出接近最優(yōu)的解。文獻［13］中提出一種啟發(fā)式算法：正弦余弦算法（Sine Cosine Algorithm，SCA）。該算法數(shù)學(xué)模型簡單、參數(shù)設(shè)置少、且容易實現(xiàn)，僅僅通過正余弦函數(shù)值的波動變化來實現(xiàn)最優(yōu)解的搜索。雖然SCA已被證明在部分問題優(yōu)化、收斂速度、精度等方面均優(yōu)于經(jīng)典算法如遺傳算法（GA）、粒子群算法（PSO）等［13］，但是也存在易出現(xiàn)早熟收斂缺點。已有學(xué)者將它用于電力系統(tǒng)經(jīng)濟調(diào)度［14］和應(yīng)用反向?qū)W習(xí)改進SCA算法［15］。本文將改進正弦余弦算法（Improved Sine Cosine Algorithm，ISCA）求解實驗排程，并取得了比較好的效果。

1 問題描述及數(shù)學(xué)模型

紡織學(xué)院所有學(xué)生（主要是碩士、博士）都有一個共享的纖維加工和制造實驗室，供學(xué)生完成自己所需的實驗新型纖維材料加工實驗（以下簡稱實驗）。研究一個時間周期內(nèi)有N個實驗（纖維加工實驗）需要在M臺機器上加工，每臺機器加工速度不一致，機器m都有自己恒定的加工速度為vm，不失一般性，假定機器的加工速度v1≥v2≥…≥vM。并根據(jù)實際情況考慮每個實驗i的教師布置時間（下達(dá)時間）ri，同時考慮加工不同纖維時機器需要更換和清洗組件的準(zhǔn)備時間，正常情形下進行的每個實驗任務(wù)i所需時間為～pi和教師要求正常完成實驗期限di。要求實驗室管理老師設(shè)計一個調(diào)度方案使得最小化最大完工時間最小。

1.1 模型假設(shè)

問題基于以下基本假設(shè)：

（1）每個實驗的信息已知，即加工時間和交付期等信息；

（2）每臺機器在任意時刻只能進行一個實驗；

（3）機器一旦開始某個實驗，中途不可中斷；

（4）計劃周期的初始時刻所要求做的實驗材料已到位；

（5）除了一個實驗與接下來另一個實驗有轉(zhuǎn)化組件間歇，機器的實驗加工速率恒定并可持續(xù)工作。

1.2 參數(shù)符號

本文其他所使用的符號如下：

i—實驗任務(wù)編號，0為虛擬初始實驗任務(wù)。

B—機器的集合。m為機器的編號，m∈B，B＝｛1，2，…，M｝。

I—實驗的集合，N為最后一個實驗；i，j∈I，I＝｛1，2…，N｝。

ti，j，m—實驗i完成后緊接著實驗j在機器m的準(zhǔn)備所需時間，其中t0，i，m為在機器m上的初始實驗i的準(zhǔn)備時間。

L—一個足夠大的正數(shù)。

1.3 決策變量

pi，m—實驗i在機器m的實驗時間，其中，pi，m＝i/vm。

Xi，j，m∈｛0，1｝—如果實驗任務(wù)i的在機器m上完成后，緊接著做實驗任務(wù)j，則Xi，j，m＝1；否則為0。

δi，m∈（0，1）—如果實驗任務(wù)i的在機器m上加工，則δi，m＝1；否則為0。

Si，m—機器m對實驗任務(wù)i開始時間。

Ci，m—機器m對實驗任務(wù)i完成時間。

Cmax—最大完工時間，即最后一個實驗任務(wù)完成時間。

1.4 目標(biāo)函數(shù)

目標(biāo)函數(shù)是最小化最大完工時間。

式（2）為最大完工時間不小于每個實驗i的完成時間。式（3）為實驗i在機器m上加工的完成時間和開始時間的關(guān)系。式（4）為實驗i開始時間必須大于等于實驗布置時間（下達(dá)時間）。式（5）為實驗i和實驗j在同一臺機器上加工，先后順序時間限制。式（6）為實驗i完成時間必須小于教師要求的時間。式（7）為實驗i在機器m上的加工時間計算方式。式（8）～（11）為實驗i的只能在某一臺機器上加工，并且只加工一次。式（12）為決策變量的取值范圍。

2 正弦余弦算法（SCA）

在SCA［14］中，當(dāng)正余弦函數(shù)系數(shù)大于1或者小于-1時，進行全局尋優(yōu)；當(dāng)正余弦函數(shù)系數(shù)介于-1到1之間時，進行局部尋優(yōu)。該算法最大的特點是利用正余弦函數(shù)值的波動來實現(xiàn)最優(yōu)解搜尋。在SCA中，假設(shè)種群規(guī)模為N，優(yōu)化問題的每個解對應(yīng)搜索空間（維度為d）中對應(yīng)個體的位置，并Xi＝｛xi1，xi2，…，xid｝，表示第i（i＝1，2，…，N）個個體的位置，當(dāng)前所有個體經(jīng)過的最好位置表示為X*，在每一次迭代中，群體中個體均按如下更新位置［11-13］，即：

式中：t為當(dāng)前迭代次數(shù)；為閾值，本文取值為0.5。為3個隨機參數(shù)［14-15］，1稱為控制參數(shù)，是一個關(guān)鍵參數(shù)，會影響算法全局尋優(yōu)和局部搜尋最優(yōu)解的性能。2的定義［14-16］如下：

式中：t為目前迭代次數(shù)；α＞0為預(yù)設(shè)的常數(shù)；T為最大迭代次數(shù)。標(biāo)準(zhǔn)SCA算法流程或偽代碼參見文獻［13-14］。

3 改進的正弦余弦算法（ISCA）

3.1 編碼方式

假設(shè)有N個實驗任務(wù)，按實驗的下達(dá)時間排序（如果下達(dá)時間一樣，按實驗任務(wù)從大到小排序）。為了編程方便，本文采用2N維實數(shù)位置向量表示N個實驗任務(wù)和M臺機器的調(diào)度序列。向量中的2N維實數(shù)的取值范圍是［1，M+1），M表示機器數(shù)量。編碼分成兩個部分，前N位表示實驗任務(wù)加工順序；后N位的整數(shù)部分表示N個實驗任務(wù)分配在哪臺機器上加工。

3.2 解碼方式

用一個例子說明編/解碼的過程。例如有2臺機器處理4個實驗任務(wù)（按釋放時間排序）：v1＝1，v2＝2，，（r1，r2，r3，r4）＝（2，3，4，5），為了簡明扼要地說明問題，暫時都假設(shè)ti，j，m＝2，編碼信息見表1。

表1 4個任務(wù)2個機器的編碼信息

解碼：

（1）取前N位，這里4個實驗（N＝4），取前4位，根據(jù)數(shù)字的大小排序，得出加工順序：1?3?4?2。

（2）然后，取接下來的N位（N＝4）整數(shù)部分，計算出每個實驗任務(wù)被分配的機器號。這里有4個實驗，表1分別列出第1、3個實驗的在機器2（見圖1中M2）加工，第2、4實驗任務(wù)在機器1（見圖1中M1）上加工。

圖1 2臺平行機4個實驗任務(wù)的調(diào)度方案

3.3 差分變異策略

差分進化算法優(yōu)點是具有強大的尋優(yōu)能力，收斂速度快。為了快速引導(dǎo)群體找到最優(yōu)解，本文在差分進化算法的基礎(chǔ)上提出了差分變異策略：

3.4 改進正弦余弦算法（ISCA）流程

綜上所述，紡織纖維實驗排程調(diào)度的ISCA流程可描述如下：

步驟1初始化種群Xi，（i＝1，2，…，n），如種群規(guī)模NP，問題維數(shù)D、閾值，最大迭代次數(shù)等參數(shù)T、預(yù)設(shè)常數(shù)a等。

步驟3利用式（14）計算控制參數(shù)1。

步驟4隨機產(chǎn)生參數(shù)4，根據(jù)概率值大小按式（13）進行個體更新，然后計算整個種群的最優(yōu)值。將現(xiàn)有函數(shù)值與上一代最優(yōu)值進行比較，若前者較好，則改變當(dāng)前最優(yōu)值，則接受新解。

步驟5對當(dāng)前粒子進行差分變異機制的擾動，擾動后與當(dāng)前質(zhì)量最優(yōu)的粒子進行比較；若較好，則改變當(dāng)前最優(yōu)值，選擇接受新解，并用較好的個體進行替換。

步驟6判斷當(dāng)前粒子的適應(yīng)度是否優(yōu)于之前種群的全局最優(yōu)解。若是，將當(dāng)前的粒子的適應(yīng)度值替換為全局最優(yōu)解。

步驟7若未達(dá)到最大迭代次數(shù)，則返回步驟3；否則，輸出全局最優(yōu)位置。

4 仿真實驗

為驗證算法尋優(yōu)性能，分小數(shù)據(jù)和大數(shù)據(jù)兩部分進行試驗。算法采用Matkab2014a編程，實驗運行環(huán)境為：CPU 2.1 GHz，內(nèi)存4 GB，Windows7 操作系統(tǒng)（64 bit）。

4.1 問題松弛的下界分析

定理1由于實驗布置時間是隨機的，如果最后一個實驗下達(dá)時間遠(yuǎn)遠(yuǎn)大于此前其他實驗下達(dá)時間；即假設(shè)最后一個實驗下達(dá)時，其他先前實驗都完成了，將最后一個實驗安排到速度最快的機器1上加工，顯然是最優(yōu)解的一個下界：

定理2由于實驗纖維種類是隨機的，故松弛2個條件。假設(shè)本周期內(nèi)所有的實驗都是一個類型的，實驗之間的切換時間可以忽略不計，那么只有一次準(zhǔn)備時間；還有一個松弛條件，所有的機器加工速度都是一樣的，都是最快的那種機器。該問題的下界為那么下界又可以表示為：

目前我國的教育對口支援主要有三種模式，包含教育部直接組織施行的對口支援、內(nèi)地省市對西部地區(qū)的對口支援以及西部省（市、自治區(qū)）組織的大中城市對口支援工作。[1]從支援少數(shù)民族高校的政策發(fā)展歷史中，可以看到國家對支援工作的重視程度。

4.2 評判指標(biāo)

（1）將任一算法alg所求得的解的質(zhì)量用相對偏差RPD指標(biāo)來衡量：

式中：faig為算法alg中計算獲得的目標(biāo)函數(shù)值；LB*＝max（LB1，LB2）。本文運行5 次，取平均值A(chǔ)vg.RPD。Avg.RPD值越小，說明算法alg所得解的目標(biāo)值越接近下界，表明解的質(zhì)量越好。

（2）Time（s）：CPU平均運行時間，指算法求得最優(yōu)解所花費的平均計算時間，算例運行5次，取5次的平均計算時間。

4.3 實驗參數(shù)

本實驗用ERD（Earliest Release Date）規(guī)則來做其中的對比之一。ERD規(guī)則（先到先服務(wù)規(guī)則）：實驗根據(jù)下達(dá)時間從小到大排序，然后依次選擇機器最空閑進行加工；若多于一個實驗任務(wù)釋放時間相同，則選擇加工時間長的實驗任務(wù)先進行加工。本文采用隨機測試算例，算例規(guī)模和參數(shù)見表2。

各算法的參數(shù)設(shè)置見表3。其中c1和c2為粒子群算法中的學(xué)習(xí)因子，ω為PSO中的慣性權(quán)重。

表2 算例的參數(shù)分類和取值范圍

表3 算法參數(shù)設(shè)置

4.4 實驗分析

對于上述實例用ISCA、SCA和PSO 3種算法進行求解，并對實驗結(jié)果做參照對比。由于篇幅有限，就算法收斂曲線圖各隨機選取2組：N＝200，M＝3和N＝100，M＝3。

從圖2、3分別在N＝100和N＝200的兩種情況下描繪了算法的收斂曲線；從圖中可以看出，當(dāng)達(dá)到一定的迭代次數(shù)的時候，優(yōu)化目標(biāo)無法再改進。另一方面，可以看出，SCA和PSO算法有著類似的收斂速度，而ISCA的收斂性能明顯優(yōu)于SCA和PSO。

圖2 3臺機器100個實驗任務(wù)的算法收斂曲線圖

圖3 3臺機器200個實驗任務(wù)的算法收斂曲線圖

通過不同規(guī)模下的實驗，很好地驗證了改進正余弦算法的有效性。從表4中的第3和第6列可以看出，該算法比我們經(jīng)常在實際中用的ERD模式的RPD節(jié)約4%，說明各算法運行的穩(wěn)定性較好，而且解的質(zhì)量令人滿意。

表4 各算法的性能指標(biāo)比較

5 結(jié) 語

本文探討了準(zhǔn)備時間具有次序有關(guān)的短纖維加工實驗調(diào)度，建立了混合整數(shù)規(guī)劃模型，設(shè)計了ISCA進行求解，數(shù)值實驗表明所建立的模型能有效地減少實驗之間切換所必需的準(zhǔn)備時間；達(dá)到減少整體實驗完成時間，最終達(dá)到減少損耗和提高實驗設(shè)備利用率；同時也證明了所設(shè)計的算法的有效性能。為今后存在類似有次序有關(guān)的準(zhǔn)備時間的實驗排程比如生物實驗等方面提供參考。