【正文】 度問(wèn)題的理論研究成果主要在jobshop問(wèn)題為代表的基于最小完工時(shí)間的調(diào)度問(wèn)題上。它可分為精確求解方法和近視求解方法。而傳統(tǒng)的運(yùn)籌學(xué)方法，即便在較大規(guī)模的基于單目標(biāo)優(yōu)化的靜態(tài)調(diào)度問(wèn)題中也難以有效應(yīng)用。車間作業(yè)是指利用車間資源(如機(jī)床、刀具、夾具等)完成的某項(xiàng)任務(wù)。而在本文中，為了研究方便，我們將這項(xiàng)任務(wù)限定為加工一批工件。一個(gè)工件在一臺(tái)機(jī)器上的加工程序稱為一道“工序”，相應(yīng)的加工時(shí)間稱為該工序的“加工時(shí)間”。用“加工順序”表示各臺(tái)機(jī)器上各個(gè)工件加工的先后順序。它所要解決的問(wèn)題就是確定每臺(tái)機(jī)器上不同工件的加工順序，以及每個(gè)工件的所有工序的起始加工時(shí)間，以最優(yōu)化某個(gè)性能指標(biāo)。(機(jī)器)獨(dú)占性約束:任一臺(tái)機(jī)器每次只能加工一個(gè)工件，且一旦開(kāi)工就不能中斷，反映了加工隊(duì)列中工件間的時(shí)序關(guān)系。2. 不考慮工件加工的優(yōu)先權(quán)，即工件之間沒(méi)有優(yōu)先約束關(guān)系限制的。4. 所有機(jī)器處理的加工類型均不同。6. 緩沖區(qū)容量為無(wú)窮大。假設(shè)有n個(gè)工件，要在m臺(tái)機(jī)器上加工，每個(gè)工件有Pi道工序，每臺(tái)機(jī)器上總共要加工Lj道工序。P（i，j）表示i工件的第j道工序。不足，那么其空余的位置用0填滿。（i，j）表示i工件的第j道工序的機(jī)器號(hào)，表示i工件的所有工序按優(yōu)先順序加工的各機(jī)器號(hào)的排列。 （）T:加工時(shí)間陣，此為矩陣。同樣地，如果某工件的工序數(shù)不足，那么其空余的位置用0填滿。表示在i機(jī)器上排在第j位加工的工件號(hào)，表示i機(jī)器上依次加工的各工件的排列。事實(shí)上，工件排列陣就是調(diào)度的一種表示形式。即使得目標(biāo)函數(shù)取值最小(或最大)，且與相容，則稱為車間作業(yè)調(diào)度問(wèn)題在此目標(biāo)函數(shù)下的最優(yōu)解。調(diào)度問(wèn)題從生產(chǎn)成本方面來(lái)考慮，其優(yōu)化目標(biāo)有:庫(kù)存最少、在制品最少、設(shè)備利用率最高等。兩個(gè)方向的優(yōu)化目標(biāo)之間彼此不是相互孤立的，其中的許多具體目標(biāo)之間的聯(lián)系很密切，有的相互促進(jìn)，有的相互沖突，也有的毫無(wú)聯(lián)系。第一章簡(jiǎn)要介紹了車間調(diào)度問(wèn)題和求解調(diào)度問(wèn)題的基本方法；第二章介紹了遺傳算法的基本理論；第三章用遺傳算法來(lái)解決車間調(diào)度問(wèn)題,其中介紹了常用的幾種編碼方式,。2 遺傳算法相關(guān)理論與實(shí)現(xiàn)技術(shù)遺傳算法(Genetic Algorithm, GA)是一種基于自然群體遺傳演化機(jī)制的高效探索算法，它是美國(guó)學(xué)者Holland于1975年首先提出來(lái)的［7］。它將問(wèn)題域中的可能解看作是群體的一個(gè)個(gè)體或染色體，并將每一個(gè)體編碼成符號(hào)串形式，對(duì)群體反復(fù)進(jìn)行基于遺傳學(xué)的操作（遺傳，交叉和變異），根據(jù)預(yù)定的目標(biāo)適應(yīng)度函數(shù)對(duì)每個(gè)個(gè)體進(jìn)行評(píng)價(jià)，依據(jù)適者生存，優(yōu)勝劣汰的進(jìn)化規(guī)則，不斷得到更優(yōu)的群體，同時(shí)以全局并行搜索方式來(lái)搜索優(yōu)化群體中的最優(yōu)個(gè)體，求得滿足要求的最優(yōu)解。化石記錄表明我們所觀察的復(fù)雜結(jié)構(gòu)的生命是在相對(duì)短的時(shí)間進(jìn)化而來(lái)的，對(duì)這一點(diǎn)包括生物學(xué)家在內(nèi)的許多人都感到驚奇。進(jìn)化是發(fā)生在編碼染色體上，通過(guò)對(duì)染色體的譯碼部分生成生物體，但下面幾個(gè)關(guān)于進(jìn)化理論的一般特性已被廣大人們所接受。，哪些適應(yīng)性好地個(gè)體的染色體經(jīng)常比差的個(gè)體的染色體有更多的繁殖機(jī)會(huì)。大多數(shù)生物體是通過(guò)自然選擇和有性生殖這兩種基本過(guò)程進(jìn)行演化的。自然選擇決定了群體中那些個(gè)個(gè)體能存活并繁殖，有性生殖保證了后代基因中的混合與重組。 基本遺傳算法 遺傳算法的基本思路；，并從求解空間中任選N個(gè)點(diǎn)組成初始群體；。 遺傳算法的模式定理選擇操作是遺傳算法中體現(xiàn)“適者生存”的關(guān)鍵一環(huán)，它能控制高適應(yīng)度的模式成指數(shù)級(jí)增長(zhǎng)。其傳統(tǒng)實(shí)現(xiàn)建立在逐項(xiàng)比較的基礎(chǔ)上，算法復(fù)雜度為O（n＾2）。交換操作是有規(guī)則的信息交換，它能創(chuàng)建新的模式結(jié)構(gòu)，但又最低限度地破壞選擇操作過(guò)程所選擇的高適應(yīng)度的模式。但是如果其中一方個(gè)體不具有模式H，則有可能會(huì)引起另一個(gè)個(gè)體模式的改變。通過(guò)變異操作對(duì)個(gè)體串中單個(gè)位置進(jìn)行代碼替換，替換的概率為變異概率Pm，則該位置不發(fā)生變異的概率為1Pm。綜合上面所述，考慮到選擇操作、交換操作和變異操作對(duì)模式的影響，則第t代種群P(t)經(jīng)過(guò)遺傳操作后下一代種群P(t+1)具有模式H的個(gè)體總數(shù)為: ()該式表示了下述的模式定理。模式定理保證了較優(yōu)的模式(遺傳算法的較優(yōu)解)的數(shù)目呈指數(shù)增長(zhǎng)，為解釋遺傳算法機(jī)理提供了數(shù)學(xué)基礎(chǔ)。這些模式在遺傳中很重要，稱為基因塊。模式定理保證了較優(yōu)模式的樣本數(shù)呈指數(shù)增長(zhǎng)，從而使遺傳算法找到全局最優(yōu)解的可能性存在。上述結(jié)論并沒(méi)有得到證明，因而被稱為假設(shè)。 遺傳算法的收斂性分析遺傳算法要實(shí)現(xiàn)全局收斂，首先要求任意初始種群經(jīng)有限步都能到達(dá)全局最優(yōu)解，其次算法必須由保優(yōu)操作來(lái)防止最優(yōu)解的遺失。通常，種群太小則不能提供足夠的采樣點(diǎn)，以致算法性能很差。選擇操作使高適應(yīng)度個(gè)體能夠以更大的概率生存，從而提高了遺傳算法的全局收斂性。交叉操作用于個(gè)體對(duì)，產(chǎn)生新的個(gè)體，實(shí)質(zhì)上是在解空間中進(jìn)行有效搜索。概率太小時(shí)，交叉操作很少進(jìn)行，從而會(huì)使搜索停滯不前，造成算法的不收斂。但是，變異概率太小則很難產(chǎn)生新模式，變異概率太大則會(huì)使遺傳算法成為隨機(jī)搜索算法。由馬爾可夫鏈推導(dǎo)出來(lái)的一些結(jié)論:基本遺傳算法收斂于最優(yōu)解的概率為1,使用保留最優(yōu)個(gè)體策略的遺傳算法收斂于最優(yōu)解的概率為1。從總體上來(lái)說(shuō)，每代之間所處理的個(gè)體要遠(yuǎn)大于其表面的數(shù)目，這就是遺傳算法獨(dú)特的隱含并行性。隱含并行性為遺傳算法的高效性提供了理論依據(jù)。(population size)種群數(shù)目的多少直接影響到遺傳算法的優(yōu)化性能和效率，種群選擇太小時(shí)，不能提供足夠多的個(gè)體，致使算法性能較差，易產(chǎn)生早熟收斂，甚至不能得到可行解。(crossover rate)交換概率Pc用于控制交換操作的頻率。交換概率太小的時(shí)候又容易產(chǎn)生搜索停滯不前的現(xiàn)象。增加種群多樣性具有重要意義。如果變異概率太大的時(shí)，遺傳算法易變成隨機(jī)搜索，如果變異概率太小，則不能產(chǎn)生新個(gè)體，不利于種群的多樣性。(scaling window)該參數(shù)用于作出由目標(biāo)值到適應(yīng)度函數(shù)值的調(diào)整。另一種為保優(yōu)策略，首先進(jìn)行純選擇，把目前最優(yōu)個(gè)體直接加入下一代種群中，該策略是為了防止最優(yōu)解的丟失，但在實(shí)際應(yīng)用中往往采取這兩種選擇策略結(jié)合的方法，并做適當(dāng)?shù)淖冃汀＿@種機(jī)制意味著搜索過(guò)程可以跳出局部最優(yōu)點(diǎn)，能很好地將局部搜索和全局搜索協(xié)調(diào)起來(lái)，達(dá)到全局最優(yōu)點(diǎn)。，而不是對(duì)參數(shù)本身，因此遺傳算法具有靈活性高的特點(diǎn)。，容易形成通用算法程序。，在存在噪聲的情況下，對(duì)同一問(wèn)題利用遺傳算法求解所得的結(jié)果是相似的。，用遺傳算法求最優(yōu)解比較困難，因?yàn)槿旧w種群很可能過(guò)早地?cái)?，而?duì)以后變化了的數(shù)據(jù)不再產(chǎn)生變化。其中一種是所謂觸發(fā)式超級(jí)突變，就是當(dāng)染色體群體的質(zhì)量下降(彼此的區(qū)別減少)時(shí)增加突變概率。，但交叉和變異的重要性存在爭(zhēng)議。而另一種觀點(diǎn)則認(rèn)為交叉過(guò)程的作用只不過(guò)是在種群中推廣變異過(guò)程所造成的更新，對(duì)于初期的種群來(lái)說(shuō)，交叉幾乎等效于一個(gè)非常大的變異率，而這么大的變異很可能影響進(jìn)化過(guò)程。，優(yōu)化問(wèn)題要具體情況具體分析。 遺傳算法的進(jìn)展地球上自出現(xiàn)生命至今已有30多億年的歷史，從低級(jí)生物到高級(jí)生命再至擁有智慧的人類，這是一個(gè)漫長(zhǎng)的生物進(jìn)化過(guò)程。通過(guò)不斷的選擇，使有利于生存發(fā)展的變異遺傳下去，積累下來(lái)，使變異和遺傳向著適應(yīng)環(huán)境的方向發(fā)展。 遺傳算法是從代表問(wèn)題可能潛在的解集的一個(gè)種群（population）開(kāi)始的，而一個(gè)種群則由經(jīng)過(guò)基因（gene）編碼的一定數(shù)目的個(gè)體(individual)組成。染色體作為遺傳物質(zhì)的主要載體，即多個(gè)基因的集合，其內(nèi)部表現(xiàn)（即基因型）是某種基因組合，它決定了個(gè)體的形狀的外部表現(xiàn)，如黑頭發(fā)的特征是由染色體中控制這一特征的某種基因組合決定的。由于仿照基因編碼的工作很復(fù)雜，我們往往進(jìn)行簡(jiǎn)化，如二進(jìn)制編碼，初代種群產(chǎn)生之后，按照適者生存和優(yōu)勝劣汰的原理，逐代（generation）演化產(chǎn)生出越來(lái)越好的近似解，在每一代，根據(jù)問(wèn)題域中個(gè)體的適應(yīng)度（fitness）大小選擇（selection）個(gè)體，并借助于自然遺傳學(xué)的遺傳算子（genetic operators）進(jìn)行組合交叉（crossover）和變異（mutation），產(chǎn)生出代表新的解集的種群。隨著應(yīng)用領(lǐng)域的擴(kuò)展，遺傳算法的研究出現(xiàn)了幾個(gè)引人注目的新動(dòng)向［9］：一是基于遺傳算法的機(jī)器學(xué)習(xí)，這一新的研究課題把遺傳算法從歷來(lái)離散的搜索空間的優(yōu)化搜索算法擴(kuò)展到具有獨(dú)特的規(guī)則生成功能的嶄新的機(jī)器學(xué)習(xí)算法［10］。二是遺傳算法正日益和神經(jīng)網(wǎng)絡(luò)［12］、模糊推理以及混沌理論等其它智能計(jì)算方法相互滲透和結(jié)合，這對(duì)開(kāi)拓21世紀(jì)中新的智能計(jì)算技術(shù)將具有重要的意義。這一研究不僅對(duì)遺傳算法本身的發(fā)展，而且對(duì)于新一代智能計(jì)算機(jī)體系結(jié)構(gòu)的研究都是十分重要的。所謂人工生命即是用計(jì)算機(jī)模擬自然界豐富多彩的生命現(xiàn)象，其中生物的自適應(yīng)、進(jìn)化和免疫等現(xiàn)象是人工生命的重要研究對(duì)象，而遺傳算法在這方面將會(huì)發(fā)揮一定的作用，五是遺傳算法和進(jìn)化規(guī)劃（Evolution Programming,EP）以及進(jìn)化策略（Evolution Strategy,ES）等進(jìn)化計(jì)算理論日益結(jié)合。目前，這三者之間的比較研究和彼此結(jié)合的探討正形成熱點(diǎn)。 1996年，舉行了第1次遺傳程序設(shè)計(jì)國(guó)際會(huì)議，該領(lǐng)域己引起越來(lái)越多的相關(guān)學(xué)者們的興趣。此后，Holland指導(dǎo)學(xué)生完成了多篇有關(guān)遺傳算法研究的論文。1975年是遺傳算法研究歷史上十分重要的一年。Holland在該書(shū)中系統(tǒng)地闡述了遺傳算法的基本理論和方法，并提出了對(duì)遺傳算法的理論研究和發(fā)展極其重要的模式理論（schema theory）。同年， Jong完成了他的博士論文《一類遺傳自適應(yīng)系統(tǒng)的行為分析》（An Analysis of the Behavior of a Class of Genetic Adaptive System）。盡管De Jong和Hollstien 一樣主要側(cè)重于函數(shù)優(yōu)化的應(yīng)用研究，但他將選擇、交叉和變異操作進(jìn)一步完善和系統(tǒng)化，同時(shí)又提出了諸如代溝（generation gap）等新的遺傳操作技術(shù)。進(jìn)入八十年代，遺傳算法迎來(lái)了興盛發(fā)展時(shí)期，無(wú)論是理論研究還是應(yīng)用研究都成了十分熱門(mén)的課題。1989年，《搜索、優(yōu)化和機(jī)器學(xué)習(xí)中的遺傳算法》（Genetic Algorithms in Search , Optimization, and Machine Learning）。同年，美國(guó)斯坦福大學(xué)的Koza基于自然選擇原則創(chuàng)造性地提出了用層次化的計(jì)算機(jī)程序來(lái)表達(dá)問(wèn)題的遺傳程序設(shè)計(jì)( genetic programming, GP)方法，成功地解決了許多問(wèn)題。此外，以遺傳算法的理論基礎(chǔ)為中心的學(xué)術(shù)會(huì)議還有Foundations of Genetic Algorithms，該會(huì)也是從1990年開(kāi)始隔年召開(kāi)一次。1991年，《遺傳算法手冊(cè)》（Handbook of Genetic Algorithms），其中包括了遺傳算法在工程技術(shù)和社會(huì)生活中的大量應(yīng)用實(shí)例。1994年，他又出版了《遺傳程序設(shè)計(jì)，第二冊(cè):可重用程序的自動(dòng)發(fā)現(xiàn)》深化了遺傳程序設(shè)計(jì)的研究，使程序設(shè)計(jì)自動(dòng)化展現(xiàn)了新局面。1993年，MIT出版社創(chuàng)刊了新雜志《Evolutionary Computation》。《Advanced Computational Intelligence》雜志即將發(fā)刊。遺傳算法主要應(yīng)用在機(jī)器學(xué)習(xí)中。一般的學(xué)習(xí)系統(tǒng)要求具有隨時(shí)間推移逐步調(diào)整有關(guān)參數(shù)或者改變自身結(jié)構(gòu)以更加適應(yīng)環(huán)境，更好達(dá)到目標(biāo)的能力。除了機(jī)器學(xué)習(xí)之外遺傳算法所涉及的主要領(lǐng)域還有自動(dòng)控制、規(guī)劃設(shè)計(jì)、組合優(yōu)化、圖象處理、信號(hào)處理、人工生命、模式識(shí)別，神經(jīng)網(wǎng)絡(luò)、自適應(yīng)控制、生物科學(xué)、系統(tǒng)工程、社會(huì)科學(xué)等。今后幾年，拓廣更加多樣的應(yīng)用領(lǐng)域，將是GA發(fā)展的主流。與此同時(shí)，理論方面同樣有大量工作要做，例如：控制參數(shù)的選擇；交換和突變這兩類最重要的算子的確切作用；并行GA和分布式GA的研究。這對(duì)GA的實(shí)際應(yīng)用關(guān)系重大。與自然界相似，遺傳算法對(duì)待求解問(wèn)題本身一無(wú)所知，它所需要的僅是對(duì)算法所產(chǎn)生的每個(gè)染色體進(jìn)行評(píng)價(jià)，并基于適應(yīng)度值來(lái)評(píng)價(jià)染色體，使適用性好的染色體比適應(yīng)性差的染色體有更多的繁殖機(jī)會(huì)。 研究過(guò)程中的幾個(gè)關(guān)鍵問(wèn)題 設(shè)備死鎖現(xiàn)象初始解群是問(wèn)題的起點(diǎn)，解決設(shè)備死鎖問(wèn)題必須從初始解群開(kāi)始。 設(shè)備死鎖示意圖，分屬工件1和工件2的總共四個(gè)工序都處于循環(huán)等待其前面工序或前道工序結(jié)束加工的狀態(tài)之中，從而使設(shè)備1和設(shè)備2處于空轉(zhuǎn)狀態(tài)，即產(chǎn)生了所謂的死鎖現(xiàn)象。遺傳算法的工作基礎(chǔ)是選擇適當(dāng)?shù)姆椒ū硎緜€(gè)體和問(wèn)題的解(作為進(jìn)化的個(gè)體)。由于遺傳算法不能直接處理空間解的數(shù)據(jù)，在解決此車間調(diào)度問(wèn)題上把它們轉(zhuǎn)換成遺傳空間的基因按一定結(jié)構(gòu)組成的染色體或個(gè)體，也就是通過(guò)編碼將它們表示成遺傳空間的基因型串結(jié)構(gòu)數(shù)據(jù)。 加工時(shí)間和工藝約束項(xiàng)目工件操作序列123操作時(shí)間J1J2J3313352233機(jī)器J1J2J3M1M1M2M2M3M1M3M2M3，假設(shè)染色體為{2 1 2 3 1 1 3 2 3}，Oijk表示第i個(gè)工件的第j個(gè)工序在第k個(gè)機(jī)器上加工（以下同），則對(duì)機(jī)器加工順序的工藝約束，該染色體對(duì)應(yīng)的有序操作表為[O211 O111 O223 O312 O122 O133 O321 O232 O333]，即首先安排第二個(gè)工件的第一個(gè)操作步驟，然后安排第一個(gè)工件的第一個(gè)操作步驟，第二項(xiàng)任務(wù)的第二個(gè)操作步驟，…以次類推。t1296J3J3J3J1J1J1J2J2J2tt1M110734M3M2 Gantte圖（jobbased representation）將每個(gè)染色體用n個(gè)代表工件的基因組成，是所有工件的一個(gè)排列。其基本思想是只對(duì)任務(wù)進(jìn)行編碼，然后按照編碼在染色