邊 倩

（山西交通職業(yè)技術學院，太原 030031）

0 引言

隨著制造業(yè)的不斷發(fā)展，產(chǎn)品質(zhì)量提升的同時面臨很多工業(yè)操作優(yōu)化問題，其中，n個作業(yè)必須在m臺機器上按順序處理，就是非常典型的車間流調(diào)度問題。在一個置換流車間調(diào)度問題中，所有機器上的作業(yè)必須以相同的順序進行處理，證明了該問題是非常困難的。因此，不能用常規(guī)的線性方法來解決這些問題。在過去的幾十年里，研究人員開發(fā)了許多啟發(fā)式和元啟發(fā)式的流程車間調(diào)度問題，以找到最優(yōu)的解決方案。重要的建設性啟發(fā)法是由Campbell等人（1970）、Dannenbring（1977）和Nawaz等人（1983）提出的。調(diào)度可以定義為在一段時間內(nèi)分配資源，以執(zhí)行一組任務來優(yōu)化一個或多個目標函數(shù)。調(diào)度是一個決策過程。資源可以稱為機器，任務可以稱為作業(yè)。在當今的競爭環(huán)境中，有效的調(diào)度在制造業(yè)和服務業(yè)中都扮演著重要的角色。本文研究了具有n個作業(yè)和m臺機器的置換流車間調(diào)度問題。

1 優(yōu)化算法在工業(yè)流水調(diào)度優(yōu)化中的應用發(fā)展

Murata等人（1996）利用遺傳算法解決了流水車間調(diào)度問題。Nowicki和Smutnicki（1998）應用禁忌搜索算法解決了并行機器的流程車間調(diào)度問題。Nearchou（2004）利用混合模擬退火算法解決了流水作業(yè)調(diào)度問題。自Johnson（1954）提出流程車間調(diào)度問題以來，它一直是過去幾十年中最著名的問題之一。Johnson開發(fā)了一個精確的算法來最小化最大完工時間來解決n個工作和2臺機器的流水車間調(diào)度問題。流程車間調(diào)度問題是一個組合優(yōu)化問題。流程車間調(diào)度問題可能被陳述排序流車間調(diào)度問題中最小化最大完工時間和總流水時間的退火算法。Haq等人（2006）提出了一種分散搜索算法，使流水作業(yè)問題的最大完工時間最小化。Onwubolu和Davendra（2006）提出了一種差分演化算法來解決最小化完工時間的流水車間調(diào)度問題。Ruiz和Stutzle（2007）提出了一種新的置換流車間調(diào)度問題的迭代貪婪算法。Liao等人（2007）提出了一種用于流水車間調(diào)度問題的粒子群優(yōu)化算法。劉集等人（2008）開發(fā)了一種有效的混合算法，該算法基于粒子群優(yōu)化算法，以最大限度地縮短連續(xù)機器之間有限緩沖區(qū)的置換流車間調(diào)度問題的完成時間。Saravanan 等人（2008）評估了分散搜索算法對流水車間調(diào)度問題最大完工時間最小化的性能。Kuo等人（2009）提出了一種基于混合粒子群優(yōu)化模型、隨機密鑰編碼和個體增強（IE）方案的高效流水作業(yè)調(diào)度算法。Oian et al。（2009）對無等待流水作業(yè)調(diào)度問題提出了一種有效的混合微分演化，使最大完工時間最小化。最近，Lei和Wang（2016）提出了一種有效的鄰域搜索算法，用于調(diào)度批量處理機器車間流，使其時間最小化。

2 一種改進的新型布谷鳥搜索算法的提出

2.1 布谷鳥搜索（Cuckoo Search，CS）算法

布谷鳥搜索（Cuckoo Search，CS）算法是Yang and Deb（2009）最新開發(fā)的一種基于種群的元啟發(fā)式算法。Yang和Deb（2010）使用CS算法解決了各種優(yōu)化問題。Noghrehabadi等（2011）采用冪級數(shù)和CS優(yōu)化算法計算微固定-固定梁的屈曲。Valian等（201 1）將改進的CS算法應用于前饋神經(jīng)網(wǎng)絡的訓練兩個基準分類問題。他們提出了一種調(diào)整CS參數(shù)的正確策略，Divya等人（2011）開發(fā)了一種基于布谷鳥的粒子方法來實現(xiàn)高效節(jié)能的無線傳感器網(wǎng)絡和多模態(tài)目標函數(shù)，類似于許多元啟發(fā)式算法，CS中的初始解也是隨機生成的。但本文采用Nawaz等人（1983）開發(fā)的一種稱為NEH算法的建設性啟發(fā)式算法來生成初始解之一，以提高解的質(zhì)量。此外，本文還對CS算法的參數(shù)進行了調(diào)整，提高了算法的效率。為此，本文提出了一種改進的混合布谷鳥搜索（IHCS）元啟發(fā)式算法，使排序流車間調(diào)度問題的最大完工時間最小化。

