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

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

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

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

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

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