基于啟發(fā)式規(guī)則和階乘碼的零等待流水車間調(diào)度算法研究.pdf

1、零等待流水車間廣泛的存在與現(xiàn)代制造系統(tǒng)中，如鋼鐵、醫(yī)藥等制造系統(tǒng)。在零等待流水車間中，假設(shè)有n個工件被 m臺機(jī)器加工。各個工件由z個工序組成，每個工序與機(jī)器是一一對應(yīng)的，即一種機(jī)器只能加工一種工序，一個工序只能在一臺機(jī)器上進(jìn)行加工。一個工件的連續(xù)兩道加工工序不能出現(xiàn)中斷。一臺機(jī)器不能同時加工多個工件。因此零等待流水車間調(diào)度算是一個典型的NP-hard問題。已有的調(diào)度策略和傳統(tǒng)的調(diào)度方法已無法滿足實(shí)際生產(chǎn)過程中的各種復(fù)雜需求。因此調(diào)度理論

2、方面的學(xué)術(shù)研究以及在實(shí)際的制造業(yè)生產(chǎn)之中，有效的調(diào)度方案研究仍然是本領(lǐng)域的一個熱點(diǎn)。
　　本文的主要研究內(nèi)容如下：
　　1.針對快速縮小搜索空間問題提出了基于傅里葉變換和搜索區(qū)域分割的啟發(fā)式算法。本文提出的基于快速傅里葉變換的方法使得搜索空間不再是以點(diǎn)為基本單元，而是以每個維度最小頻率對應(yīng)的周期的1/2或更小所圍成的區(qū)域為基本單元。這種分割方法能保證在每個維度上只存在4種可能性：
　　1）單調(diào)上升；
　　2）單調(diào)

3、下降；
　　3）有且只有1個極大值點(diǎn)；
　　4）有且只有1個極小值點(diǎn)。
　　在這種特殊的區(qū)域內(nèi)我們使用二分查找法來尋找每個維度上所能達(dá)到的最好值所在位置的集合。各個維度上的最好位置組合成的個體便是這個區(qū)域內(nèi)的最好值所在的位置。這使得算法不再與點(diǎn)的數(shù)量有關(guān)，而是和數(shù)據(jù)的最小頻率的數(shù)量有關(guān)。這將極大的減少了搜索空間，增加搜索效率。
　　2.針對零等待流水車間調(diào)度問題的甘特圖特性提出一種拼圖游戲啟發(fā)的算法。該算法將兩個

4、工件之間的總空余時間作為兩個工件是否契合的標(biāo)準(zhǔn)。算法開始時，先計算每個工件與其它工件之間的空余時間，對空余時間進(jìn)行由小到大排序，從而每個工件都有個匹配隊列。然后每個工件分別作為第一工件并且在它的匹配隊列中找出空余時間最小同時又不在已有序列中的工件作為下一個工件。此時這兩個工件即為局部最優(yōu)匹配，可將其視為一個工件。不斷迭代當(dāng)前步驟直至所有工件都出現(xiàn)在已有隊列中。此時每個工件作為第一個工件的調(diào)度序列組就產(chǎn)生了。最后選擇其中加工時間最小的序列

5、作為調(diào)度結(jié)果。
　　3.針對零等待流水車間調(diào)度問題中的Landscape提出了一種基于階乘碼和種群調(diào)整的粒子群優(yōu)化算法。這篇文章中提出的一種基與階乘的編/解碼方法的種群調(diào)整的粒子群算法用來解決零等待流水車間調(diào)度中尋找調(diào)度序列使得最小完成時間達(dá)到最小。此編碼將排列組合和自然數(shù)相互轉(zhuǎn)換。采用的是一一對應(yīng)的方式，即一個排列組合唯一對應(yīng)一個自然數(shù)，一個自然數(shù)唯一對應(yīng)一個排列組合。同時，通過這種編碼方法，我們可以得出各個調(diào)度模型的Lands