CS算法的靈感來自于一些杜鵑物種的專孵育寄生行為，以及自然界中一些鳥類和果蠅的飛行行為。以下三條理想化的規(guī)則被考慮用于描述該算法：一是每只杜鵑一次產(chǎn)一個蛋（解決方案），并將蛋放在隨機選擇的巢中；二是最好的巢和高質(zhì)量的蛋（解決方案）將進行到下一代；三是杜鵑下的蛋被寄主鳥發(fā)現(xiàn)的概率是Pa，然后鳥巢就建好了。對于最小化問題，質(zhì)量或適應度函數(shù)值可能是目標函數(shù)的倒數(shù)。鳥巢中的每個蛋代表一個解決方案（一個新的杜鵑蛋代表一個新的解決方案）。較好的解決方案正在取代較差的解決方案。CS算法的偽代碼在圖1給出。

圖1 布谷鳥搜索（Cuckoo Search，CS）算法偽代碼示意

2.2 新型改進的雜交杜鵑搜索 （IHCS） 元啟發(fā)式算法構架

一般情況下，初始解是隨機生成的。為了提高解的質(zhì)量，用構造啟發(fā)式算法生成一個解。上節(jié)給出了重要啟發(fā)式算法的構造。其中，采用Nawaz等人（1983）提出的一種建設性啟發(fā)式算法，即NEH啟發(fā)式算法生成一個初始解，其余解隨機生成。CS算法由Pa（接受概率）、α（步長）等參數(shù)組成，這些對于獲得更好的解非常重要。Valian等人（2011）討論了這些參數(shù)值的影響。在文獻中，CS算法的這些參數(shù)保持不變。在初始步驟中定義了參數(shù)Pa和α，并且不能更改這些值。由于參數(shù)的變化會降低算法的效率，因此本文中的參數(shù)都不是常數(shù)。

3 新型改進的雜交杜鵑搜索 （IHCS） 元啟發(fā)式算法工業(yè)優(yōu)化應用

3.1 問題描述

本文研究了流水車間調(diào)度問題。車間調(diào)度環(huán)境由m臺成批的機器和n個作業(yè)組成。每個作業(yè)必須按照特定的順序通過機器進行處理。此外，每個作業(yè)的處理將是連續(xù)的流程車間調(diào)度。該問題目標是最小化最大完工時間。最大完工時間可以定義為最后一項工作離開系統(tǒng)的完成時間。最大完工時間最小化對縮短生產(chǎn)時間和提高系統(tǒng)利用率具有重要意義。流程車間調(diào)度環(huán)境如圖2所示。

圖2 本文優(yōu)化流水車間調(diào)度問題模型簡圖

流水車間調(diào)度問題假設：所有作業(yè)和機器在零時都可用；這些操作不是可搶占的；每臺機器一次只能處理一項工作；每個作業(yè)一次只能在一臺機器上處理；處理時間是已知的，并且是固定的；作業(yè)的設置時間包含在處理時間中，不依賴于操作的順序；作業(yè)的操作順序在每臺機器上都是相同的，必須確定公共順序；機器在整個調(diào)度期間都可用。

3.2 計算與優(yōu)化結(jié)果

IHCS元啟發(fā)式算法是用c++編寫的，在PC上運行，CPU是英特爾酷睿2.4 GHz，2G。隨機選擇20個基準問題。測試問題涉及兩個機器號值（m = 15，20）和4個作業(yè)編號值（n = 20，30，40，50）。并與由Demirkol等人（1998）提出的一個蟻群優(yōu)化元啟發(fā)式算法（MHD-ACS）進行了比較。這里不考慮計算時間比較不同的研究人員使用不同的軟件硬件的配置可能會有變化。根據(jù)得到的結(jié)果和百分比改進后的IHCS算法提供比其他元啟發(fā)式算法更好的結(jié)果。IHCS獲得的改進百分比算法如圖3所示。

圖3 改良雜交杜鵑所獲得的改良百分率

本文首次提出了一種最大完工時間最小化的置換流車間調(diào)度算法。在大多數(shù)的元啟發(fā)式算法中，解是隨機產(chǎn)生的。但在這項工作中，一個建設性的啟發(fā)式稱為NEH啟發(fā)式納入初始隨機解決方案，以提高解決方案的質(zhì)量。同時對CS算法的參數(shù)進行了優(yōu)化，得到了較好的結(jié)果。文中提出的IHCS算法已經(jīng)在一組基準問題上進行了測試，并與已有的結(jié)果進行了比較，證明了算法的有效性。

4 結(jié)束語

綜上所述，這項工作可以擴展到許多方面。該算法只適用于單目標流水車間調(diào)度問題，可以推廣到多目標流水車間調(diào)度問題。該算法也可用于解決實際工業(yè)調(diào)度問題。未來我們可能會對混合流車間調(diào)度問題進行研究。與到期日相關的性能度量的調(diào)度問題和包含設置時間的問題可能是這項工作的一些可能范圍。