具有學(xué)習(xí)效應(yīng)的總完工時(shí)間流水線排序問(wèn)題與仿真論文

1、<p><b>　　本科畢業(yè)設(shè)計(jì)論文</b></p><p><b>　　題 目</b></p><p>　　具有學(xué)習(xí)效應(yīng)的總完工時(shí)間流水線排序問(wèn)題與仿真 </p><p>　　專業(yè)名稱 機(jī)械設(shè)計(jì)制造及其自動(dòng)化 </p><p>　　學(xué)生姓名

2、 </p><p>　　畢業(yè)時(shí)間 二〇一四年 七月 </p><p><b>　　畢業(yè) 任務(wù)書</b></p><p><b>　　一、題目</b></p><p>　　具有學(xué)習(xí)效應(yīng)的總完工時(shí)間流水作業(yè)排序與仿真</p><p>　　二

3、、指導(dǎo)思想和目的要求</p><p>　　（1）掌握運(yùn)用所學(xué)理論知識(shí)分析解決工程實(shí)際問(wèn)題的一般方法；</p><p>　?。?）培養(yǎng)分析問(wèn)題、解決問(wèn)題和獨(dú)立工作的能力；</p><p>　?。?）通過(guò)畢業(yè)實(shí)習(xí)、畢業(yè)設(shè)計(jì)及畢業(yè)答辯全過(guò)程的訓(xùn)練，加強(qiáng) 老師與學(xué)生之間、學(xué)生與學(xué)生之間知識(shí)的相互交流，互相滲透，培養(yǎng)學(xué)術(shù)研討的好學(xué)風(fēng)；</p><p>

4、　?。?）要求同學(xué)們以滿腔的熱情、科學(xué)的態(tài)度，嚴(yán)謹(jǐn)?shù)淖黠L(fēng)、高度的責(zé)任感從事畢業(yè)設(shè)計(jì)工作；不得敷衍了事、馬馬虎虎、得過(guò)且過(guò)；提倡周密思考、大膽創(chuàng)新，反對(duì)死搬硬套、墨守陳規(guī)；提倡共同研究，反對(duì)相互抄襲；</p><p>　　（5）要求遵守學(xué)校的各項(xiàng)規(guī)章制度，確保畢業(yè)設(shè)計(jì)順利地、高質(zhì)量地完成。</p><p><b>　　三、主要技術(shù)指標(biāo)</b></p>&

5、lt;p>　　過(guò)去處理排序問(wèn)題，大多采用兩種方式:一種是根據(jù)以往經(jīng)驗(yàn)，必要時(shí)作些修改，另一種是事物并不復(fù)雜，作些考慮即可奏效，排序問(wèn)題不成其為一門學(xué)問(wèn)。計(jì)算不周即可造成重大損失，依靠拍拍腦袋已不能解決問(wèn)題;而且產(chǎn)品更新很快，新產(chǎn)品的生產(chǎn)、銷售等沒有成法可資參考，此時(shí)各種新的組合優(yōu)化問(wèn)題便涌現(xiàn)出來(lái)，排序問(wèn)題便是其中之一。</p><p>　　翻譯文獻(xiàn)1500——2000字</p><p&g

6、t;<b>　　討論單機(jī)排序問(wèn)題</b></p><p>　　利用仿真軟件對(duì)單機(jī)排序問(wèn)題做出算法并給出最優(yōu)解</p><p>　　研究學(xué)習(xí)效應(yīng)對(duì)機(jī)器的影響</p><p><b>　　四、進(jìn)度和要求</b></p><p>　　（1）第1-3周收集資料，根據(jù)需要學(xué)習(xí)相關(guān)的硬軟件；</p>

7、<p>　?。?）第4周進(jìn)行系統(tǒng)概要設(shè)計(jì)，提出設(shè)計(jì)的總體思想；</p><p>　?。?）第5周，初步確定設(shè)計(jì)方案；</p><p>　?。?）第6-12周，完成單機(jī)，針對(duì)設(shè)計(jì)中存在的缺點(diǎn)和不足，不斷完善設(shè)計(jì)方案；</p><p>　?。?）第13-14周，撰寫并修改論文；</p><p>　?。?）第15-16周，完成論文，準(zhǔn)

8、備答辯資料。</p><p>　　五、主要參考書及參考資料</p><p><b>　　自行確定</b></p><p><b>　　本頁(yè)不夠可以續(xù)頁(yè)</b></p><p>　　學(xué)生 張紅偉 指導(dǎo)教師 王劍 系主任 </p><p>&

9、lt;b>　　摘 要</b></p><p>　　排序問(wèn)題的一大特點(diǎn)是:模型繁多，適用于某一模型的算法，只要將模型的條件稍加變化，該算法即不適用. 包括如何對(duì)各個(gè)部件進(jìn)行分隔、布線和布局的問(wèn)題”.排序論是國(guó)際上發(fā)展最迅速、研究最活躍、成果最豐碩、前景最誘人的學(xué)科領(lǐng)域之一特別引人注目的是:隨著現(xiàn)代工業(yè)的發(fā)展，經(jīng)典的排序模式已被突破，新的模式層出不窮，吸引了越來(lái)越多的理論工作者和實(shí)際工作者、可控排

10、序、多目標(biāo)排序、成組分批排序、同時(shí)加工排序、準(zhǔn)時(shí)排序和窗時(shí)排序、資源受限排序、不同時(shí)開工排序、隨機(jī)排序、模糊排序、應(yīng)用排序等，就是其中發(fā)展最為迅速的一些新方向. 在我國(guó)，對(duì)排序問(wèn)題的研究較晚，雖然早在20世紀(jì)50年代末，就有人注意到這一問(wèn)題一問(wèn)題的研究，并開始作一些宣傳普及的工作;但由于眾所周知的原因，對(duì)這，直至70年代中才開始，到80年代，對(duì)算法感興趣的人越來(lái)越多。現(xiàn)研究工件具有學(xué)習(xí)效應(yīng)的單臺(tái)機(jī)器流水作業(yè)排序問(wèn)題與仿真。工件的學(xué)習(xí)效應(yīng)

11、指工件的加工時(shí)間為所排位置的指數(shù)函數(shù)。目標(biāo)函數(shù)為極小化總完工時(shí)間。給出該問(wèn)題的數(shù)學(xué)規(guī)劃模型。同時(shí)對(duì)大規(guī)模問(wèn)題給出3個(gè)啟發(fā)式算法,并給出計(jì)算結(jié)果。 </p><p><b>　　，</b></p><p>　　關(guān)鍵詞：排序，流水作業(yè)，學(xué)習(xí)效應(yīng)，總完工時(shí)間 </p><p><b>　　ABSTRACT</b></p&g

12、t;<p>　　Scheduling problem is a major feature: the model range, the algorithm applies to a model, just a little change in the conditions of the model, the algorithm does not apply. Including the issue of how to se

13、parate the various components, wiring and layout. " Sort theory is one of the world's most rapid development, research the most active, the most fruitful achievements, the most attractive prospects disciplines a

14、re particularly striking: With the development of modern industry, the classic sort </p><p>　　Keywords: scheduling，flow shop，learning effect，the total completion time</p><p><b>　　目 錄<

15、/b></p><p>　　錯(cuò)誤!未找到引用源。</p><p><b>　　緒 論</b></p><p>　　1.1 流水作業(yè)排序問(wèn)題</p><p><b>　　1.1.l引例</b></p><p>　　排序(scheduling)問(wèn)題產(chǎn)生的背景主要是機(jī)器制造，

16、后來(lái)被廣泛應(yīng)用于計(jì)算機(jī)系統(tǒng)、運(yùn)輸調(diào)度、生產(chǎn)管理等領(lǐng)域.從普通的生產(chǎn)部門的計(jì)劃安排、人員調(diào)度，學(xué)校課程表的制訂，到宇宙飛船的復(fù)雜龐大的飛行計(jì)劃，都要用到排序的理論和算法。在給出排序問(wèn)題的一般定義之前，我們先看幾個(gè)排序在實(shí)際領(lǐng)域中應(yīng)用的例子。</p><p><b>　　例1.1機(jī)械加工</b></p><p>　　一個(gè)機(jī)械加工車間要加工一批機(jī)器零件，每一個(gè)零件都具有相同

