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

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

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

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

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

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