基于混合遺傳算法的訂單生產(chǎn)調(diào)度在機(jī)車(chē)車(chē)輛行業(yè)中的應(yīng)用

機(jī)車(chē)車(chē)輛企業(yè)是典型的訂單式生產(chǎn)企業(yè)，面對(duì)全球經(jīng)濟(jì)一體化，客戶(hù)需求個(gè)性化以及產(chǎn)品交貨高速化的經(jīng)濟(jì)時(shí)代，機(jī)車(chē)車(chē)輛行業(yè)面臨著快速響應(yīng)客戶(hù)需求、縮短產(chǎn)品交貨期、提高產(chǎn)品質(zhì)量和改進(jìn)產(chǎn)品服務(wù)的壓力。為了在激烈的市場(chǎng)競(jìng)爭(zhēng)中求得生存和發(fā)展，企業(yè)需要從生產(chǎn)調(diào)度環(huán)節(jié)進(jìn)行優(yōu)化。生產(chǎn)調(diào)度是制造系統(tǒng)的一個(gè)研究熱點(diǎn)，調(diào)度的任務(wù)是根據(jù)生產(chǎn)目標(biāo)和約束，為每一個(gè)對(duì)象確定具體的加工路徑、時(shí)間、機(jī)器和操作等，優(yōu)良的調(diào)度策略對(duì)于縮短產(chǎn)品的生產(chǎn)時(shí)間，降低成本有著極大的作用。

訂單生產(chǎn)調(diào)度問(wèn)題屬于一類(lèi)NP-hard組合問(wèn)題，因此尋找具有多項(xiàng)式復(fù)雜性的最優(yōu)算法幾乎是不可能的。傳統(tǒng)的啟發(fā)式算法、智能模擬退火算法、禁忌算法、神經(jīng)網(wǎng)絡(luò)法等算法其共性是對(duì)生產(chǎn)線(xiàn)優(yōu)化問(wèn)題尋求滿(mǎn)足實(shí)際需要的近似解或滿(mǎn)意解，但都是局部尋優(yōu)的方法。而各種基于統(tǒng)計(jì)優(yōu)化的方法諸如模擬退火法、遺傳算法等，提供了一種解決調(diào)度優(yōu)化問(wèn)題的新途徑，但也存在著一定程度的枚舉，一般來(lái)說(shuō)收斂到最優(yōu)解較慢，并且對(duì)于判斷解的最優(yōu)性也很困難。將遺傳算法與優(yōu)化算法結(jié)合起來(lái)對(duì)解決訂單生產(chǎn)調(diào)度問(wèn)題具有較高的性能。

1 混合遺傳算法

1.1 遺傳算法

遺傳算法由于其運(yùn)算的簡(jiǎn)易性和解決問(wèn)題的高效性而被廣泛應(yīng)用于眾多的領(lǐng)域。理論上已經(jīng)證明，遺傳算法能從概率的意義上以隨機(jī)的方式尋求到問(wèn)題的最優(yōu)解。但是另一方面，應(yīng)用實(shí)踐表明，在遺傳算法的應(yīng)用過(guò)程中也會(huì)出現(xiàn)一些不盡如人意的問(wèn)題，這些問(wèn)題主要表現(xiàn)為：容易產(chǎn)生早熟現(xiàn)象、局部尋優(yōu)能力較差等。并且一般來(lái)說(shuō)，對(duì)很多問(wèn)題，基本遺傳算法的求解效果往往不是解決這個(gè)問(wèn)題的最有效的方法，它比起專(zhuān)門(mén)針對(duì)該問(wèn)題的知識(shí)型啟發(fā)算法的求解效率要差，雖然這種知識(shí)型啟發(fā)算法并保證不了一定能夠找到問(wèn)題的全局最優(yōu)解。另外，遺傳算法也無(wú)法避免多次搜索同一個(gè)可行解的情況，這也是影響遺傳算法運(yùn)行效率的一個(gè)重要因素。

1.2 混合遺傳算法