17、的工序，</p><p>　　即按相同的順序在幾個(gè)不同的機(jī)床上加工，但每個(gè)零件在每個(gè)機(jī)床上的加工時(shí)間可能不同.如何安排加工順序才能以最短的時(shí)間加工完所有的零件，這是一個(gè)流水線排序問(wèn)題。</p><p><b>　　例1.2進(jìn)程調(diào)度</b></p><p>　　在計(jì)算機(jī)多道程序操作系統(tǒng)中，并發(fā)執(zhí)行多個(gè)進(jìn)程，在宏觀上同時(shí)執(zhí)行多個(gè)進(jìn)程，在微觀上在任何

18、時(shí)刻CPU只能執(zhí)行一個(gè)進(jìn)程。進(jìn)程的到達(dá)時(shí)間是不同的，怎樣調(diào)度這些進(jìn)程才能使CPU的利用率最高或進(jìn)程的平均周轉(zhuǎn)時(shí)間最短?這也是一個(gè)排序問(wèn)題。另外，每個(gè)進(jìn)程的到達(dá)時(shí)間和執(zhí)行時(shí)間事先是不知道的，但隨機(jī)到達(dá)時(shí)間和執(zhí)行時(shí)間的分布、它們的數(shù)學(xué)期望、方差等是已知的，這時(shí)的目標(biāo)是極小化平均周轉(zhuǎn)時(shí)間的數(shù)學(xué)期望。排序問(wèn)題中出現(xiàn)了隨機(jī)變量稱作隨機(jī)排序問(wèn)題。</p><p><b>　　例1.3機(jī)場(chǎng)調(diào)度</b>&l

19、t;/p><p>　　在一個(gè)飛機(jī)場(chǎng)，有幾十個(gè)登機(jī)門，每天有幾百架飛機(jī)降落和起飛。登機(jī)門的種類和大小是不同的，而班機(jī)的機(jī)型和大小也是不同的，一些登機(jī)門安放在能容納大型飛機(jī)的地方，小登機(jī)門只能容納小型飛機(jī)。飛機(jī)按時(shí)刻表降落和起飛，由于天氣和機(jī)場(chǎng)的其他原因，時(shí)刻表也有很大的隨機(jī)性。當(dāng)飛機(jī)占有登機(jī)門時(shí)，到達(dá)的旅客下飛機(jī)，出發(fā)的旅客上飛機(jī)，飛機(jī)要接受諸如加油、維護(hù)和裝卸行李等服務(wù)。如果飛機(jī)在下一個(gè)機(jī)場(chǎng)不能按時(shí)降落，此時(shí)為了節(jié)省

20、燃料，飛機(jī)不能起飛，登機(jī)時(shí)間推遲，飛機(jī)需要占有一個(gè)登機(jī)門，而其他的飛機(jī)不能使用。</p><p>　　機(jī)場(chǎng)的調(diào)度人員需要制訂一個(gè)可行的方案，把登機(jī)門分配給降落的飛機(jī)，使機(jī)場(chǎng)的利用率最高或晚點(diǎn)起飛的飛機(jī)最少，這也是一個(gè)排序間題，在這里飛機(jī)被看成是被處理的任務(wù)，登機(jī)門當(dāng)作處理機(jī)，機(jī)場(chǎng)的規(guī)定是約束條件。</p><p>　　1.2 排序問(wèn)題的定義</p><p>　　排序

21、(scheduling)問(wèn)題是一類重要的組合最優(yōu)化問(wèn)題，它是利用一些處理機(jī)(processor)、機(jī)器(machine)或資源( resource )，最優(yōu)地完成一批給定的任務(wù)(task)或作業(yè)(yob)。在執(zhí)行這些任務(wù)或作業(yè)時(shí)需要滿足某些限制條件，如任務(wù)的到達(dá)時(shí)間、完工的限定時(shí)間、任務(wù)的加工順序、資源對(duì)加工時(shí)間的影響等.最優(yōu)的完成指的是使目標(biāo)函數(shù)達(dá)到最小，而目標(biāo)函數(shù)通常是對(duì)加工時(shí)間的長(zhǎng)短、處理機(jī)的利用率的描述。</p>

22、<p>　　在排序問(wèn)題中，處理機(jī)的數(shù)量和種類，任務(wù)或作業(yè)的順序、到達(dá)時(shí)間、完工限制，資源的種類和性能等情況是錯(cuò)綜復(fù)雜的，很難用精確的數(shù)學(xué)描述給出一般的排序定義。在本書中，我們用如下方式來(lái)描述排序問(wèn)題: </p><p>　　給定n個(gè)任務(wù)的任務(wù)集</p><p>　　T ={ ,,…,}</p><p>　　m個(gè)處理機(jī)的處理機(jī)集</p><

23、;p>　　P ={,,…, }</p><p><b>　　和s種資源的資源集</b></p><p><b>　　R ={,,…,}</b></p><p>　　排序問(wèn)題指的是在一定條件下，為了完成各項(xiàng)任務(wù)，把沙中的處理機(jī)和}(如果有)中的資源分配給了中的任務(wù)，使目標(biāo)函數(shù)達(dá)到最優(yōu)。排序問(wèn)題基本上是由處理機(jī)的數(shù)量、種

24、類與環(huán)境，以及任務(wù)或作業(yè)的性質(zhì)和目標(biāo)函數(shù)所組成。</p><p>　　處理機(jī)只有一個(gè)處理機(jī)的排序問(wèn)題稱為單(處理)機(jī)(single processor, single machine)排序問(wèn)題，否則稱為多(處理)機(jī)排序問(wèn)題。在多處理機(jī)排序問(wèn)題中，如果所有的處理機(jī)都具有相同的功能，稱它們?yōu)橥悪C(jī)或平行機(jī)(parallel processors)。同類機(jī)按處理的速度又分為三種類型:如果所有的處理機(jī)都具有相同的速度，稱

25、之為同速機(jī)(identical processors );如果處理機(jī)的速度不同，但每個(gè)處理機(jī)的速度都是常數(shù)，不依賴被加工的任務(wù)，稱它們?yōu)楹闼贆C(jī)(uniform processors);如果處理機(jī)的速度依賴被加工的任務(wù)，它們被稱為變速機(jī)(unrelated processors)。</p><p>　　多處理機(jī)的另一種情況是多類型機(jī)(dedicated processors)。多類型機(jī)指的是m個(gè)處理機(jī)具有不同的功能

26、。在多處理機(jī)環(huán)境中，被加工的任務(wù)需要在不同的處理機(jī)上加工.在這種情況下，把任務(wù)(task )稱為作業(yè)(job)。設(shè)有作業(yè)集</p><p><b>　　J={,,…,}</b></p><p>　　每個(gè)作業(yè),有，道工序(operation) ，，…，}.工序指的是作業(yè)在某處理機(jī)上被加工的這部分任務(wù)。</p><p>　　如果每個(gè)作業(yè)需要在每個(gè)處

27、理機(jī)上加工，即=m ,j二1，2，…，n.而且每個(gè)作業(yè)的工序也相同，即在處理機(jī)上加工的順序相同，把這種多類機(jī)的環(huán)境稱為同順序作業(yè)或流水作業(yè)(flow shop)。</p><p>　　如果每個(gè)作業(yè)需要在每個(gè)處理機(jī)上加工，每個(gè)作業(yè)有自己的加工順序，稱之為異順序作業(yè)(job shop)。</p><p>　　如果每個(gè)作業(yè)需要在每個(gè)處理機(jī)上加工，每個(gè)作業(yè)可按任意順序加工，把它稱為自由順序作業(yè)或開

