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

關(guān)鍵詞：車間作業(yè)調(diào)度問題；遺傳算法；不可行調(diào)度

中圖分類號：TP301文獻(xiàn)標(biāo)識碼：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 引言

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

目前求解JSP問題的方法包括解析方法、窮舉方法、分支定界法、動態(tài)規(guī)劃法、拉格朗日松馳法和神經(jīng)網(wǎng)絡(luò)映射算法等。但由于問題本身難度很大，多數(shù)現(xiàn)有的優(yōu)化算法只適用于規(guī)模較小的問題，另外，工業(yè)界依靠經(jīng)驗或計算機模擬得到的可行調(diào)度也不能保證最好的性能。

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

2 JSP問題描述

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

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

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

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

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

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

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

3 解JSP遺傳算法流程

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

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

Step2：定義調(diào)度問題的適應(yīng)度函數(shù)(Fitness)，評價個體的適應(yīng)度值。

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

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

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

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

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

Step6：判斷算法是否達(dá)到終止條件，是則停止算法運行，最優(yōu)個體為問題的最終解；否則轉(zhuǎn)Step3。

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

4 算法分析

4.1 遺傳算法染色體編碼

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

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

4.2 Job Shop問題的目標(biāo)函數(shù)

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

4.3 遺傳算法染色體選擇算子設(shè)計

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

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

4.4 遺傳算法染色體交叉算子設(shè)計

鑒于JSP的特殊性，遺傳算法必須結(jié)合所采用的編碼技術(shù)設(shè)計相應(yīng)的交叉操作。置換編碼是一種主要的交叉操作，表示JSP的置換碼通常可分為兩類，即單一文字串(pure literal string，PLS)和一般文字串(general literal string，GLS)，其中PLS由不同的文字排列而成，而GLS則允許所排列的文字重復(fù)出現(xiàn)。基于工件的編碼和基于機器的編碼采用PLS，而基于操作的編碼、基于優(yōu)先表的編碼和基于先后規(guī)則的編碼則采用GLS，其中基于優(yōu)先表的編碼所采用的GLS由若干個PLS構(gòu)成。與PLS相關(guān)的交叉操作包括：部分映射交叉、次序交叉、基于位置的交叉、線性次序交叉、非ABEL群交叉和子調(diào)度互換交叉。非PLS下的交叉操作需要特殊設(shè)計，以保證染色體和對應(yīng)解的可行性與合法性。

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

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

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

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

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

5 不可行調(diào)度的處理

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

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

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

6 小結(jié)

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

參考文獻(xiàn)：

[1]王小平.遺傳算法—理論、應(yīng)用與軟件實現(xiàn)[M].西安:西安交通大學(xué)出版社,2002:130-136.

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

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

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

收稿日期：2008-04-03

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