梯度法、爬山法、模擬退火算法、列表尋優(yōu)法等一些優(yōu)化算法卻具有很強(qiáng)的局部搜索能力，而遺傳算法由于其運(yùn)算的簡(jiǎn)易性以及另一些含有問(wèn)題與相關(guān)知識(shí)的啟發(fā)式算法的運(yùn)行效率也比較高。因此可以預(yù)計(jì)，在遺傳算法的搜索過(guò)程中融合這些優(yōu)化方法的思想，構(gòu)成一種混合遺傳算法是提高遺傳算法運(yùn)行效率和求解質(zhì)量的一個(gè)有效手段。

混合遺傳算法是在標(biāo)準(zhǔn)遺傳算法中融合了局部搜索算法的思想，其特點(diǎn)主要體現(xiàn)在以下兩個(gè)方面：

（1）引入了局部搜索過(guò)程?；谌后w中各個(gè)個(gè)體所對(duì)應(yīng)的表現(xiàn)型，進(jìn)行局部搜索，從而找出各個(gè)個(gè)體在目前的環(huán)境下所對(duì)應(yīng)的局部最優(yōu)解，以便達(dá)到改善群體總體性能的目的。

（2）增加了編碼變換操作過(guò)程。對(duì)局部搜索過(guò)程所得到的局部最優(yōu)解，再通過(guò)編碼過(guò)程將它們變化為新的個(gè)體，以便能夠以一個(gè)性能較優(yōu)的新群體為基礎(chǔ)來(lái)進(jìn)行下一代的遺傳進(jìn)化操作。

2 機(jī)車(chē)車(chē)輛業(yè)面向訂單生產(chǎn)調(diào)度模型

訂單生產(chǎn)調(diào)度問(wèn)題中存在著多種優(yōu)化目標(biāo)或者綜合優(yōu)化目標(biāo)，調(diào)度問(wèn)題的優(yōu)化目標(biāo)通常從生產(chǎn)的成本和生產(chǎn)的時(shí)間兩個(gè)方面來(lái)考慮。從生產(chǎn)成本方面來(lái)考慮，其優(yōu)化目標(biāo)有：制品最少、庫(kù)存最少、設(shè)備利用率最高等；從生產(chǎn)時(shí)間方面來(lái)考慮，其優(yōu)化目標(biāo)有：最小完成時(shí)間、最大程度滿(mǎn)足交貨期、最小流動(dòng)時(shí)間和最小等待時(shí)間等。這兩個(gè)方向的優(yōu)化目標(biāo)之間彼此不是相互孤立的，其中的許多具體目標(biāo)之間聯(lián)系非常密切，有的相互促進(jìn)，有的相互沖突，也有的毫無(wú)聯(lián)系。本算法采用以總加工時(shí)間最小為目標(biāo)，具體表示為：

其中：Rk表示需要在設(shè)備k上加工的總工序數(shù)；Aijk表示第i個(gè)工件的第j道工序在設(shè)備k上完成加工所需要的時(shí)間。這個(gè)時(shí)間包括開(kāi)始加工此道工序之前的等待時(shí)間Wijk和從開(kāi)始加工到完成此道工序的所需時(shí)間Nijk；Cj表示訂單j的生產(chǎn)時(shí)間是訂單j中包括的所有部件全部完成的時(shí)間總和；Cmax為所有訂單在并行生產(chǎn)的情況下，最大完工時(shí)間，即各個(gè)訂單完成時(shí)間最晚的訂單的完成時(shí)間；目標(biāo)函數(shù)F（x）的目的是使得最長(zhǎng)需要時(shí)間盡可能地短。這樣，經(jīng)過(guò)算法的多次迭代后就可以生成調(diào)度的近似最優(yōu)解，得到滿(mǎn)意的調(diào)度結(jié)果。

3 混合遺傳算法的生產(chǎn)調(diào)度設(shè)計(jì)

根據(jù)上述思想，設(shè)計(jì)的混合遺傳算法的基本步驟如下：