28、放作業(yè)(open shop ) 。</p><p>　　在多處理機(jī)中，還有一種更復(fù)雜的情況，這就是柔性流水作業(yè)(flexible flow shop)，它是流水作業(yè)和平行機(jī)的推廣。在柔性流水作業(yè)中，有，類處理機(jī)，第J類有個(gè)平行機(jī)，每個(gè)作業(yè)有s道工序，每道工序需要在每類平行機(jī)中的一個(gè)處理機(jī)上加工，且每個(gè)作業(yè)的加工順序相同。</p><p>　　為方便起見，以后我們把同順序作業(yè)、異順序作業(yè)、開

29、放作業(yè)、柔性流水作</p><p><b>　　業(yè)通稱為車間作業(yè)。</b></p><p>　　處理機(jī)的各種類型和環(huán)境總結(jié)如下:</p><p>　　·· 單處理機(jī)</p><p><b>　　同速機(jī)</b></p><p

30、>　　同類機(jī)（平行機(jī)） 恒速機(jī)</p><p>　　· 自由順序作業(yè)（開放作業(yè)）</p><p><b>　　柔性流水作業(yè)</b></p><p>　　任務(wù)和作業(yè)排序問(wèn)題中的約束條件，主要指的是任務(wù)或作業(yè)的性質(zhì)以及它們?cè)诩庸み^(guò)程中的要求和限制。下邊的數(shù)據(jù)描述了任務(wù)的一些性質(zhì)<

31、;/p><p><b>　　(1)加工時(shí)間向量</b></p><p>　　任務(wù)的加工時(shí)間向量是</p><p><b>　　=(,,…,)</b></p><p>　　其中是任務(wù) 在處理機(jī)，上所需要的加工時(shí)間，對(duì)同速機(jī)有=，i=1,2，…，m，對(duì)恒速機(jī)有,= /，i=1,2，…,m。其中 是標(biāo)準(zhǔn)的加工

32、時(shí)間(一般是速度最慢的處理機(jī)的加工時(shí)間)，是處理機(jī)的速度因子，在車間作業(yè)的排序問(wèn)題中，作業(yè)的加工時(shí)間向量是</p><p><b>　　=(,,…,)</b></p><p>　　其中,是工序。在對(duì)應(yīng)的處理機(jī)上的加工時(shí)間。</p><p><b>　　(2)到達(dá)時(shí)間</b></p><p>　　到達(dá)

33、時(shí)間( arrival time)或準(zhǔn)備時(shí)間(ready time) 是任務(wù)已經(jīng)準(zhǔn)備好可以被加工的時(shí)間如果所有的任務(wù)的準(zhǔn)備時(shí)間相同，取=0 ;j=1,2, …,n。</p><p>　　(3)工期和截止期限</p><p>　　工期(due date)表示對(duì)任務(wù)限定的完工時(shí)間.如果不按期完工，應(yīng)受到一定的懲罰。絕對(duì)不準(zhǔn)許延誤的工期稱為截止期限(deadline) 。</p>

34、<p><b>　　(4)優(yōu)先因子</b></p><p>　　優(yōu)先因子瑪是一個(gè)權(quán)，它表示任務(wù)相對(duì)于其他任務(wù)的重要程度.為了敘述方便起見，我們假設(shè)以上參數(shù)，，和都是整數(shù).實(shí)際上這等價(jià)于它們可以是任意的有理數(shù)。</p><p>　　我們經(jīng)常用向量和矩陣的列給出這些數(shù)據(jù)。例如用</p><p><b>　　r=(,,…,)<

35、;/b></p><p><b>　　d=(,,…,)</b></p><p><b>　　w=(,,…,)</b></p><p>　　分別表示n個(gè)任務(wù)的到達(dá)時(shí)間、工期和優(yōu)先因子。用</p><p>　　的第i行(,, …,)表示n個(gè)任務(wù)在第i個(gè)處理機(jī)上的加工時(shí)間。</p>&

36、lt;p>　　任務(wù)被加工時(shí)的一個(gè)重要約束是可中斷(preemptive)或不可中斷(nonpreemptive).如果排序問(wèn)題中，每一個(gè)任務(wù)在加工時(shí)的任一時(shí)刻都可暫停加工，加工該任務(wù)的處理機(jī)可去加工任何其他任務(wù)，以后可在任何時(shí)刻在任意處理機(jī)上重新繼續(xù)加工，這種排序問(wèn)題稱之為可中斷排序.任何任務(wù)都不允許中斷的排序問(wèn)題稱為不可中斷排序。</p><p>　　加工任務(wù)時(shí)的另一個(gè)重要限制是任務(wù)之間的優(yōu)先約束(pre

37、cedence constraints)。任務(wù)之間的優(yōu)先約束是任務(wù)集上的一個(gè)偏序關(guān)系。</p><p>　　味著必須加工完才能開始加工。如果任務(wù)集T中至少有兩個(gè)任務(wù)受到優(yōu)先約束的限制，集T的任務(wù)稱為相關(guān)的(dependent)，否則稱為無(wú)關(guān)的(indepent)。</p><p>　　1.2.1排序問(wèn)題的分類</p><p>　　在排序問(wèn)題中，如果所有的數(shù)據(jù)在進(jìn)行決

38、策之前都是己知的，排序問(wèn)題稱為確定性排序(deterministic scheduling)問(wèn)題。如果有的數(shù)據(jù)，例如加工時(shí)間、準(zhǔn)備時(shí)間和工期等，在做決策時(shí)是未知的，它們是一些隨機(jī)變量，但它們的分布是己知的，這樣的排序問(wèn)題稱為隨機(jī)排序(stochastic scheduling)問(wèn)題。無(wú)論是確定性排序還是隨機(jī)排序，我們都假設(shè):</p><p>　　(1)任務(wù)或作業(yè)和處理機(jī)都是有限的。</p><

39、p>　　(2)在任一時(shí)刻，任何處理機(jī)只能加工一個(gè)任務(wù)或一道工序。</p><p>　　(3)極小化單一目標(biāo)函數(shù)，在隨機(jī)排序中，極小化目標(biāo)函數(shù)的數(shù)學(xué)期望。</p><p>　　處理機(jī)、任務(wù)或作業(yè)和目標(biāo)函數(shù)三要素組成了排序問(wèn)題。處理機(jī)的數(shù)量、類型和環(huán)境有近十種情況，任務(wù)或作業(yè)和資源的約束條件更是錯(cuò)綜復(fù)雜，再加上度量不同指標(biāo)的目標(biāo)函數(shù)，形成了種類繁多的排序類型。我們用Graham等人首先使

40、用的三元組來(lái)描述排序問(wèn)題的類型，這樣能大大簡(jiǎn)化排序問(wèn)題的表示。</p><p>　　1.3 排序問(wèn)題的求解</p><p>　　1.3.1可行排序和最優(yōu)排序</p><p>　　排序問(wèn)題是一類組合最優(yōu)化問(wèn)題.由于排序問(wèn)題中的處理機(jī)、任務(wù)或作業(yè)都是有限的，絕大部分排序問(wèn)題是從有限個(gè)可行解中找出一個(gè)最優(yōu)解，使目標(biāo)函數(shù)達(dá)到極小。在排序問(wèn)題中，把可行解稱為可行排序(feas

41、ible schedule)，最優(yōu)解稱為最優(yōu)排序(optimal schedule)。</p><p>　　在排序問(wèn)題中，一個(gè)可行排序是一個(gè)順序(sequence)或排列(permutalion)，按照這個(gè)順序，在給定的處理機(jī)上加工所有的任務(wù)或作業(yè)。</p><p>　　例1.1給定排序問(wèn)題1||∑，其中n=4,</p><p>　　P=(3，2，5，i)，r=(0

42、，1，0，0)</p><p>　　[,,,]是一個(gè)可行排序，對(duì)應(yīng)的總加工時(shí)間是31,[,,,]是一個(gè)最優(yōu)排序，最優(yōu)總加工時(shí)間是21。</p><p><b>　　符號(hào)說(shuō)明</b></p><p><b>　　——第J個(gè)任務(wù)</b></p><p><b>　　T 一一任務(wù)集</b&

