車間生產(chǎn)調(diào)度算法研究

　　摘要：本文對(duì)柔性加工路徑的車間生產(chǎn)調(diào)度問(wèn)題提出了一種新的算法，即遺傳算法與啟發(fā)式算法相結(jié)合的混合算法。經(jīng)實(shí)驗(yàn)結(jié)果表明，這種算法可以大大提高企業(yè)制造資源的利用率和生產(chǎn)效率。
　　關(guān)鍵詞：柔性 車間生產(chǎn)調(diào)度 遺傳算法 啟發(fā)式算法
　　
　　車間生產(chǎn)調(diào)度可以描述為：用m臺(tái)機(jī)床來(lái)加工n個(gè)工件，每個(gè)工件都有多個(gè)工序且每個(gè)工序可以在多個(gè)并不相同的機(jī)床上加工。怎樣把有限的制造資源分配給這些要被加工的工件，使其某種指標(biāo)最優(yōu)化，這樣的一個(gè)決策過(guò)程就是車間的生產(chǎn)調(diào)度。實(shí)際生產(chǎn)中經(jīng)常會(huì)出現(xiàn)機(jī)床設(shè)備安排不當(dāng)而造成加工工期延遲、導(dǎo)致企業(yè)重大損失的現(xiàn)象。因此，如何將稀缺的制造資源有效地分配給被加工工件，就成了制造行業(yè)的重要研究課題。
　　一、生產(chǎn)調(diào)度算法研究現(xiàn)狀
　　自20世紀(jì)50年代開始到現(xiàn)在，關(guān)于調(diào)度問(wèn)題的解決方法有很多，如：運(yùn)籌學(xué)方法、遺傳算法、啟發(fā)式方法、粒子群優(yōu)化算法、DNA算法、Petri網(wǎng)、攝動(dòng)分析法和仿真調(diào)度法等等?，F(xiàn)將幾種經(jīng)典的調(diào)度算法的特點(diǎn)總結(jié)如下。
　　1.啟發(fā)式方法
　　此方法簡(jiǎn)單易行，在生產(chǎn)中得到了廣泛的應(yīng)用，但它也有缺點(diǎn)：一是不能考慮車間所有資源；二是由于分派規(guī)則的單一性導(dǎo)致多目標(biāo)調(diào)度不能實(shí)現(xiàn)，而這個(gè)問(wèn)題又是車間調(diào)度的基本問(wèn)題；三是分派規(guī)則的選擇決定調(diào)度性能，但是不存在一個(gè)分派規(guī)則能適應(yīng)多個(gè)車間環(huán)境。
　　2.遺傳算法
　　遺傳算法是模擬達(dá)爾文生物進(jìn)化論的自然選擇和遺傳學(xué)機(jī)理的生物進(jìn)化過(guò)程的計(jì)算模型，是一種通過(guò)模擬自然進(jìn)化過(guò)程搜索最優(yōu)解的方法。其主要特點(diǎn)有三：一是直接對(duì)結(jié)構(gòu)對(duì)象進(jìn)行操作，不存在求導(dǎo)和函數(shù)連續(xù)性的限定；二是具有內(nèi)在的隱并行性和更好的全局尋優(yōu)能力；三是采用概率化的尋優(yōu)方法，能自動(dòng)獲取和指導(dǎo)優(yōu)化的搜索空間，自適應(yīng)地調(diào)整搜索方向，不需要確定的規(guī)則。這種方法是解決搜索問(wèn)題的一種通用算法，已被人們廣泛應(yīng)用。
　　3.拉氏松弛法
　　拉氏松弛法一般能在較短時(shí)間內(nèi)對(duì)復(fù)雜的規(guī)劃問(wèn)題提供一個(gè)次優(yōu)解，但是，大多情況下，要得到滿意的調(diào)度結(jié)果，就要對(duì)所求解進(jìn)行修改[5]。
　　人們所研究的各種調(diào)度算法都有各自的特點(diǎn)，但由于實(shí)際生產(chǎn)車間調(diào)度的復(fù)雜性、實(shí)時(shí)性和動(dòng)態(tài)性等特點(diǎn)，車間調(diào)度問(wèn)題還有待尋求更為優(yōu)化的解法。
　　二、車間調(diào)度新算法
　　很多研究已經(jīng)表明，要解決一個(gè)柔性加工路徑的車間調(diào)度問(wèn)題，單單僅靠傳統(tǒng)的遺傳算法進(jìn)行優(yōu)化，是很難得到滿意結(jié)果的。因此，本文提出采用遺傳算法與啟發(fā)式算法相結(jié)合的混合算法來(lái)解決，具體步驟如下：
　　第一步：初始化，把可以使用機(jī)床k的時(shí)間Rk和工件i的第一道工序可被加工的時(shí)間Di1均設(shè)置為零；
　　第二步：使用優(yōu)先規(guī)則挑出還沒(méi)有被調(diào)度的工序，且它還是排在第一位的工序，并已經(jīng)進(jìn)入第三步運(yùn)算的工序；否則時(shí)間跨度=min(Oi)（i=1，2，…，n），其中，Oi表示工件i的完工時(shí)間;
　　第三步：利用Fijk=max[Rk，Dij]+dijk更新工件下一道工序的開始加工時(shí)間和機(jī)床的利用時(shí)間，這里的Fijk表示工件i在機(jī)床k上完成工序j的時(shí)刻；
　　第四步：設(shè)工件i的第j道工序的最早完工時(shí)間Eij=min(Fijk)，那么Oi=Eij；否則，工件的下一道工序的可加工時(shí)間Oi(j+h)=Oi(j+h)+(Eij-Oi(j+1))，其中h=1，2，…，(Ji-j)；
　　第五步：使機(jī)床k的可使用時(shí)刻Rk等于工件i的第j道工序的最早完工時(shí)間Eij；
　　第六步：判斷是否還有沒(méi)有被調(diào)用的工序，要是還有就從第二步重新開始，否則跨度時(shí)間就等于min(Oi)。
　　三、結(jié)束語(yǔ)
　　本文針對(duì)企業(yè)中常見(jiàn)的柔性加工路徑的車間調(diào)度問(wèn)題，提出了一種新的優(yōu)化算法，即遺傳算法與啟發(fā)式算法相結(jié)合的混合算法。實(shí)踐證明，該方法對(duì)于提高制造企業(yè)的資源利用率和生產(chǎn)效率是有效的。
　　參考文獻(xiàn)：
　　[1]