運用遺傳算法優化車間作業調度問題

摘要：在車間作業調度數學表達模型的基礎上，研究了遺傳算法對該問題的解決策略和過程。在算法流程的基礎上，討論了求解JSP問題遺傳算法的具體設計，包括染色體編碼設計、目標函數、遺傳算子設計、選擇策略設計等，最后給出了對不可行調度的處理方案。

關鍵詞：車間作業調度問題；遺傳算法；不可行調度

中圖分類號：TP301文獻標識碼：A文章編號：1009-3044(2008)18-2pppp-0c

A Genetic Algorithm for Job Shop Scheduling Problem Optimization

HUANG Shao-rong

(Department of Information Management,Guangdong Justice Police Vocational College,Guangdong 510520,China)

Abstract:This paper gives out the mathematics model of JSP and the skeleton of,researches the strategies and processes of solving JSP by genetic algorithm,and discusses the design of GA in detail,then gives the mothed to solve the unfeasible scheduling solutions.

Key words:genetic algorithms;Job-shop Scheduling Problem;unfeasible scheduling solutions

1 引言

車間作業調度問題JSP（Job-shop Scheduling Problem）是一類求解困難的組合優化問題，實際是資源上的分配，求解目標是要找到一個將一組工件安排到設備上去，以使作業可為“最優”完成的方案。每個作業由一組任務組成，而每個任務必須由特定的設備處理，調度就是按先后順序條件將所有任務安排到設備上的一種方案。通常，約束條件很多，使JSP成為一個難解的組合問題，是調度問題中最典型也是最困難的問題之一。

目前求解JSP問題的方法包括解析方法、窮舉方法、分支定界法、動態規劃法、拉格朗日松馳法和神經網絡映射算法等。但由于問題本身難度很大，多數現有的優化算法只適用于規模較小的問題，另外，工業界依靠經驗或計算機模擬得到的可行調度也不能保證最好的性能。

遺傳算法作為一種有效的全局優化工具在JSP問題上的應用，是近年來才發展起來的研究方向，對復雜工業過程的建模、控制和優化領域的研究有重要的理論意義和工程價值。

2 JSP問題描述

設n個作業m臺機器的車間作業調度問題（n/m JSP）滿足下列約束條件：(1)一個作業由若干道工序組成；(2)每道工序必須在它前面的工序加工完畢后再加工；(3)每道工序必須在指定的機器上加工；(4)每道工序從加始到結束，不會被另外的工序中斷。問題定義為：

(1)n個工件的集合{1,2,…,n}，m臺機器的集合{1,2,…,m}；

(2)工序(i,j,k)表示作業i的第j道工序在機器k上執行，其中1≤i≤n，1≤k≤m，若工件i的工序數為pt，記p0=max(p1,p2,…,pn)，p=p1+p2+…+pn；

(3)矩陣W=(wij)n×p0為工序的耗時矩陣，wij表示執行工件i的第j道工序耗時，當j>pt時，wij=0；

(4)子集Work(a)={(i,j,k)|k=a} 1≤a≤m，表示共享機器a的工序集，記集合Work(a)的元素個數為La；

(5)一個調度S被定義為S=(S1,S2,…,Sm)T，其中Sa=(ga1,ga2,…,gaLa)是Work(a)中工序的一種排列(1≤a≤m)。即一個調度是由m臺機器上加工工序的排列組成；

(6)T(S)表示在調度策略S下的一個性能指標，求解目標就是尋找一個滿足約束的調度S，使T(S)最優。

3 解JSP遺傳算法流程

遺傳算法是一種基于自然選擇和自然遺傳機制的隨機搜索算法，其求解JSP的具體流程如下：

Step1：問題的染色體設計，種群規模為Popsize的初始可行解生成。

Step2：定義調度問題的適應度函數(Fitness)，評價個體的適應度值。

Step3：按某種選擇策略選擇下一代種群。

Step4：對種群中的個體進行了遺傳操作，生成新個體。

Step4a：按交叉概率Pm對種群中未匹配的個體對進行交叉操作，生成新個體。

Step4b：按變異概率Pc隨機選擇個體，進行變異操作生成新個體。

Step5：計算新個體的適應度值，父代個體和子代個體共同參與生存競爭。

Step6：判斷算法是否達到終止條件，是則停止算法運行，最優個體為問題的最終解；否則轉Step3。

以下將分別討論求解JSP問題遺傳算法的具體設計，主要包括染色體編碼設計、目標函數、遺傳算子設計、選擇策略設計等。

4 算法分析

4.1 遺傳算法染色體編碼

鑒于JSP的組合特性以及工藝約束性，編碼可歸納為直接編碼和間接編碼兩種：①直接編碼將各調度作為狀態，通過狀態演化達到尋優目的，主要包括基于操作的編碼、基于工件的編碼、基于工件對關系的編碼、基于完成時間的編碼、隨機鍵編碼等。②間接編碼將一組工件的分配處理規則作為狀態，算法優化的結果是一組最佳的分配規則序列，再由規則序列構造調度，主要包括基于優先權規則的編碼、基于先后表的編碼、基于析取圖的編碼和基于機器的編碼等。

在所有的編碼方式中，使用最多的是基于優先權規則的編碼。在這種編碼中，每個基因鏈由n條子鏈所構成，一條子鏈對應于一臺機器。子鏈的長度為n即該機器上工件的個數，鏈中的每個基因位表示一個工序，用這種編碼產生的染色體可以方便地實施各種遺傳操作。