43、gt;</p><p><b>　　——第j個(gè)作業(yè)</b></p><p><b>　　J 一一作業(yè)集</b></p><p><b>　　——第J種資源</b></p><p><b>　　R 一一資源集</b></p><p>

44、<b>　　——任務(wù)的加工時(shí)間</b></p><p>　　P ——n個(gè)任務(wù)的加工時(shí)間向量</p><p>　　——任務(wù)的隨機(jī)加工時(shí)間</p><p>　　——任務(wù)在處理機(jī)上的加工時(shí)間</p><p>　　——任務(wù)在處理機(jī)上的隨機(jī)加工時(shí)間</p><p>　　——任務(wù)或作業(yè)的到達(dá)時(shí)間</p&

45、gt;<p>　　r——n個(gè)任務(wù)的到達(dá)時(shí)間向量</p><p>　　——任務(wù)或作業(yè)的工期或截止期限</p><p>　　d --- n個(gè)任務(wù)的工期向量</p><p>　　——任務(wù)的優(yōu)先因子(權(quán))</p><p>　　W——n個(gè)任務(wù)的優(yōu)先因子向量</p><p>　　——任務(wù)或作業(yè)的完工時(shí)間</p

46、><p><b>　　——時(shí)間表長(zhǎng)</b></p><p>　　——任務(wù)或作業(yè)的延誤時(shí)間</p><p>　　——任務(wù)或作業(yè)的誤工時(shí)間</p><p>　　——對(duì)任務(wù)或作業(yè)誤工的單位懲罰</p><p><b>　　—— m個(gè)同速機(jī)</b></p><p>

47、;　　第二章 具有學(xué)習(xí)效應(yīng)的總完工時(shí)間流水線排序</p><p><b>　　2.1 問(wèn)題描述</b></p><p>　　具有學(xué)習(xí)效應(yīng)的流水作業(yè)排序問(wèn)題的一般描述如下:設(shè)有n個(gè)工件,,…,依次在機(jī)器上加工。工件在2臺(tái)機(jī)器和上加工,在每個(gè)機(jī)器上的加工順序相同,工件在機(jī)器的工序記為,工序的正常加工時(shí)間為。設(shè)工序排在第r個(gè)位置的實(shí)際加工時(shí)間為。</p>&

48、lt;p>　　= （2—1）</p><p>　　式中:i=1,2, …,m; r,j=1,2,…,n; α為學(xué)習(xí)因子,且0<α≤1;r表示工件實(shí)際加工時(shí)所排的位置。對(duì)于給定的排序,工序的完工時(shí)間記為,工序的完工時(shí)間稱為工件的完工時(shí)間,記為即。對(duì)于2臺(tái)機(jī)器上具有指數(shù)學(xué)習(xí)效應(yīng)的最大完工時(shí)間的流水作業(yè)問(wèn)題,用三參數(shù)表示法表示為 </p>

49、<p><b>　　F2|=|∑</b></p><p>　　對(duì)于經(jīng)典流水作業(yè)問(wèn)題F2‖∑是NP-難的,所以問(wèn)題F2|=|∑也是NP-難的。</p><p><b>　　2.2 預(yù)備知識(shí)</b></p><p>　　2.2.1學(xué)習(xí)效應(yīng)的概念</p><p>　　在制造業(yè)系統(tǒng)中,排序問(wèn)題

50、是一類重要的問(wèn)題,多年來(lái)人們一直致力于該問(wèn)題的研究。在大多數(shù)排序問(wèn)題中,工件的加工是一個(gè)獨(dú)立的且與加工位置無(wú)關(guān)的常數(shù)。然而,在一些實(shí)際排序問(wèn)題中,由于工人(機(jī)器)在長(zhǎng)時(shí)間加工相同或類似的工件時(shí),加工效率有可能逐漸提高,使后加工的工件的加工時(shí)間變小,這種現(xiàn)象被稱為具有學(xué)習(xí)效應(yīng)。</p><p>　　學(xué)習(xí)曲線又叫經(jīng)驗(yàn)曲線，是一種可以顯示單位產(chǎn)品生產(chǎn)時(shí)間與所生產(chǎn)的產(chǎn)品總數(shù)之間的關(guān)系的曲線。學(xué)習(xí)曲線可以用于個(gè)人和組織。當(dāng)

51、人們重復(fù)同一過(guò)程工作中并從他們自己的作業(yè)經(jīng)歷中獲得技能和提高效率，個(gè)人的學(xué)習(xí)能力將得到提高，即所謂的“熟能生巧”。組織的學(xué)習(xí)能力同樣來(lái)源于實(shí)踐，但也來(lái)源于管理、設(shè)備和產(chǎn)品設(shè)計(jì)等方面的變化。在組織學(xué)習(xí)中我們期望能夠同時(shí)達(dá)到兩種學(xué)習(xí)能力的提高，通常用一條學(xué)習(xí)曲線來(lái)描述兩者相結(jié)合的結(jié)果。</p><p>　　學(xué)習(xí)曲線基于以下三條假設(shè)：</p><p>　　1、每次完成同一性質(zhì)的工作后，下次完成該

52、性質(zhì)的工作或生產(chǎn)單位產(chǎn)品的時(shí)間將減少；</p><p>　　2、單位產(chǎn)品生產(chǎn)時(shí)間將以一種遞減的速率下降；</p><p>　　3、單位產(chǎn)品生產(chǎn)時(shí)間的減少將遵循一個(gè)可預(yù)測(cè)的模式。</p><p>　　學(xué)習(xí)曲線方程的一般形式是:</p><p>　　Yx=K（n為X的指數(shù)）</p><p>　　式中: X =單位數(shù)量<

53、;/p><p>　　= 生產(chǎn)第X個(gè)產(chǎn)品所需的直接勞動(dòng)小時(shí)數(shù)</p><p>　　K = 生產(chǎn)第一個(gè)產(chǎn)品所需的直接勞動(dòng)小時(shí)數(shù)</p><p>　　n = lgb/lg X，其中b 為學(xué)習(xí)比例</p><p>　　以上三條假設(shè)最初是從飛機(jī)制造過(guò)程中得到驗(yàn)證的，也就是學(xué)習(xí)曲線最先被應(yīng)用在飛機(jī)制造業(yè)。在飛機(jī)制造過(guò)程中發(fā)現(xiàn)，每當(dāng)產(chǎn)量翻倍，用于制造飛機(jī)的時(shí)間

54、就會(huì)減少20%。也就是說(shuō)，假設(shè)制造第一架飛機(jī)用時(shí)100000小時(shí)，那么當(dāng)制造第二架的時(shí)候，用時(shí)就為80000小時(shí)，而第四架就會(huì)耗去64000小時(shí)，以此類推。換言之，制造第二架飛機(jī)所用時(shí)間是制造第一架飛機(jī)時(shí)間的80%，制造第四架飛機(jī)所用時(shí)間是制造第二架飛機(jī)時(shí)間的80%，當(dāng)時(shí)的人們把這種關(guān)系稱為學(xué)習(xí)曲線，80%叫做學(xué)習(xí)率。</p><p>　　學(xué)習(xí)曲線理論有兩種主要的模型：?jiǎn)挝划a(chǎn)品生產(chǎn)時(shí)間學(xué)習(xí)曲線和累計(jì)平均時(shí)間學(xué)習(xí)曲

55、線。單位產(chǎn)品生產(chǎn)時(shí)間學(xué)習(xí)曲線表示的是生產(chǎn)第N個(gè)單位的產(chǎn)品耗用了多少時(shí)間，而累計(jì)平均時(shí)間學(xué)習(xí)曲線表示的是生產(chǎn)N個(gè)單位的產(chǎn)品總共耗用了多少時(shí)間</p><p>　　不同的人或者組織或者工作，由于環(huán)境、方法、素質(zhì)等因素的差異，學(xué)習(xí)率會(huì)有不同。一般來(lái)說(shuō)，對(duì)于簡(jiǎn)單的任務(wù)，傾向于采用95%的學(xué)習(xí)率，中等復(fù)雜的任務(wù)采用80%-90%的學(xué)習(xí)率，高復(fù)雜程度的任務(wù)傾向于使用70%-80%的學(xué)習(xí)率。</p><p&

