【正文】 描述如下：F=min{max[max[etik ] ] } JobShop調(diào)度問題的染色體編碼在用遺傳算法解決 JobShop問題時(shí)，首先要考慮的就是遺傳編碼的設(shè)置，這也是基本遺傳算法的第一步，和它相對(duì)應(yīng)的是解碼。由于 JobShop是一類組合優(yōu)化問題，而且在進(jìn)行遺傳操作的時(shí)候要考慮工藝約束性、染色體的Lamarkian特性、解碼的復(fù)雜性、編碼的空間特性和存儲(chǔ)量的需求是設(shè)計(jì)遺傳算法編碼通常要考慮的問題。下一代種群中的個(gè)體還能繼承父代種群中適應(yīng)度值高的優(yōu)點(diǎn)，這時(shí)稱染色體編碼具有Lamarkian特性。（2）解碼的復(fù)雜性遺傳算法在通過編碼、遺傳操作后產(chǎn)生最終的優(yōu)秀個(gè)體，這些個(gè)體需要我們把它轉(zhuǎn)化成與生產(chǎn)車間相對(duì)應(yīng)的生產(chǎn)調(diào)度。最終的染色體編碼要通過簡(jiǎn)單映射關(guān)系才能生成車間的生產(chǎn)調(diào)度叫1類復(fù)雜性解碼；最終的染色體編碼要通過簡(jiǎn)單啟發(fā)式方法才能生成車間的調(diào)度叫2類復(fù)雜性；只能復(fù)雜啟發(fā)式方法才能生成車間的生產(chǎn)調(diào)度解碼叫3類復(fù)雜性解碼。（4）存儲(chǔ)量需求對(duì)于車間調(diào)度問題，存儲(chǔ)量需求是指編碼的長(zhǎng)度=工件數(shù)x機(jī)器數(shù)，這叫標(biāo)準(zhǔn)碼長(zhǎng)，但在編碼設(shè)計(jì)時(shí)有時(shí)為了操作和解碼方便，可以設(shè)計(jì)編碼長(zhǎng)度超過這個(gè)標(biāo)準(zhǔn)長(zhǎng)度或低于標(biāo)準(zhǔn)長(zhǎng)度的編碼。直接編碼將調(diào)度作為狀態(tài)，一般包括基于工件對(duì)關(guān)系、工件、操作、完成時(shí)間、隨機(jī)鍵編碼等。一般包括基于優(yōu)先權(quán)規(guī)則、機(jī)器、析取圖、先后表編碼：（1）基于操作的編碼該編碼方式是每個(gè)染色體由nm個(gè)代表操作的基因組成，是所有操作的一個(gè)排列，其中各工件號(hào)均出現(xiàn)m次，n代表加工的工件數(shù)，m代表加工的機(jī)器數(shù)。（2）基于工件的編碼此編碼方式以加工的工件為特征，染色體編碼由要加工的工件排列組成。（3）基于優(yōu)先規(guī)則的編碼此編碼方式的染色體編碼由長(zhǎng)度為標(biāo)準(zhǔn)編碼長(zhǎng)度按優(yōu)先分配規(guī)則組成的編碼，編碼的每個(gè)基因就是一種調(diào)度規(guī)則。在生物學(xué)中，基因是物種的性狀的決定因素，而染色體又是基因的載體，所以染色體是決定物種性狀的更高層次的物理實(shí)體，迄今為止，染色體是生物學(xué)中所發(fā)現(xiàn)的反映物種性狀的最大的物理實(shí)體。從JobShop調(diào)度問題的數(shù)學(xué)描述可知，它為每個(gè)待加工工件的加工工序在指定的機(jī)器上的加工順序，所以染色體能否表達(dá) JobShop調(diào)度問題的一個(gè)有效解，關(guān)鍵在于它是否能直接或間接地表達(dá)解空間。只有有序才會(huì)將JobShop調(diào)度問題的染色體編碼串唯一映象成一個(gè)解S。因?yàn)榻釹中的元素與所有的待加工工序一一對(duì)應(yīng)，只有包含所有的待加工工序，染色體編碼才會(huì)唯一地映象為一個(gè)解S。因?yàn)橹挥芯?jiǎn)才會(huì)利于遺傳進(jìn)化操作的效率。因?yàn)橹挥欣谶z傳操作算子的設(shè)計(jì)與操作，才能保證算法的有效性，進(jìn)而保證算法的成功性。即分析機(jī)器上當(dāng)前等待隊(duì)列的狀態(tài)并判斷是否用先后表來(lái)確定調(diào)度，也就是說，最先出現(xiàn)在先后表的操作將被選中。析取圖上的各孤的操作順序組成的染色體決定同臺(tái)機(jī)器上發(fā)生操作沖突時(shí)各操作的順序。JobShop生產(chǎn)調(diào)度就是要得到各機(jī)器上各操作的次序，即設(shè)置析取弧的方向以得到非循環(huán)圖來(lái)保證沒有操作間的先后沖突。在此過程中，若一臺(tái)機(jī)器上的兩個(gè)節(jié)點(diǎn)(操作)發(fā)生沖突，則染色體的相應(yīng)位決定操作的先后順序。（6）基于完成時(shí)間的編碼基于完成時(shí)間的編碼方式利用各操作完成時(shí)間的有序表來(lái)表示染色體。該編碼長(zhǎng)度為標(biāo)準(zhǔn)長(zhǎng)度，設(shè)計(jì)編碼時(shí)需要考慮編碼的空間特性，遺傳操作的設(shè)計(jì)需要設(shè)計(jì)成特殊的操作，不具有Lamarkian性且無(wú)需解碼(0類復(fù)雜)?；跈C(jī)器的編碼方式一般通過移動(dòng)瓶頸方法來(lái)構(gòu)造調(diào)度。它的性能依賴于對(duì)它的定義的排列順序。該編碼方式的特點(diǎn)可歸納為：半Lamarkian性、3類解碼復(fù)雜性、僅能表征部分解空間，不能保證全局最優(yōu)解的存在件、碼長(zhǎng)小于標(biāo)準(zhǔn)長(zhǎng)度。遺傳算法的適應(yīng)度f(wàn)是用來(lái)評(píng)判群體中的個(gè)體的優(yōu)劣程度的指標(biāo)。在這里我們根據(jù)本節(jié)所討論的 JobShop調(diào)度問題兩種不同的目標(biāo)函數(shù)給出兩種不同的適應(yīng)度評(píng)價(jià)函數(shù)。 JobShop的交叉與變異操作設(shè)計(jì)遺傳算法是一種通用的隨機(jī)優(yōu)化算法，而JSP則是一類特殊的組合優(yōu)化難題。一方面可對(duì)問題進(jìn)行處理使其適應(yīng)GA的優(yōu)化，另一方面可對(duì)GA進(jìn)行處理使其適JSP的求解，更有效的方法是對(duì)GA和JSP同時(shí)作處理使其相互適應(yīng)，如圖31所示。這里所謂的處理就是對(duì)問題和算法的編碼、操作、結(jié)構(gòu)等的處理。因此，目前求解JSP的大部分GA首先采用遺傳操作得到一個(gè)合適的置換排列，然后利用一定的方法將其轉(zhuǎn)化為一個(gè)調(diào)度。下面分別介紹求解JSP的GA的交叉與變異操作以及算法框架的若干設(shè)計(jì)。交叉操作的目的是利用父代個(gè)體組合出后代新個(gè)體。進(jìn)化計(jì)算中的遺傳算法流派認(rèn)為，交叉操作是主要的遺傳操作，GA的性能在很大程度少依賴于所使用的交叉操作?？紤]到置換編碼已成為目前GA解決調(diào)度問題的主流，征此僅介紹若干針對(duì)置換編碼的交叉操作。由于JobShop需要確定各操作的加工順序，并且要滿足各操作進(jìn)行加工的工藝先后約束，因此其表示方式和求解遠(yuǎn)比旅行商問題(TSP)復(fù)雜。此外，這些操作也可以按一定方式結(jié)合使用。標(biāo)準(zhǔn)遺傳算法的步驟可以歸結(jié)如下：步驟 1：令k=0，隨機(jī)產(chǎn)生N個(gè)初始個(gè)體構(gòu)成初始種群P(0)。步驟 3：判斷算法收斂準(zhǔn)則是否滿足。步驟 4：令m=0。步驟 6：若交叉概率Pc∈[0,1]，則對(duì)選中個(gè)體執(zhí)行交叉操作來(lái)產(chǎn)生兩個(gè)臨時(shí)個(gè)體；否則將所選中的父代個(gè)體作為臨時(shí)個(gè)體。上述算法中，復(fù)制操作通常采用比例復(fù)制，交叉操作通常交換父代個(gè)體的部分信息構(gòu)成后代個(gè)體，使得后代能夠繼承父代的有效模式，從而有助于產(chǎn)生優(yōu)良個(gè)體；變異操作通過隨機(jī)改變個(gè)體中某些基因而產(chǎn)生新個(gè)體，有助于增加種群的多樣性，避免早熟收斂。圖32 標(biāo)準(zhǔn)遺傳算法流程圖第4章 基于遺傳算法的車間調(diào)度算法設(shè)計(jì) 編碼的確定，本文提出了一種用工件號(hào)進(jìn)行染色體編碼的編碼規(guī)則，編碼規(guī)則為：規(guī)則1 根據(jù)染色體須能夠反映JobShop調(diào)度問題解的要求，首先按所有工件的所有加工工序進(jìn)行編碼，即由集合v={v=(i，j)|i=1,2，Oi}中元素形成的一個(gè)串，并且每個(gè)元素在串中必須且只能出現(xiàn)一次?？梢钥闯鲞@個(gè)串可以唯一映象為一個(gè)JobShop調(diào)度問題的解S，而且是一個(gè)精簡(jiǎn)解。這種編碼規(guī)則實(shí)質(zhì)上是用工件編號(hào)在染色體編碼串中的相對(duì)位置來(lái)表示不同的基因，而且每個(gè)工件編號(hào)在染色體中前后位置代表了該工件的加工工序的先后，即加工順序。而在進(jìn)行遺傳交叉運(yùn)算時(shí)，只須保證交叉段中相同工件的工件編號(hào)數(shù)相同，即可進(jìn)行交叉操作，且不會(huì)產(chǎn)生不可行解。例子41：如果有J={1，2}，JO1={1，2，3〕，JO2={1，2，3，4}，按工件號(hào)進(jìn)行編碼規(guī)則的第一步，可得一個(gè)串為:String=[(1，1)，(1，2)，(2，1)，(2，2)，(2，3)，(1，3)，(2，4)」按工件號(hào)進(jìn)行編碼規(guī)則的第二步，得染色體為：Chromosome=[1，1，2，2，2，l，2]。第一個(gè)位置的“1”表示工件1的第1道工序，第二個(gè)位置的“1”表示工件1的第2道工序，第6個(gè)位置的“1”表示工件1的第3道工序，以此類推。下面將討論如何把采用這種編碼方式的染色體轉(zhuǎn)化為唯一的JobShop調(diào)度問題的解s。規(guī)則3 依照染色體中基因排列的順序，依次取出每一個(gè)基因，然后根據(jù)每個(gè)基因所表示的工件及工件的加工工序，以及該加工工序應(yīng)該在哪臺(tái)機(jī)器上加工，再在該機(jī)器上依次排定該加工工序，直至完了。如表31所示為一個(gè)3個(gè)工件在3臺(tái)機(jī)器上加工的調(diào)度問題，它的一個(gè)染色體可為[2 1 1 1 2 3 2 3 3]。 交叉操作算子交叉算子根據(jù)交叉率(Pc)將種群中的兩個(gè)個(gè)體隨機(jī)地交換某些基因，能夠產(chǎn)生新的基因組合，期望將有益基因組合在一起。本文將提出一種新的交叉方法：（1）隨機(jī)劃分工件集{l，2，…，n}為兩個(gè)非空的子集J1和J2。（3）在p2中找到子集j2的各個(gè)工序，在順序不變的情況下插入到c1的空余位置，在p1中找到子集j1的各個(gè)工序，在順序不變的情況下插入到c2的空余位置。圖41顯示了兩個(gè)父代染色體應(yīng)用新的交叉算法產(chǎn)生兩個(gè)子代c1和c2的操作過程。這樣可以在一定程度上克服算法早熟收斂這一情況。 解碼的確定本文采用染色體解碼方式是半主動(dòng)解碼方式，這種方式將染色體上表示的工序按照表中已經(jīng)給定的工序從先到后加工?；诠ば蚓幋a的染色體可以相互轉(zhuǎn)換，但是一種機(jī)器碼的染色體可能對(duì)應(yīng)多種基于工序編碼的染色體。 算法參數(shù)設(shè)定及實(shí)現(xiàn)方法選擇算子采用最優(yōu)保存策略（1）初始化參數(shù) 族群60，循環(huán)100次，（2）初始化群 本文采用基于工序的編碼方式，如以表31為例，則初始化染色體（隨機(jī)生成）為：[2 1 3 2 1 2 3 3 1][1 2 3 3 1 1 2 3 2]等。具體交叉方法見43節(jié)所述。（7）替換：經(jīng)過交叉變異產(chǎn)生了新的種群，從中選擇出最差的染色體個(gè)體，然后用步驟三保留的最優(yōu)染色體把最差染色體替換。第5章 基于遺傳算法的車間調(diào)度實(shí)現(xiàn)及仿真 環(huán)境選擇在本系統(tǒng)的開發(fā)中，調(diào)度算法的實(shí)現(xiàn)要求編程語(yǔ)言有較高的運(yùn)算效率和較強(qiáng)的靈活性，并且能夠支持動(dòng)態(tài)數(shù)組。Microsoft Visual Basic 是 Microsoft 公司推出的功能強(qiáng)大的面向?qū)ο罂梢暬幊陶Z(yǔ)言，是目前使用最廣泛的編程語(yǔ)言之一。開發(fā)人員不需要編寫大量代碼去描述界面元素的外觀和行為，使得 Microsoft Visual Basic 具有語(yǔ)言結(jié)構(gòu)簡(jiǎn)單、界面生成直觀、開發(fā)周期較短和易于維護(hù)等優(yōu)點(diǎn)，另外它還能夠通過ADO和ODBC方便地訪問數(shù)據(jù)庫(kù)，因此是開發(fā)車間作業(yè)調(diào)度系統(tǒng)很不錯(cuò)的選擇。另外，可以使用Visual Basic通過ADO和ODBC方便地對(duì)access數(shù)據(jù)庫(kù)進(jìn)行訪問。本系統(tǒng)運(yùn)行的硬件環(huán)境為CPU主頻300MHZ以上，內(nèi)存為64M以上，操作系統(tǒng)為Windows92000、XP或win7。本文針對(duì)生產(chǎn)調(diào)度的具體需求設(shè)計(jì)了相應(yīng)的數(shù)據(jù)庫(kù)，用以存儲(chǔ)待加工工件信息、機(jī)床信息以及工藝信息。 算法實(shí)現(xiàn)模塊算法實(shí)現(xiàn)模塊是本系統(tǒng)的核心模塊之一，本文針對(duì)最大加工時(shí)間最短為目標(biāo)，采取遺傳算法對(duì)工件進(jìn)行排序，算法實(shí)現(xiàn)流程圖如下圖51所示：加工工件加工機(jī)床調(diào)度結(jié)果圖51 算法實(shí)現(xiàn)流程圖 系統(tǒng)界面與操作 用戶登錄界面設(shè)計(jì)用戶通過輸入用戶名和密碼，登錄到生產(chǎn)調(diào)度系統(tǒng)主界面圖 52 用戶登錄圖53 系統(tǒng)主窗口，點(diǎn)擊菜單可以進(jìn)入其他模塊進(jìn)行編輯和進(jìn)行其它操作。 甘特圖圖55甘特圖生成窗口點(diǎn)擊調(diào)度菜單下的甘特圖，進(jìn)入甘特圖生成窗口（圖55）。 調(diào)度結(jié)果圖56 調(diào)度結(jié)果窗口點(diǎn)擊調(diào)度菜單下的調(diào)度結(jié)果，進(jìn)入調(diào)度結(jié)果窗口（56）。另外，系統(tǒng)還設(shè)計(jì)了系統(tǒng)管理功能模塊，可以添加新用戶、修改用戶密碼。 結(jié)果分析根據(jù)軟件系統(tǒng)的結(jié)構(gòu)和程序運(yùn)行的結(jié)果來(lái)看，所設(shè)計(jì)的簡(jiǎn)易軟件主要有以下幾方面的問題：一 系統(tǒng)結(jié)構(gòu)簡(jiǎn)單，主要有車間調(diào)度基本數(shù)據(jù)和調(diào)度甘特圖生成兩部分。但在給定工件各工序的加工時(shí)間和各工序確定的加工機(jī)床等位假設(shè)的情況下，實(shí)現(xiàn)了工件的調(diào)度，即解決了基本的調(diào)度問題。二 車間調(diào)度選用了遺傳算法作為調(diào)度算法，各參數(shù)選擇為：種群大小40，迭代次數(shù)100。如對(duì)本文3表31的3X3的模型進(jìn)行調(diào)度時(shí)，所需時(shí)間為5秒，并且隨著工件或機(jī)床數(shù)的增加，運(yùn)行時(shí)間大大增加。由此，系統(tǒng)在運(yùn)行時(shí)間上有待減少，可從改進(jìn)算法結(jié)構(gòu)和算法實(shí)現(xiàn)語(yǔ)言這兩個(gè)方面考慮來(lái)減少運(yùn)行時(shí)間。第一章說明了課題的提出背景和研究意義，詳細(xì)闡述了車間作業(yè)調(diào)度問題，分析了調(diào)度模型及數(shù)學(xué)模型描述，總結(jié)了車間調(diào)度的求解方法，討論了車間調(diào)度的國(guó)內(nèi)外研究現(xiàn)狀；第二章詳細(xì)介紹了遺傳算法的發(fā)展歷史、算法思想以及遺傳算法的基本實(shí)現(xiàn)技術(shù)；第三章介紹JobShop調(diào)度問題的遺傳算法操作模型、調(diào)度問題的染色體編碼、染色體的交叉變異以及JobShop的遺傳算法流程；第四章主要內(nèi)容是基于遺傳算法的車間調(diào)度算法設(shè)計(jì)，包括確定基于工序的編碼方式、適應(yīng)度函數(shù)的確定、選定半主動(dòng)解碼方式、交叉變異操作算子的具體方法的確定以及求解JobShop問題的遺傳算法參數(shù)選擇和算法流程確定。 全文總結(jié)Jobshop調(diào)度問題是許多實(shí)際生產(chǎn)問題的簡(jiǎn)化模型，對(duì)其的研究具有重要的理論意義和工程價(jià)值，它也是目前研究最廣泛的一類典型調(diào)度問題JobShop調(diào)度問題是一個(gè)典型的NPhard問題，而開發(fā)求解JobShop調(diào)度問題的有效算法一直是調(diào)度和優(yōu)化領(lǐng)域的重要課題。本文成功地把遺傳算法運(yùn)用到單件小批的車間調(diào)度問題中。（2）建立了車間作業(yè)調(diào)度的數(shù)學(xué)模型（3）應(yīng)用遺傳算法，用VB為開發(fā)工具，access為數(shù)據(jù)庫(kù)后臺(tái)，開發(fā)實(shí)現(xiàn)了基于遺傳算法的作業(yè)車間調(diào)度系統(tǒng)，詳細(xì)介紹了各個(gè)模塊的功能與操作，驗(yàn)證了算法的實(shí)用性。本文的后續(xù)工作展望如下：（1）本文所研究的調(diào)度問題是把加工設(shè)備當(dāng)唯一的資源約束，但實(shí)際車間中存在多種資源約束（例如操作人員、刀具等），如何把單資源調(diào)度問題推廣到多資源調(diào)度，可以進(jìn)一步的深入考慮。（3）本文限于時(shí)間，所開發(fā)的系統(tǒng)只針對(duì)了加工總流程時(shí)間最短這一優(yōu)化目標(biāo)進(jìn)行了算法設(shè)計(jì)。（4）本文主要研究了靜態(tài)車間調(diào)度，即假設(shè)所用工件的信息和車間狀態(tài)都是明確的，一旦調(diào)度計(jì)劃確定，車間就按計(jì)劃生產(chǎn)?？梢婌o態(tài)調(diào)度不符合實(shí)際成產(chǎn)調(diào)度情況，因此可進(jìn)行更符合實(shí)際情況的動(dòng)態(tài)調(diào)度的研究。他淵博的知識(shí)、活躍的學(xué)術(shù)思想、嚴(yán)謹(jǐn)求實(shí)的治學(xué)態(tài)度、一絲不茍的工作作風(fēng)將使我受益終生，是我人生道路上的一筆寶貴財(cái)富。在論文研究過程中，王雯副教授和馬淼莉?qū)W姐給予了我很多的指導(dǎo)和幫助，同時(shí)在生活中也給予了我很多關(guān)懷，在此向她們表示深深地感謝。謹(jǐn)向我的父母、兄長(zhǎng)和親友致以崇高的敬意，感謝他們?cè)诰裆瞎膭?lì)和生活