運(yùn)用遺傳算法優(yōu)化車間作業(yè)調(diào)度問題

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

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

中圖分類號(hào)：TP301文獻(xiàn)標(biāo)識(shí)碼：A文章編號(hào)：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)化問題，實(shí)際是資源上的分配，求解目標(biāo)是要找到一個(gè)將一組工件安排到設(shè)備上去，以使作業(yè)可為“最優(yōu)”完成的方案。每個(gè)作業(yè)由一組任務(wù)組成，而每個(gè)任務(wù)必須由特定的設(shè)備處理，調(diào)度就是按先后順序條件將所有任務(wù)安排到設(shè)備上的一種方案。通常，約束條件很多，使JSP成為一個(gè)難解的組合問題，是調(diào)度問題中最典型也是最困難的問題之一。

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

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

2 JSP問題描述

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

(1)n個(gè)工件的集合{1,2,…,n}，m臺(tái)機(jī)器的集合{1,2,…,m}；

(2)工序(i,j,k)表示作業(yè)i的第j道工序在機(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為工序的耗時(shí)矩陣，wij表示執(zhí)行工件i的第j道工序耗時(shí)，當(dāng)j>pt時(shí)，wij=0；

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

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

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

3 解JSP遺傳算法流程

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

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

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

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

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

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

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

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

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

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

4 算法分析

4.1 遺傳算法染色體編碼

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

產(chǎn)生原因：(1)隨機(jī)生成的原始種群中，由于沒有檢測(cè)措施，含有違反工序約束的調(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)修補(bǔ)措施。

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

6 小結(jié)

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

參考文獻(xiàn)：

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

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

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

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

收稿日期：2008-04-03

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