56、gt;　　2.3 單機(jī)排序問(wèn)題</p><p>　　單機(jī)排序問(wèn)題是最簡(jiǎn)單的一類排序問(wèn)題，同時(shí)也是最重要的排序問(wèn)題之一首先單機(jī)排序問(wèn)題比較容易求出解決方法，這些方法對(duì)于研究比較復(fù)雜的排序問(wèn)題具有指導(dǎo)作用，可以為處理復(fù)雜排序問(wèn)題提供近似算法;其次，單機(jī)排序問(wèn)題大量存在于現(xiàn)實(shí)生活中，具有廣泛的實(shí)際背景，許多實(shí)際問(wèn)題都可以歸結(jié)為單機(jī)排序問(wèn)題。因此，單機(jī)排序問(wèn)題對(duì)于有效地利用資源，提高生產(chǎn)效率，具有十分重要的指導(dǎo)意義。&l

57、t;/p><p>　　2.3.1 加權(quán)總完工時(shí)間問(wèn)題</p><p>　　單機(jī)排序問(wèn)題的一個(gè)重要目標(biāo)函數(shù)是加權(quán)平均流時(shí)間。由于極小化加權(quán)平均流時(shí)間等價(jià)于極小化加權(quán)總完工時(shí)間，因此下面僅以加權(quán)總完工時(shí)間為目標(biāo)函數(shù)討論問(wèn)題.首先討論問(wèn)題</p><p>　　1‖∑ (21)</p><p>　　其中是任務(wù)的完工時(shí)間，是賦予任務(wù)的權(quán)，它表示的

58、重要程度.對(duì)于問(wèn)題(2.3.1)，應(yīng)用加權(quán)最短加工時(shí)間優(yōu)先(weighted shortest processing time first，簡(jiǎn)記WSPT)規(guī)則可以得到最優(yōu)排序。按照這一規(guī)則，任務(wù)按/非增的順序進(jìn)行排序。對(duì)于相等的特殊情況，加權(quán)最短加工時(shí)間優(yōu)先規(guī)則化為最短加工時(shí)間優(yōu)先(shortest processing time first，簡(jiǎn)記SPT)規(guī)則。</p><p>　　定理2.1對(duì)于問(wèn)題(2.1),

59、WSPT規(guī)則得到的是最優(yōu)排序。</p><p>　　證明假定某最優(yōu)排序 違反了WSPT規(guī)則，則在此排序中，至少有兩個(gè)相鄰任務(wù)與 (在前)，使/< /，設(shè)在時(shí)間t時(shí)開始加工.將 做變動(dòng)如下:對(duì)調(diào)任務(wù)與的位置，保持其余任務(wù)位置不變，從而得到另一個(gè)排序，見圖2.1.在中，的開始加工時(shí)間是t，緊隨其后.顯然與加權(quán)總完工時(shí)間的差別僅在于任務(wù)與的加權(quán)完工時(shí)間不同。在中，和的加權(quán)完工時(shí)間為</p><

60、p>　　(t+)+(t++)</p><p><b>　　而在中為</b></p><p>　　(t+)+(t++)</p><p>　　從而在兩種順序下加權(quán)總完工時(shí)間之差為</p><p><b>　　(∑)一(∑)</b></p><p>　　=(t+)+(t++)

61、- (t+)-(t++)</p><p><b>　　=-=(-)</b></p><p>　　在假設(shè)條件下，顯然有</p><p><b>　　(∑)>(∑)</b></p><p>　　與是最優(yōu)排序矛盾.定理證畢。</p><p><b>　　2.4數(shù)學(xué)規(guī)

62、劃模型</b></p><p>　　下面給出問(wèn)題F2|=|∑的數(shù)學(xué)規(guī)劃模型。</p><p><b>　　目標(biāo)函數(shù):</b></p><p><b>　　約束條件:</b></p><p>　　i=1,2; r=1,2，…，n </p><p>

63、　　≥﹢, r＝1,2, …,n （2—5）</p><p>　?。僵€， r＝1,2, …,n (2—6)</p><p><b>　　(2—7)</b></p><p>　　r＝1,2, …,n；＝＝0</p><p>　　式中:j為工件數(shù),j=1,2,…,n;i為機(jī)器數(shù)，

64、i=1,2；為在機(jī)器i上排在第r個(gè)位置工件的實(shí)際加工時(shí)間,i=1,2；r=1,2,…,n; 為在第二臺(tái)機(jī)器上第r個(gè)工件的開始時(shí)間與第r-1個(gè)工件的完工時(shí)間之間的空閑時(shí)間，r=1,2，…，n；為第1臺(tái)機(jī)器上第r個(gè)工件的完工時(shí)間和它在第2臺(tái)機(jī)器上的開始時(shí)間之差r=1,2，…，n；Sr為第1臺(tái)機(jī)器上第r個(gè)工件的開始時(shí)間,r=1,2,…,n。約束(2)說(shuō)明在第r個(gè)位置只有一個(gè)工件;約束(3)說(shuō)明每個(gè)工件只排在一個(gè)位置; 約束(4)表示第r個(gè)工件

65、在機(jī)器上的實(shí)際加工時(shí)間; 約束(5、6、7)分別表示第r個(gè)工件的開始時(shí)間、完工時(shí)間與空閑時(shí)間約束。所有的變量都是大于等于0且Zjr只能等于1或0。</p><p><b>　　決策變量：</b></p><p>　　1 如果工件Jj排在第r個(gè)位置</p><p>　　= </p><p>

66、<b>　　0　 否則</b></p><p>　　j,r=1,2,…,n</p><p>　　式(1)中的與式(4)中的表達(dá)的意思不同,式(1)中的表示在機(jī)器上的工件排在第r個(gè)位置的實(shí)際加工時(shí)間;而式(4)中的表達(dá)的是在機(jī)器上排在第r個(gè)位置的實(shí)際加工時(shí)間。</p><p><b>　　2.5　啟發(fā)式算法</b><

67、/p><p>　　前面已把求F2|=|∑的最優(yōu)解問(wèn)題轉(zhuǎn)化為求解相應(yīng)的數(shù)學(xué)規(guī)劃模型,數(shù)學(xué)規(guī)劃問(wèn)題通過(guò)數(shù)學(xué)軟件Lingo或Lindo進(jìn)行計(jì)算,得到最優(yōu)解,但是,數(shù)學(xué)規(guī)劃模型只能解決小規(guī)模問(wèn)題,大規(guī)模問(wèn)題運(yùn)行的時(shí)間過(guò)長(zhǎng),很難求到最優(yōu)解。</p><p>　　引理1　對(duì)于問(wèn)題1 |=|∑,SPT(把工件按非減順序排列)規(guī)則產(chǎn)生最優(yōu)排序。</p><p>　　受單機(jī)排序問(wèn)題的啟發(fā)

68、(引理1),可以給出把工件按照在第1臺(tái)機(jī)器上的加工時(shí)間的SPT規(guī)則排序或把工件按照在第1和第2臺(tái)機(jī)器上的加工時(shí)間和的SPT規(guī)則排序作為啟發(fā)式算法。為了進(jìn)一步改進(jìn)啟發(fā)式算法,可以用交換工件位置的方法,得到改進(jìn)解。下面給出這3個(gè)算法的詳細(xì)步驟:</p><p>　　2.5.1 啟發(fā)式算法1</p><p>　　(1)把工件按 (表示工件在第1臺(tái)機(jī)器上的加工時(shí)間)非減(SPT規(guī)則)順序排列,即把

