經典word整理文檔，僅參考，雙擊此處可刪除頁眉頁腳。本資料屬于網絡整理，如有侵權，請聯(lián)系刪除，謝謝！流水線調度問題求解XXX(:XXXXXXXX)摘要:有N個工件同時到達流水線上，給出一個加工順序排列使得最后一個工件從流水線最后一臺機器加工關鍵詞:flowshop多機調度遺傳算法元啟發(fā)式算法超啟發(fā)式算法1a)流水車間（FlowShop）調度問題是很多實際流水線生產調度問題的簡化模型，也是一個典型的NP-hard問題，因此其研究具有重要的理論意義和工程價值，也是目前研究最廣泛的一類典型調度問題。b)已知：有n個工件需要在m臺機器上流水加工。工件上的約束：所有工件均在0時刻釋放且在各機器上的加工順序相同，每個工件在每臺機器上只加工一次。機器上的約束：每個機器某一個時刻最多只能加工一個工件，而且執(zhí)行過程是非搶占的。目標：給出調度方案，使調度總完工時間最小。要求：算法復雜度在多項式時間內。c)對于工件加工順序的排列，可以看成是一段DNA序列，這段DNA序列可以交換片段的位置，可以改變兩個堿基對的位置，分別對應基因的交叉與突變。而給所有排列（基因）一個生存空間，并定期淘汰掉來的基因一定是更優(yōu)的。本文后續(xù)部分組織如下。第2節(jié)詳細陳述使用的方法，第3節(jié)報告實驗結果，第4節(jié)對討論本文的方法并總結全文。2遺傳算法對于流水線問題，遺傳算法相比于其他群智能算法能更加貼近問題，更容易實現(xiàn)，因此我采用了遺傳算法對該問題進行求解。具體設計思路如下：遺傳算法就是模擬了自然界中物競天擇，適者生存的法則，通過生物的不斷變異和自然選擇，遺傳留下優(yōu)秀的基因，淘汰不適應選擇條件的基因。對于工件加工順序的排列，可以看成是一段DNA序列，第i個堿基對上的編碼c表示第i個加工第c個工件。每個排列可看成一個細菌。在程序中，我使用一條鏈表來表示一個DNA鏈。這段DNA序列可以交換片段的位置，可以改變兩個堿基對的位置，分別對應基因的交叉與突變。繁殖相當于復制鏈表并對鏈表進行交叉互換與堿基對互換。使用鏈表表示為片段與堿基的交換提供了方便。給一個細菌一個生存空間，在初始階段，細菌會大量地繁殖而導致數(shù)量呈指數(shù)型地增長。程序通過隨機或貪心生成一條初始的排列，每過一段時間完成一輪繁殖。當鏈的數(shù)量小于生存容量時，DNA鏈的每一輪、每一個都會繁殖一條新的鏈，因此鏈的數(shù)量呈現(xiàn)指數(shù)型增長。當數(shù)量大于生存空間的容量時，則需要淘汰一些劣質的DNA鏈。淘汰規(guī)則有輪盤賭、錦標賽等等，輪盤賭即解更優(yōu)的留下的概率更大，弱者也有概率留下，而錦標賽是嚴格的適者生存，留下的都是時間較小的，這里我使用的是錦標賽規(guī)則。對總時間進行排序，殺死并銷毀排名在生存榜上排名較后2的DNA鏈。并讓留下來的DNA鏈進行下一輪繁殖與競爭。不斷迭代，經過很多代的演化后，遺傳下來的基因一定是更優(yōu)的。主要代碼如下：structgeneNode{intp;//堿基對,相當于脫氧核苷酸,形成鏈表//編碼，指向的工件號structgeneNode*next;};//指向下一個堿基對GeneNode*createNode();classGene{//新建一個堿基對//每一個基因即生存的個體private:GeneNode*head;intTotalTime;public://基因的第一個節(jié)點//花費的總時間Gene();//初始化的構造函數(shù)Gene(constGene&b);Gene(GeneNode*dna);Gene(Geneb,intflag);~Gene();//拷貝構造函數(shù)//為dna鏈構造對象//相當于復制一個b(鏈是新鏈,flag無意義)復制//析構函數(shù)死亡intcalculateTotalTime();//計算總時間GeneNode*copyDNA(GeneNode*p);//復制DNA鏈voiddeleteDNA(GeneNode*p);//刪除并銷毀DNA鏈booloperator<(constGene&a)const;GeneNode*recombination(GeneNode*dna);//基因重組voidmutation(GeneNode*dna);GeneNode*propagate();voidsetDNA(GeneNode*i);voidkill();//基因突變//繁殖后代。先復制一條鏈，并產生變異//設置基因頭節(jié)點//殺死該個體并釋放DNA鏈表的空間//將鏈狀DNA遞歸輸出//將基因輸出voidprintDNA(GeneNode*i);voidprintGene();};Geneq[MAX_CAPCITY*2];GeneNode*init();//生存空間,物競天擇,適者生存//初始化一個基因夏娃voidschedule();//進行調度，算法的主體涉及DNA鏈表的操作為數(shù)據(jù)結構基礎，這里不再詳解，只對主要的函數(shù)schedule進行講解。voidschedule(){intnum=1;q[0].setDNA(init());//初始化一個基因夏娃while(num<MAX_CAPCITY){inttmp=num;//數(shù)量小于容量，生存空間足夠,指數(shù)繁殖for(inti=0;i<tmp;i++,num++){//一輪繁殖，每一個DNA都產生一個新個體q[tmp+i].setDNA(q[i].propagate());3}}printProcess(0);sort(q,q+num);while(1){//排序，保留容量數(shù)的個體//繁殖一倍淘汰一半for(inti=0;i<MAX_CAPCITY;i++)//保留個體繼續(xù)繁殖q[MAX_CAPCITY+i].setDNA(q[i].propagate());sort(q,q+MAX_CAPCITY*2);currentTime=clock();if((currentTime-startTime)/CLOCKS_PER_SEC>BREAKTIME)break;//一直運行，直到超時退出printProcess(0);}printProcess(1);q[0].print();}元啟發(fā)式算法元啟發(fā)式算法是一個隨機化算法，是對啟發(fā)式規(guī)則的改進。啟發(fā)式算法是一種確定性算法，對于啟發(fā)式規(guī)則來說，需要找到一種策略，使得任意兩個堿基對之間滿足該規(guī)則約束，貪心算法就是一種典型的啟發(fā)式算法。對于元啟發(fā)來說，基因會發(fā)生變異，而且是否發(fā)生變異、基因片段交換的位置等都是通過隨機生成的，它是隨機算法與局部搜索結合的產物。由于隨機的存在，搜索可以跳出局部最優(yōu)的限制，在整個解空間中搜索。當?shù)拇螖?shù)趨于無窮大時，理論上元啟發(fā)式算法可以得到問題最優(yōu)解。GeneNode*Gene::propagate(){GeneNode*a=copyDNA(head);if(probability(PROBABILITY1))a=recombination(a);if(probability(PROBABILITY2))mutation(a);returna;}繁殖的時候有PROBABILITY1的概率基因重組，PROBABILITY2的概率發(fā)生基因突變，由于遺傳算法與自然界生物還是有一定差別，當概率太小時會導致大量無用的重復解，降低算法效率。因此變異的概率很大。交叉表示從一個隨機的節(jié)點開始前后互換。突變表示任意兩個結點的編碼內容交換。GeneNode*Gene::recombination(GeneNode*dna){inta=rand()%n;dna＝dna[a:n]+dna[0:a-1];returndna;}voidGene::mutation(GeneNode*dna){inta=rand()%n;intb=rand()%n;dna[a]<->dna[b];}4具體實現(xiàn)見代碼。超啟發(fā)式算法由于元啟發(fā)算法所搜尋的是問題的解空間，雖然尋優(yōu)能力強，但是當問題規(guī)模一大搜索的效率就會非常的低，因此要使用一個規(guī)則庫對搜尋進行約束，這便是超啟發(fā)算法。超啟發(fā)算法是對元啟發(fā)的一種改進，通過一種高層的策略操縱與組合底層的啟發(fā)式規(guī)則。底層啟發(fā)式規(guī)則包括各種貪心或其他算法，一般由問題專家給出。這些底層規(guī)則組成一個規(guī)則庫，而高層控制策略通過隨機組合底層啟發(fā)式規(guī)則對問題進行求解。因此，超啟發(fā)算法通過底層啟發(fā)式規(guī)則剪枝壓縮搜索空間，從而提高搜索效率。為了方便，程序采取了六種常用的貪心策略——時間小的先運行，每次變異時選擇一種貪心規(guī)則，當交換的片段滿足貪心規(guī)則時才進行變異，否則遞歸選取兩個新的節(jié)點直到基因發(fā)生變異。策略庫偽代碼StrategyN(){If(變異片段滿足貪心規(guī)則N)變異并return；ElsestrategyN();//遞歸直到發(fā)生變異}頂層控制策略choose(){probability1:Strategy1();probability2:Strategy2();probability3:Strategy3();probability4:Strategy4();probability5:Strategy5();probability6:Strategy6();}33.1實驗設置本程序實驗環(huán)境為DevC++，平均運行時間6秒左右。在DevC++中打開.cpp文件，將＃9-＃15的參數(shù)調好（實驗用例均使用的默認參數(shù)）測試用例文件分別為instance［10-14。編譯即可運行。3.2實驗結果元啟發(fā)算法5測試用例1運行結果測試用例2運行結果6測試用例3運行結果測試用例4運行結果7測試用例5運行結果超啟發(fā)算法測試用例1運行結果8測試用例2運行結果測試用例3運行結果9測試用例4運行結果測試用例5運行結果由于該算法是隨機性算法，因此還是使用表格來統(tǒng)計多次運行的結果測試用例啟發(fā)式遺傳算法運行結果超啟發(fā)式遺傳算法運行結果17038703870387038703870387038703870387038716671667038703870387038703870387038703870387038716671662107166716671887166716671667166716673127366731273127366736673127312731273668003800380038003800380038003800380038003772077387720772077207720772078477720772071667166718871667166716671667166731273667366731273127503736673127366736680038003800380038003800380038003800380037720772077387738782277207720773877277720345由表格可以看出，啟發(fā)式遺傳算法所得到的解離散度更小，因為對于問題規(guī)模不大的情況下，搜索全部解空間得到最優(yōu)解的概率更大，但是如果問題規(guī)模較大時漫無目的的搜索只會導致搜索的效率大大降低。超啟發(fā)式算法得到最優(yōu)解的概率小，但是搜索效率較高，是‘有選擇的’搜索，但是可能有時會把最優(yōu)解所在區(qū)域排除掉。兩種算法互有顧忌，應該依賴實際情況進行選擇。4本次實驗使用了元啟發(fā)算法與超啟發(fā)算法對問題進行求解，算法的框架為遺傳算法，因為遺傳算法能夠很好