考慮準備時間和加工速度的紡織纖維實驗加工調度

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

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

0 引 言

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

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

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

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

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

1.1 模型假設

問題基于以下基本假設：

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

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

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

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

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

1.2 參數(shù)符號

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

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

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

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

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

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

1.3 決策變量

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

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

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

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

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

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

1.4 目標函數(shù)

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

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

2 正弦余弦算法（SCA）

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

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

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

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

3.1 編碼方式

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

3.2 解碼方式

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

表1 4個任務2個機器的編碼信息

解碼：

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

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

圖1 2臺平行機4個實驗任務的調度方案

3.3 差分變異策略

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

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

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

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

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

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

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

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

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

4 仿真實驗

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

4.1 問題松弛的下界分析

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

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

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

4.2 評判指標

（1）將任一算法alg所求得的解的質量用相對偏差RPD指標來衡量：

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

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

4.3 實驗參數(shù)

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

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

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

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

4.4 實驗分析

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

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

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

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

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

表4 各算法的性能指標比較

5 結 語

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