69、工件按≤≤ … ≤排列得到的排序;</p><p>　　(2)設(shè)由步驟(1)得到的排序?yàn)?;</p><p><b>　　(3)置k=1;</b></p><p>　　(4)置i=k+1;</p><p>　　(5)通過(guò)交換第k和第i個(gè)工件得到新的排序。如果排序的目標(biāo)函數(shù)值小于排序的目標(biāo)函數(shù)值,則用代替;</p&g

70、t;<p>　　(6)如果i＜n,則置i=i+1,轉(zhuǎn)(5);</p><p>　　(7)如果k＜n-1,則置k=k+1,轉(zhuǎn)(4);否則,停止。</p><p>　　2.5.2 啟發(fā)式算法2</p><p>　　(1)把工件按 (表示工件在第2臺(tái)機(jī)器上的加工時(shí)間)非減(SPT規(guī)則)順序排列,即≤≤ … ≤排列得到的排序;</p><p

71、>　　(2)設(shè)由步驟(1)得到的排序?yàn)?</p><p><b>　　(3)置k=1;</b></p><p>　　(4)置i=k+1;</p><p>　　(5)通過(guò)交換第k和第i個(gè)工件得到新的排序。如果排序的目標(biāo)函數(shù)值小于排序的目標(biāo)函數(shù)值,則用代替;</p><p>　　(6)如果i＜n,則置i=i+1,轉(zhuǎn)(5

72、);</p><p>　　(7)如果k＜n-1,則置k=k+1,轉(zhuǎn)(4);否則,停止。</p><p>　　2.5.3 啟發(fā)式算法3</p><p>　　(1)把工件按+非減(SPT規(guī)則)順序規(guī)列,即+≤+≤ … ≤ +排列得到的排序;</p><p>　　(2)設(shè)由步驟(1)得到的排序?yàn)?</p><p>

73、;<b>　　(3)置k=1;</b></p><p>　　(4)置i=k+1;</p><p>　　(5)通過(guò)交換第k和第i個(gè)工件得到新的排序。如果排序的目標(biāo)函數(shù)值小于排序的目標(biāo)函數(shù)值,則用代替;</p><p>　　(6)如果i<n,則置i=i+1,轉(zhuǎn)(5);</p><p>　　(7)如果k<n-1,則

74、置k=k+1,轉(zhuǎn)(4),否則,停止。</p><p><b>　　2.6 數(shù)值試驗(yàn)</b></p><p><b>　　2.6.1基本假設(shè)</b></p><p>　?。?）工件數(shù)為5個(gè)，機(jī)器數(shù)為2臺(tái)</p><p>　?。?）假設(shè)第1臺(tái)機(jī)器上第r個(gè)工件的完工時(shí)間和它在第2臺(tái)機(jī)器上的開始時(shí)間之差皆

75、為5min，即。</p><p>　　（3）假設(shè)5個(gè)不同工件在第一臺(tái)機(jī)器每一個(gè)批次的實(shí)際加工時(shí)間分別為4,6,7,5，9。在第二臺(tái)機(jī)器實(shí)際加工時(shí)間分別為7,11,10,9,6。另外，每種工件各有5個(gè)批次。</p><p>　　（4）假設(shè)學(xué)習(xí)因子α=0.9</p><p>　?。?）假設(shè)第二臺(tái)機(jī)器上第r個(gè)工件的開始時(shí)間與第r-1個(gè)工件的完工時(shí)間之間的空閑時(shí)間為0，即。

76、</p><p><b>　　2.6.2數(shù)據(jù)模擬</b></p><p>　　對(duì)于問(wèn)題F2|=|∑，令∑ 表示得到的最優(yōu)解,令表示按啟發(fā)式算法1得到的排序, ∑ ()表示用啟發(fā)式算法1得到的總完工時(shí)間。令表示按啟發(fā)式算法2得到的排序, ∑ ()表示用啟發(fā)式算法2的總完工時(shí)間。令表示按啟發(fā)式算法3得到的排序,∑Cj()表示用啟發(fā)式算法3排序得到的總完工時(shí)間。</p

77、><p>　　由以上假設(shè)我們可以得到|=|∑ 代入數(shù)據(jù)后可知：</p><p><b>　　目標(biāo)函數(shù)：</b></p><p>　　根據(jù)2.4數(shù)學(xué)規(guī)劃模型我們可得出：</p><p>　　即第一種工件的五個(gè)批次的完工時(shí)間分別為4,3.6,3.24,2.92,2.62min。那么第一種工件五個(gè)批次的總完工時(shí)間為18.74mi

78、n。即 。 以此類推可知，</p><p>　　， r＝1,2, …,5 　　 </p><p><b>　　則目標(biāo)函數(shù)</b></p><p>　　第三章 流水線作業(yè)排序模型仿真</p><p><b>　　3.1仿真軟件介紹</b><

79、;/p><p>　　Lekin一款很好的生產(chǎn)運(yùn)作管理研究與教學(xué)軟件，可以快速建立單機(jī)，流水，柔性流水車間，作業(yè)車間等模型。包含許多調(diào)度算法和啟發(fā)式算法。</p><p>　　3.2 Liken仿真軟件算法介紹</p><p>　　3.2.1 EDD算法規(guī)則</p><p>　　最早交期法則（EDD）：最大延誤時(shí)間最小化。交期越早者排越前面。1

80、955年Jackson提出EDD（Early Due Date）派工法則其應(yīng)用在最小化最大延誤時(shí)間和最大延遲時(shí)間，但是此法會(huì)有增加延遲工作數(shù)目和增加平均延遲時(shí)間的傾向。</p><p>　　3.2.2 加權(quán)最短作業(yè)時(shí)間法則（WSPT）</p><p>　　最小化平均加權(quán)流程時(shí)間。將作業(yè)時(shí)間除以權(quán)重所得之值越小者排越前面。</p><p>　　當(dāng)工作附有重要性的屬性

81、時(shí)，排序人員可給予個(gè)別的權(quán)重權(quán)重值越大表示重要性越大。WSPT法則即是將作業(yè)時(shí)間除以權(quán)重所得的值越小者表示越重要的工作，而它將排至順序的第一位，以此類推。加權(quán)平均流程時(shí)間的計(jì)算方法為：</p><p>　　3.2.3 SPT算法規(guī)則</p><p>　　最短作業(yè)時(shí)間法則(SPT) ：最小化平均流程時(shí)間。job作業(yè)時(shí)間越小者排越前面，亦可以使平均延誤時(shí)間，平均等候時(shí)間最小化。</p&

82、gt;<p>　　最短作業(yè)時(shí)間法則——最小化平均流程時(shí)間</p><p>　　當(dāng)n個(gè)作業(yè)要排至單一機(jī)臺(tái)上時(shí)，利用SPT (Shortest Process Time) 法則排序可使得平均流程時(shí)間最小化，也就是。</p><p><b>　　范例3.1</b></p><p>　　給予一組工作集如下表所示，目標(biāo)為最小化平均流程時(shí)間&

83、lt;/p><p><b>　　表 3.1</b></p><p>　　依SPT派工法則排序，順序?yàn)?-1-8-7-3-2-5-6。其流程時(shí)間計(jì)算如下表 </p><p><b>　　表 3.2</b></p><p><b>　　所以平均流程時(shí)間為</b></p>

84、;<p>　　由以上可知工作流程時(shí)間的計(jì)算方式為</p><p>　　除了最小化平均流程時(shí)間以外，在單機(jī)排序問(wèn)題中SPT法則亦可以最小化平均延誤時(shí)間、最小化平均等候時(shí)間。</p><p><b>　　3.3 仿真</b></p><p>　　3.3.1仿真前提條件</p><p>　?。?）工件數(shù)為5個(gè)，

85、機(jī)器數(shù)為2臺(tái)</p><p>　?。?）假設(shè)5個(gè)不同工件在第一臺(tái)機(jī)器每一個(gè)批次的實(shí)際加工時(shí)間分別為4,6,7,5，9。在第二臺(tái)機(jī)器實(shí)際加工時(shí)間分別為7,11,10,9,6。另外，每種工件各有5個(gè)批次。</p><p>　?。?）假設(shè)學(xué)習(xí)因子α=0.9</p><p>　?。?）假設(shè)第1臺(tái)機(jī)器上第r個(gè)工件的完工時(shí)間和它在第2臺(tái)機(jī)器上的開始時(shí)間之差皆為5min，即。&l