（1）輸入數(shù)據(jù)，并初始化種群。
（2）計(jì)算種群的適配值的樣本方差FSD。
（3）判斷遺傳算法的停止準(zhǔn)則是否滿(mǎn)足要求。如果滿(mǎn)足停止算法，輸出結(jié)果，否則繼續(xù)以下步驟。
（4）基于當(dāng)前種群進(jìn)行選擇交叉操作。
（5）計(jì)算種群的樣本方差fsd，判斷fsd是否小于FSD/n，若小于則進(jìn)行第（6）步，如果大于則進(jìn)行變異操作。
（6）初始化禁忌搜索算法，當(dāng)前染色體即為初始解。
（7）判斷禁忌搜索算法迭代準(zhǔn)則是否滿(mǎn)足要求，如果滿(mǎn)足結(jié)束禁忌搜索，進(jìn)行第（2）步；否則繼續(xù)以下操作。
（8）產(chǎn)生候選解集。
（9）根據(jù)設(shè)定的渴望水平和禁忌表情況，選擇一個(gè)解，并更新禁忌表。
（10）轉(zhuǎn)到步驟（7）。
（11）轉(zhuǎn)到步驟（2）。

4 仿真實(shí)驗(yàn)

本文的仿真試驗(yàn)中，以某機(jī)車(chē)車(chē)輛行業(yè)的10個(gè)零件、10臺(tái)機(jī)器的調(diào)度問(wèn)題為例。下面給出加工時(shí)間陣、機(jī)器順序陣以及GATS算法計(jì)算10次所得的最優(yōu)工件排序陣及其對(duì)應(yīng)的最優(yōu)加工Gantt圖，如圖1所示，最優(yōu)解為87個(gè)單位時(shí)間。同時(shí)，該調(diào)度問(wèn)題的Gantt圖也明顯地反映了此問(wèn)題的求解復(fù)雜性。通過(guò)Gantt圖可以清晰地了解到在每臺(tái)機(jī)器上加工的工件及其各工序加工的起始時(shí)間和終止時(shí)間。如果調(diào)度的最佳解不是唯一的，則該調(diào)度算法同樣也可以將它們?nèi)克阉鞯?，該算例的最佳調(diào)度結(jié)果就也不是唯一的，圖1只是其中的一個(gè)最佳調(diào)度的Gantt圖。

以下是其各個(gè)矩陣的表示方法，其中機(jī)器順序陣為Jm；加工時(shí)間陣為T(mén)；工件排列陣為MJ。
（1）機(jī)器順序陣Jm，Jm（i，j）表示加工i工件的第j個(gè)操作的機(jī)器號(hào)。
（2）加工時(shí)間陣T，T（i，j）為j工件在機(jī)器上的加工時(shí)間。
（3）工件排列陣MJ，MJ（i，j）為i機(jī)器上第j次加工的工件號(hào)。

實(shí)驗(yàn)在仿真環(huán)境下分別使用GATS和GA計(jì)算了10次，并且記錄了每次得到目標(biāo)函數(shù)的最小值，如表1所示。由表1的結(jié)果表明，禁忌搜索算法在10次運(yùn)算中有2次達(dá)到最小值，而且最差的值與最優(yōu)值之間的偏差也只有3，結(jié)果波動(dòng)不大。

為了驗(yàn)證算法的有效性，在交叉算法和變異算法以及一些參數(shù)設(shè)置相同的情況下，采用傳統(tǒng)的遺傳算法重復(fù)運(yùn)算10次得到的最優(yōu)解為95，與最差值之間的偏差為8。同時(shí)可以比較出，禁忌搜索混合遺傳算法比傳統(tǒng)的遺傳算法有較好的穩(wěn)定性。

在充分分析機(jī)車(chē)車(chē)輛行業(yè)生產(chǎn)調(diào)度特點(diǎn)的基礎(chǔ)上，提出的遺傳算法和禁忌搜素算法混合的混合遺傳算法應(yīng)用在生產(chǎn)調(diào)度中。實(shí)驗(yàn)數(shù)據(jù)表明，改進(jìn)的混合遺傳算法既保存了遺傳算法和禁忌搜索算法的各自?xún)?yōu)點(diǎn)，又針對(duì)各自的不足做了改進(jìn)，使得混合遺傳算法既克服了禁忌搜索算法對(duì)初始解的依賴(lài)性，又克服了遺傳算法爬山能力差、易于早熟的缺點(diǎn)。實(shí)驗(yàn)證明，本文提出的混合遺傳算法可以改善原有算法，是可行的。