基于遺傳算法和貪婪算法的作業車間調度

王新， 賈志強， 尚宏美

（河北聯合大學，河北唐山063009）

0 引言

進人21世紀以來,制造業生產模式隨著科技的飛速發展和科技的進步在不斷發生變化。快速多變且無法預測的買方市場由當初的大批量訂購向著個性化、多樣化方向轉變，這就使得制造企業所面臨的諸多問題比如社會環境、生產條件、物質供給等方面都發生了顯著變化。因此，在這種情況下,一種以大批量生產的效益、提供滿足客戶個性化需求的產品和服務的定制生產方式應運而生［1］。由于生產車間有很多不確定因素，因此在生產調度問題上面臨著巨大的挑戰。過程規劃和作業車間調度承擔著巨大重任。過程規劃的主要作用是完成對機器的分配過程，實現資源的優化配置；車間調度的工作是確定每臺機器處理的工件和加工開始時間，為了完成所有進程并實現既定目標的優化。針對遺傳算法的收斂速度不快、局部搜索能力差，生成最優解不精確等特點，本文提出一種新的算法基于遺傳算法和貪婪算法的作業生產調度，它是在遺傳算法原算法的基礎上，引進貪婪變換進行個體解碼來提高遺傳算法在解的收斂速度和尋優能力。

1 基于混合遺傳算法的車間調度問題

作業車間調度可以描述為1臺機器加工N種工件（N是工件的集合），使用B種夾具以及C種刀具對工件進行加工（B是夾具的種類，C是刀具的種類），工件的總加工時間是T（T是所有工件加工用時間總和）。工件之間的操作序列,滿足一定的約束。工件開始加工及加工工件前的準備工作是機器加工的第一個操作，工件在加工完成后都有它的特定的交貨期，且不同工件的交貨期不一樣。當然在加工過程中使用的工具最少，步驟最精，工作時間最短，機器利用率最高這些都說明了生產調度性能最優［2］。本文主要研究一般性的Job Shop調度問題，在此問題滿足以下特點［3］：

1）N為工件集，工件的種類記為K（K是所有工件細分后的種類），每個種類都有不同數目的工件，每個工件的操作步驟或許不相同但是步驟的順序是固定的。

2）處理機器配有不同的處理工具，可以處理多種工件，工件加工時間來確定所需的約束，在處理計劃中確保所有處理任務的完成。

3）每個工件有規定的到期時間，由于需要在規定的期限內完成工作任務，所以要求相同類工件的到期時間相同，方便機器統一加工；反之則不同。

4）在給定的時間內，1臺機器只能夠加工1個工件的1道工序，直到加工完此工序方可加工其他工序。滿足以上四種條件的這種作業車間調度問題，都可以按工件交工延遲最短、機器加工最多工件、總加工時間達到最小為目的設計目標函數［4］。其目標函數為：

式（1）不僅考慮了操作工件所用總時間為最少，使工件的加工時間最集中、工具應用效率最高，還使得工件的加工量不會超出機器自身的承受能力，且保證了各工件完工期限的總延誤最小。其中：i是工件號；j是工件加工的總天數計數；si是工件i的交工時間；Xi是工件i加工日的集合；wi是機器加工工件所用刀具數量的集合；ci是刀具加工工件工序的集合；v是機器在加工零件過程中的最大承受能力；ti是1臺加工機器完成工件i操作加工的時間，它包括在加工工件不同工序時的機器等待時間，以及工件的安裝時間和工件加工時間。

2 溶合遺傳算法和貪婪算法

遺傳算法是將自然進化論的理論應用到理論算法的一種隨機搜索算法,它已成功地應用于作業車間調度，本文把貪婪變換G引入到遺傳算法中，不僅能夠發揮遺傳算法在各種調度方案之間選擇的優勢，還能夠彌補遺傳算法的缺點，使得在調度方案中跳出局部最優的陷阱。

2.1 編碼

編碼的對象是工件，把每個工件看做對應的生物染色體，而個體的染色體的表示采用矩陣，m×n的矩陣Y=［yij］。i=1，2，…，m，j=1，2，…，n（m 為工件加工的天數，n 為工件的加工順序）。一般來說，任何個體X，未必有X∈Ω（Ω是設計目標函數中的機器加工最多工件數）。于是引進貪婪變換（X）=Y=（y1，y2，…，yn）。若X∈Ω，則G（X）=X；若X?R，則按照 ρi=ci/w（ixi=1）從小到大的次序變換xi=1到xi=0，一直到正好滿足 為止，即得到G（X）=Y。顯然X∈Ω是可行解。于是得到混合貪婪算法［5］的遺傳算法，即在原來的遺傳算法的搜索的各個步驟加上貪婪變換G。

2.2 初始種群的生成