86、t;/p><p>　　（5）假設(shè)5個(gè)作業(yè)的優(yōu)先級(jí)都為1。</p><p><b>　　3.3.2仿真計(jì)算</b></p><p>　　利用車間排序軟件Lekin，設(shè)置參數(shù)如下圖：</p><p>　?。?）如圖3.1與圖3.2，進(jìn)入lekin軟件后，點(diǎn)擊如圖中的Flow。并設(shè)置兩臺(tái)機(jī)器，五個(gè)作業(yè)，點(diǎn)擊OK。</p>

87、;<p>　　圖 3.1 圖 3.2</p><p>　?。?）圖3.3與圖3.4為對(duì)機(jī)器和進(jìn)行參數(shù)設(shè)置。</p><p>　　圖 3.3 圖 3.4</p><p>　　（3）圖3.5與圖3.6為對(duì)工作1進(jìn)行的各種參數(shù)設(shè)置。<

88、/p><p>　　圖 3.5 圖 3.6</p><p>　?。?）圖3.7與圖3.8為對(duì)工作2進(jìn)行的各種參數(shù)設(shè)置。</p><p>　　圖 3.7 圖 3.8</p><p>　?。?）圖3.9與圖3.10為對(duì)工作3進(jìn)行

89、的各種參數(shù)設(shè)置。</p><p>　　圖 3.9 圖 3.10</p><p>　　（6）圖3.11與圖3.12為對(duì)工作4進(jìn)行的各種參數(shù)設(shè)置。</p><p>　　圖 3.11 圖 3.12</p><p>　　（7

90、）圖3.13與圖3.14為對(duì)工作5進(jìn)行的各種參數(shù)設(shè)置。</p><p>　　圖 3.13 圖 3.14</p><p>　?。?）下圖為兩臺(tái)機(jī)床，五個(gè)作業(yè)由的排序圖。</p><p><b>　　圖 3.15</b></p><p>　?。?）以下為經(jīng)過(guò)Lekin軟件

91、SPT排序所得結(jié)果。</p><p><b>　　圖 3.16</b></p><p><b>　　圖 3.17</b></p><p><b>　　圖 3.18</b></p><p>　　從圖3.17，我們可以看出，各自對(duì)應(yīng)黃色，淺藍(lán)，紫色，綠色，灰色。由此與圖3.1

92、6做對(duì)比，可知由最短作業(yè)時(shí)間法則(SPT)所得的排序?yàn)椤?lt;/p><p>　　第四章 仿真分析與算法優(yōu)化</p><p>　　4.1 車間作業(yè)排序問(wèn)題仿真優(yōu)化系統(tǒng)的構(gòu)建思想、方法與框架</p><p>　　傳統(tǒng)的仿真優(yōu)化集成思想如圖4.1所示。對(duì)系統(tǒng)建立仿真模型,將仿真輸出信息作為優(yōu)化器的輸入,對(duì)仿真輸出進(jìn)行分析與評(píng)價(jià)后,得出新的系統(tǒng)參數(shù)或決策變量再作為仿真模

93、型的新輸入,以上過(guò)程不斷重復(fù),直至滿足一定的停止規(guī)則。這種思想實(shí)現(xiàn)了優(yōu)化算法與仿真的外部集成,提高了對(duì)問(wèn)題的建模能力和靈活性。</p><p>　　輸入（決策變量） 輸出（性能指標(biāo)）</p><p>　　輸出（優(yōu)化解） 輸入（優(yōu)化參數(shù)）</p><p><b>　　圖 4.1</b>&

94、lt;/p><p><b>　　4.2 算法優(yōu)化</b></p><p>　　為了分析啟發(fā)式算法的好壞,通過(guò)與最優(yōu)解之間的平均誤差和最大誤差的比較,得到啟發(fā)式算法的好壞。按啟發(fā)式算法1得到排序的相對(duì)誤差 </p><p><b>　　平均誤差</b></p><p>

95、　　其中,10表示對(duì)每個(gè)問(wèn)題取10組實(shí)例進(jìn)行計(jì)算,最大誤差R1為相對(duì)誤差中最大的誤差;按啟發(fā)式算法2得到排序的相對(duì)誤差</p><p><b>　　平均誤差</b></p><p>　　最大誤差為相對(duì)誤差中最大的誤差;按啟發(fā)式算法3得到排序的相對(duì)誤差</p><p><b>　　平均誤差</b></p>

96、<p>　　最大誤差為相對(duì)誤差中最大的誤差。 通過(guò)C#語(yǔ)言編程,選取4個(gè)不同工件數(shù)n=8,10,12,14,在不同的工件數(shù)中隨機(jī)選取10組數(shù),其中,工件的加工時(shí)間在[1,100]隨機(jī)產(chǎn)生,每組數(shù)按啟發(fā)式算法1～3,3種排列進(jìn)行排序,并加入指數(shù)學(xué)習(xí)效應(yīng)α=0.1,0.5,0.8,分別按3種啟發(fā)式算法求出總完工時(shí)間,并把10組數(shù)據(jù)根據(jù)以上公式求取平均值,得到啟發(fā)式算法與最優(yōu)解的平均誤差和最大誤差。從計(jì)算的結(jié)果我們是可以得到一個(gè)相應(yīng)

97、的結(jié)論的，即3個(gè)啟發(fā)式算法之間沒有明顯的好壞,對(duì)于參數(shù)α=0.1,所求之解更加接近最優(yōu)解,且大部分會(huì)產(chǎn)生最優(yōu)的排序。</p><p>　　第四章 總結(jié)與展望</p><p><b>　　5.1 論文總結(jié)</b></p><p>　　2014年3月，我開始了我的畢業(yè)論文工作，時(shí)至今日，論文基本完成。從最初的茫然，到慢慢的進(jìn)入狀態(tài)，再到對(duì)思路

98、逐漸的清晰，整個(gè)寫作過(guò)程難以用語(yǔ)言來(lái)表達(dá)。歷經(jīng)了幾個(gè)月的奮戰(zhàn)，緊張而又充實(shí)的畢業(yè)設(shè)計(jì)終于落下了帷幕?；叵脒@段日子的經(jīng)歷和感受，我感慨萬(wàn)千，在這次畢業(yè)設(shè)計(jì)的過(guò)程中，我擁有了無(wú)數(shù)難忘的回憶和收獲。</p><p>　　在整個(gè)設(shè)計(jì)過(guò)程中遇到困難我就及時(shí)和導(dǎo)師聯(lián)系，并和同學(xué)互相交流，請(qǐng)教專業(yè)課老師。在大家的幫助下，困難一個(gè)一個(gè)解決掉，論文也慢慢成型。</p><p>　　當(dāng)我終于完成了所有打字、編

99、算法、排版、校對(duì)等任務(wù)后整個(gè)人都很累，但同時(shí)看著電腦熒屏上的畢業(yè)設(shè)計(jì)稿件我的心里是甜的，我覺得這一切都值了。這次畢業(yè)論文的制作過(guò)程是我的一次再學(xué)習(xí)，再提高的過(guò)程。在論文中我充分地運(yùn)用了大學(xué)期間所學(xué)到的知識(shí)。</p><p>　　我不會(huì)忘記這難忘的幾個(gè)月的時(shí)間。畢業(yè)論文的制作給了我難忘的回憶。在整個(gè)過(guò)程中，我學(xué)到了新知識(shí)，增長(zhǎng)了見識(shí)。在今后的日子里，我仍然要不斷地充實(shí)自己，爭(zhēng)取在所學(xué)領(lǐng)域有所作為。</p>

