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

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

0 引 言

在平行機(jī)調(diào)度研究中，準(zhǔn)備時間（安裝時間）分兩大類，一是準(zhǔn)備時間與次序無關(guān)［1］，準(zhǔn)備時間可視為實(shí)驗(yà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ù)雜的問題，在制造與實(shí)驗(yàn)領(lǐng)域中有著廣泛的應(yīng)用。Ozcan［3］考慮了一類安裝時間與次序相關(guān)的裝配調(diào)度。Sarahi等［4］考慮了安裝時間與次序相關(guān)的平行機(jī)調(diào)度問題，并建立了混合整數(shù)規(guī)劃模型。Shen等［5］在柔性車間模型中考慮了安裝時間與次序相關(guān)的調(diào)度問題并討論了問題的下界。

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

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

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

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

1.1 模型假設(shè)

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

（1）每個實(shí)驗(yàn)的信息已知，即加工時間和交付期等信息；

（2）每臺機(jī)器在任意時刻只能進(jìn)行一個實(shí)驗(yàn)；

（3）機(jī)器一旦開始某個實(shí)驗(yàn)，中途不可中斷；

（4）計劃周期的初始時刻所要求做的實(shí)驗(yàn)材料已到位；

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

1.2 參數(shù)符號

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

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

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

I—實(shí)驗(yàn)的集合，N為最后一個實(shí)驗(yàn)；i，j∈I，I＝｛1，2…，N｝。

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

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

1.3 決策變量

pi，m—實(shí)驗(yàn)i在機(jī)器m的實(shí)驗(yàn)時間，其中，pi，m＝i/vm。

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

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

Si，m—機(jī)器m對實(shí)驗(yàn)任務(wù)i開始時間。

Ci，m—機(jī)器m對實(shí)驗(yàn)任務(wù)i完成時間。

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

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

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

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

2 正弦余弦算法（SCA）

在SCA［14］中，當(dāng)正余弦函數(shù)系數(shù)大于1或者小于-1時，進(jìn)行全局尋優(yōu)；當(dāng)正余弦函數(shù)系數(shù)介于-1到1之間時，進(jìn)行局部尋優(yōu)。該算法最大的特點(diǎn)是利用正余弦函數(shù)值的波動來實(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個隨機(jī)參數(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算法流程或偽代碼參見文獻(xiàn)［13-14］。

3 改進(jìn)的正弦余弦算法（ISCA）

3.1 編碼方式

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

3.2 解碼方式

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

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

解碼：

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

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

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

3.3 差分變異策略

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

3.4 改進(jìn)正弦余弦算法（ISCA）流程

綜上所述，紡織纖維實(shí)驗(yàn)排程調(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隨機(jī)產(chǎn)生參數(shù)4，根據(jù)概率值大小按式（13）進(jìn)行個體更新，然后計算整個種群的最優(yōu)值。將現(xiàn)有函數(shù)值與上一代最優(yōu)值進(jìn)行比較，若前者較好，則改變當(dāng)前最優(yōu)值，則接受新解。

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

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

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

4 仿真實(shí)驗(yàn)

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

4.1 問題松弛的下界分析

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

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

目前我國的教育對口支援主要有三種模式，包含教育部直接組織施行的對口支援、內(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）。本文運(yùn)行5 次，取平均值A(chǔ)vg.RPD。Avg.RPD值越小，說明算法alg所得解的目標(biāo)值越接近下界，表明解的質(zhì)量越好。

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

4.3 實(shí)驗(yàn)參數(shù)

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

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

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

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

4.4 實(shí)驗(yàn)分析

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

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

圖2 3臺機(jī)器100個實(shí)驗(yàn)任務(wù)的算法收斂曲線圖

圖3 3臺機(jī)器200個實(shí)驗(yàn)任務(wù)的算法收斂曲線圖

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

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

5 結(jié) 語

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