編碼成功以后，緊接著需要產生一個最優解［6］，作為實際操作中整體的一個個體。

第一步：使矩陣（工件在任何一天中使用的夾具數記為bij）的所有元素bij記為0；

第二步：矩陣bij的列方向按降序排列，依次分析每個工件。

第三步：在第一行的工件,對于任何一個元素,完成相應時期的隨機選擇處理,然后執行下一個加工工件。

第四步：接著的加工工件需要在完工期限內進行加工，然后執行下一個工件的處理。

第五步：當所需加工工件的調度處理完成時，檢查刀具、加工時間等條件是否滿足，如果滿足結束調度，否則返回第三步重新進行調度。

2.3 選擇操作

對最優化作業車間調度問題的選擇上主要依據是適應度計算。對于最小化問題，常見的適應度函數有F（X）=-f（x）；F（X）=max（cmax-f（x），0）；F（X）=1/（1+c+f（X）），（c+f（X）≥0）等。適應度決定了問題的最優化，也就是個體生存能力的最強選擇。一般在最優化問題上會選擇輪盤賭方式，按實際操作順序（即個體Aj的適應度J（Aj））占整個操作順序（即（種群）總適應度J（A）j）的比例劃分整個賭盤，然后接著轉動賭盤N次，在隨機轉動輪盤的過程中最好是能夠轉1圈以上，這樣可以防止轉盤不足1圈帶來的概率不準確等缺點，最終選出賭盤的指針所指示的計數（個體）。即每次轉動賭盤，選中Aj的概率J（A）j（A）j。在本文中按照適應度函數 （fX）=（fx1，…xn）=獨立地從當前種群中選取M個母體。

2.4 交叉操作

基因重組是來自父代的提供的交配種群中的信息然后重新組合產生新的個體的過程。而每個個體都代表著不同的內容，他們在實際生產調度中都會有相應的約束，而在矩陣中代表工件不同操作順序的某2個個體，讓所有的操作順序都并列而排出，選擇任何一個交叉點實行交叉即上下交換操作順序，代表個體的每個基因都以相同的概率Pc進行交換。

2.5 變異操作

變異就是按個體基因按小概率（變異概率Pm）擾動產生的變化，在變異過程中對整體矩陣實施貪婪變換G（Y（k+1））=（G（X1（k+1）），…，G（XN（k+1）））。實施貪婪變換的矩陣可以滿足操作步驟、加工順序等約束，但是可能不滿足整個加工的完成期限的約束。因此，還要進行隨機交換另外的個體產生新的子個體，直到滿足完工期限的約束。

表1 某個月數據加工表

3 調度實例及模擬結果

現有如下調度問題：機器加工6個工件，其中在某月的加工計劃數據表如表1所示。

在遺傳算法中取個體的數目為90，交換概率Pc=0.98，變異概率Pm=0.02.群體經過400代的進化,算法收斂。得到6個工件調度結果的Gantt圖（見圖1）。經模擬計算，得到該問題的最佳調度如表2所示，同時可得群體中指標函數最小值為780。

表2 溶合貪婪變換的混合遺傳算法下的最佳調度

圖1 甘特圖

有了數據庫中的數據,可以方便地根據這一數據生成基于工件的甘特圖，圖1中橫軸表示工件代號,縱軸表示天數。從甘特圖可以看出,工件在機器的加工上得到了合理的安排，既提高了機器的利用效率，又使得工件得以在最短時間加工完成。因此比較符合預期的結果。

4 結論

本文通過在遺傳算法中引入貪婪變換，使得改進后的遺傳算法在對作業車間調度問題求解上能夠跳出局部最優的陷井，進而得到最適合的問題求解方法。將實際生產中的作業任務轉化為染色體編碼串，引進貪婪變換G，在原來遺傳算法的選擇、交叉、變異等步驟中加入貪婪變換，使得在解的質量和求解速度方面都有非常大的改進，從而給出了一個適合于生產調度問題求解的新算法。

［1］ Bhote K R，Bhote A K.World Class Quality：Using Design of Experiments to Make It Happen［M］.New York：AMACOM，2000.

［2］ Cai Zixing，Gong Tao.Advance in research on immune algorithms［J］.Control and Decision，2004，19（8）：841-846.

［3］ 曹金全，初紅艷，費仁元.啟發式算法和遺傳算法在生產調度中的應用［J］.中國機械工程，2006（增刊 2）：211-214.

［4］ 陽明盛，羅長童.最優化原理、方法及求解軟件［M］.北京：科學出版社，2006.

［5］ 周明，孫樹棟.遺傳算法原理及應用［M］.北京：國防工業出版社，1999.

［6］ 張文修，梁怡.遺傳算法的數學基礎［M］.西安：西安交通大學出版社，2003.