100、;<p>　　腳踏實(shí)地，認(rèn)真嚴(yán)謹(jǐn)，實(shí)事求是的學(xué)習(xí)態(tài)度，不怕困難、堅(jiān)持不懈、吃苦耐勞的精神是我在這次設(shè)計(jì)中最大的收益。我想這是一次意志的磨練，是對(duì)我實(shí)際能力的一次提升，也會(huì)對(duì)我未來(lái)的學(xué)習(xí)和工作有很大的幫助。</p><p>　　通過(guò)這一學(xué)期的畢業(yè)設(shè)計(jì)，我對(duì)流水線排序問(wèn)題有了一個(gè)基本的了解和掌握，但是每一種排序算法根據(jù)其實(shí)際生產(chǎn)線的要求卻又是各有不同的，所以我在今后的工作和學(xué)習(xí)中將會(huì)繼續(xù)努力學(xué)習(xí)，了解與

101、應(yīng)用各種流水線排序算法仿真軟件，結(jié)合自己大學(xué)以來(lái)學(xué)習(xí)的各種加工軟件，我相信在以后的工作中一定能有很大的幫助。</p><p><b>　　5.2后續(xù)與展望</b></p><p>　　此次畢業(yè)設(shè)計(jì)在此就將有一個(gè)階段性的成果，但是在此過(guò)程中，自己還是有很多的不足之處，專業(yè)知識(shí)有很強(qiáng)烈的匱乏感，這都源于知識(shí)面不夠廣闊，未能深刻鉆研專業(yè)相關(guān)的知識(shí)，針對(duì)這次的畢業(yè)設(shè)計(jì)，我認(rèn)為

102、還有必要進(jìn)一步進(jìn)行完善工作。</p><p>　　流水線排序軟件如Lekin、Arena等是一款很好的流水線排序軟件，雖然在畢業(yè)設(shè)計(jì)階段對(duì)此軟件有所學(xué)習(xí)，但我感覺操作還是生疏，需要投入更多的精力在此項(xiàng)學(xué)習(xí)。</p><p>　　在實(shí)際生產(chǎn)中，排序問(wèn)題影響因素眾多我們能想到的如各種機(jī)器故障，所用機(jī)床的實(shí)際效能，車間流水線加工的學(xué)習(xí)效應(yīng)，工件的特殊性等等都可使排序問(wèn)題變得復(fù)雜，我們應(yīng)盡可能地減

103、少或避免它們。</p><p>　　另外，因時(shí)間的關(guān)系，我對(duì)很多參數(shù)了解很膚淺，排序算法軟件中的參數(shù)較多，尤其一些功用繁多的算法軟件，這些參數(shù)的意義都非常重要，應(yīng)在今后的工作中重點(diǎn)掌握。</p><p><b>　　致 謝</b></p><p>　　在此論文撰寫過(guò)程中，要特別感謝我的導(dǎo)師王劍老師，沒有她的幫助也就沒有今天的這篇論文。求學(xué)歷程

104、是艱苦的，但是有時(shí)快樂的。在這個(gè)過(guò)程中，王老師一直嚴(yán)格要求我，督促著我們，針對(duì)同學(xué)們提出的一些問(wèn)題，總能夠提出針對(duì)性的見解，同時(shí)她更注重對(duì)我們的自學(xué)能力的培養(yǎng)。這一切都使我學(xué)到了很多知識(shí)，培養(yǎng)了我們獨(dú)立做研究的能力。同時(shí)也很感謝我們?cè)O(shè)計(jì)小組的成員們，在他們的熱心幫助和鼓勵(lì)下使我順利的完成了這篇論文。在畢業(yè)設(shè)計(jì)即將完成之際，大學(xué)的學(xué)習(xí)生活也已經(jīng)接近尾聲，在此，我對(duì)幫助過(guò)我的老師和同學(xué)們表達(dá)由衷的謝意，感謝大家四年以來(lái)對(duì)我的幫助與照顧！同時(shí)

105、，我還要感謝我所在的大學(xué)——西北工業(yè)大學(xué)明德學(xué)院，是她為我提供了舒適的生活條件及良好的學(xué)習(xí)環(huán)境。本文參考了大量的文獻(xiàn)資料，在此，向?qū)W術(shù)界的前輩們致敬！</p><p><b>　　參考文獻(xiàn)</b></p><p>　　[1]　Badiru A B.Computational survey of univariate and multivariate learning

106、curve models[J].IEEE transactions on Engineering Management 1992;39(2):176-188.</p><p>　　[2]BiskupD.Single-machine scheduling with learning considerations [J].European Journal of Operational Research 1999;1

107、15(1):173-178.</p><p>　　[3]　Cheng T C E,Wang G.Single machine scheduling with learning effect considerations[J].Annals of Operations Research 2000;98(1-4):273-290.</p><p>　　[4]　Mosheiov G.Schedu

108、ling problems with a learning effect[J].European Journal of Operational Research 2001;132(3):687-693.</p><p>　　[5]　Mosheiov G.Parallel machine scheduling with a learning effect[J].Journal of the Operational

109、Research Society,2001,52(10):1165-1169.</p><p>　　[6]　Mosheiov G,Sidney J B.Scheduling with general job-dependent learning curves[J].European Journal of Operational Research,2003,147:665-670.</p><p

110、>　　[7]　Mosheiov G,Sidney J B.Note on scheduling with general learning curves to minimize the number of tardy jobs.Journal of the Operational Research Society,2005,56:110-112.</p><p>　　[8]　Bachman A,Janiak

111、 A.Scheduling jobs with position dependent processing times[J].Journal of the Operational Research Society,2004,55:257-264.</p><p>　　[9]　Wang J B.Flow shop scheduling jobs with position-dependent processing

112、times[J].Journal of Applied Mathematics and Computing,2005,18(1-2):383-391.</p><p>　　[10]　Wang J B,Xia Z Q.Flow shop scheduling with a learning effect[J].Journal of the Operational Research Society,2005,56(1

113、1):1325-1330.</p><p>　　[11]　Wang J B,Wang M Z,Xia Z Q.Single machine scheduling problems with a general learning effect [J].Journal of Mathematical Research and Exposition,2005,25(4):642-646.</p><

114、p>　　[12]　Chen P,Wu C C,Lee W C.A bi-criteria two-machine flowshop scheduling problem with a learning effect[J].Journal of the Operational Research Society,2006,57(9):1113-1125.</p><p><b>　　畢業(yè)設(shè)計(jì)小結(jié)<

115、;/b></p><p>　　三個(gè)多月的畢業(yè)設(shè)計(jì)即將結(jié)束，至此，我談一下個(gè)人的幾點(diǎn)體會(huì)：</p><p>　?。?）這次畢業(yè)設(shè)計(jì)大部分時(shí)間都在老師指導(dǎo)下，獨(dú)立進(jìn)行的。跟以前的學(xué)習(xí)環(huán)境有了很大的不同，更多是強(qiáng)調(diào)獨(dú)立專研能力的培養(yǎng)。這次畢業(yè)設(shè)計(jì)過(guò)程讓我充分體驗(yàn)了另一種獨(dú)立學(xué)習(xí)和團(tuán)隊(duì)配合精神，那就是老師做適當(dāng)?shù)闹笇?dǎo)，自己查閱資料，通過(guò)自學(xué)解決問(wèn)題。這給我在今后的工作開了個(gè)好頭。</p

116、><p>　　（2） 要敢于探討問(wèn)題，虛心細(xì)心地跟老師討論問(wèn)題。在做畢業(yè)設(shè)計(jì)的過(guò)程中老師會(huì)每周都給我們指導(dǎo)，一定要虛心的跟老師討論問(wèn)題，說(shuō)出自己的問(wèn)題，才便于老師了解你。 </p><p>　?。?） 在遇到任何困難時(shí)，不灰心，不氣餒，一定要用正確的、科學(xué)的態(tài)度來(lái)對(duì)待問(wèn)題，認(rèn)真解決好每一個(gè)問(wèn)題，嚴(yán)謹(jǐn)治學(xué)，勇于探索，要有鉆研精神。</p><p>　　（4） 學(xué)習(xí)是一個(gè)長(zhǎng)