4.2 Job Shop問題的目標函數

遺傳算法中使用適應度這個概念來度量群體中各個個體在優化計算中有可能達到、接近或有助于找到最優解的優良程度。一般來說，在運行的初期階段，適應度差距比較大，有可能導致在選擇過程中幾個個體占有很高比例，從而使遺傳算法產生早熟現象。而在運行的后期階段，群體的個體適應度可能非常接近，大部分個體的競爭力和最佳個體相差無幾，可能進入隨機選擇過程。由此，可采用線性尺度變換，從而能實現在運行的不同階段，對個體的適宜度進行適當的調整，擴大或縮小，避免早熟現象的發生。具體操作如下。

4.3 遺傳算法染色體選擇算子設計

采用比例選擇方法，即回放式隨機采樣，每個個體被選中的概率與其適應度大小成正比。為了避免誤差，可結合使用最優保存策略，即當前群體中最佳個體的適應度低于總的迄今為止的最好個體的適應度，用迄今為止的最好個體替換掉當前群體中的最差個體。

最優保存策略可視為選擇操作的一部分，其實施可保證迄今為止所得到的最優個體不會被交叉、變異等遺傳運算所破壞，是遺傳算法收斂性的一個重要保證條件。

4.4 遺傳算法染色體交叉算子設計

鑒于JSP的特殊性，遺傳算法必須結合所采用的編碼技術設計相應的交叉操作。置換編碼是一種主要的交叉操作，表示JSP的置換碼通?？煞譃閮深?，即單一文字串(pure literal string，PLS)和一般文字串(general literal string，GLS)，其中PLS由不同的文字排列而成，而GLS則允許所排列的文字重復出現?；诠ぜ木幋a和基于機器的編碼采用PLS，而基于操作的編碼、基于優先表的編碼和基于先后規則的編碼則采用GLS，其中基于優先表的編碼所采用的GLS由若干個PLS構成。與PLS相關的交叉操作包括：部分映射交叉、次序交叉、基于位置的交叉、線性次序交叉、非ABEL群交叉和子調度互換交叉。非PLS下的交叉操作需要特殊設計，以保證染色體和對應解的可行性與合法性。

4.5 遺傳算法染色體變異算子

變異操作的目的是通過隨機改變染色體的某些基因來引入新個體，增加種群多樣性，并在一定程度上進行局部搜索。常用針對置換編碼的變異操作包括：(1)互換，即隨機交換若干不同位置上的不同基因。(2)逆序，即將某兩個隨機位置間的基因串逆序。(3)插入，即將某一位置上的基因（或某一段位置上的基因串）插入到另一位置之前或之后。

4.6 交叉概率Pc和變異概率Pm

在經典遺傳算法中，交叉和變異操作采用固定概率，不能反映種群的進化過程。自適應交叉和變異概率根據種群的進化狀態來確定，使算法具有更好的收斂速度，其選取方法為：

其中，Pc為交叉概率，Pm為變異概率，Fmax為種群個體中的最大適應度，Favg為種群個體的平均適應度，fc是參加交換的兩個串中較大的適應度，fm是變異串的適應度，kc1、kc2、km1、km2為[0,1]之間的常數。Pc/Pm的自適應調整與算法的收斂程度成反比，能有效防止算法收斂于局部最小，同時，個體的適應度愈大，相應的Pc/Pm愈小，使好的進化結果得以保存。

5 不可行調度的處理

產生原因：(1)隨機生成的原始種群中，由于沒有檢測措施，含有違反工序約束的調度和死鎖調度。(2)在進化過程中，染色體的交叉和變異操作可能產生違反工序約束的調度和死鎖調度。

解決方法：(1)生成全部由可行調度組成的原始種群。(2)在選擇、交叉和變異過程中盡量避免產生違反工序約束的調度和死鎖調度，如果產生了則要采取有效的響應修補措施。

檢測和處理：(1)違反工序約束的調度的檢測：判斷各子染色體上的工序有沒有按工序約束排列。處理：引入修正操作，在執行交叉和變異操作時，每產生一個新的個體，對該個體實施修正操作。(2)死鎖調度的檢測：模擬其調度過程，若在某一時刻，所有尚未完工的機器的狀態都為空閑且這些機器上的首個未完工的狀態都為等狀態，則發生了死鎖。解鎖：交換這些染色體段上當前基因緊后的兩個基因，再檢測再交換，直到解鎖為止。

6 小結

簡要地分析了車間調度問題，利用遺傳算法對JSP問題進行求解，并對算法做了詳細分析，最后討論了對不可行解的處理。

參考文獻：

[1]王小平.遺傳算法—理論、應用與軟件實現[M].西安:西安交通大學出版社,2002:130-136.

[2]王凌.車間調度及其遺傳算法[M].北京:清華大學出版社,2003:68-76.

[3]謝勝利.求解JSP的遺傳算法中不可行調度的方案[J].計算機集成制造系統,2001,8(11).

[4]蔡良偉,張基宏.用自適應遺傳算法求解一類組合調度優化問題[J].深圳大學學報:理工版,2004,21(3).

收稿日期：2008-04-03

黃少榮（1976-），女，廣東饒平人，廣東司法警官職業學院信息管理系計算機講師，計算機應用碩士，主要研究方向：進化算法和人工智能。