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

西北工業(yè)大學(xué)明德學(xué)院本科畢業(yè)設(shè)計(jì)論文 I 本科畢業(yè)設(shè)計(jì)論文 題 目 具有學(xué)習(xí)效應(yīng)的總完工時(shí)間流水線排序問題與仿真 專業(yè)名稱 機(jī)械設(shè)計(jì)制造及其自動(dòng)化 學(xué)生姓名 畢業(yè)時(shí)間 二一四年 七月 西北工業(yè)大學(xué)明德學(xué)院本科畢業(yè)設(shè)計(jì)論文 I 畢業(yè) 任務(wù)書 一、題目 具有學(xué)習(xí)效應(yīng)的總完工時(shí)間流水作業(yè)排序與仿真 二、指導(dǎo)思想和目的要求 （ 1）掌握運(yùn)用所學(xué)理論知識(shí)分析解決工程實(shí)際問題的一般方法； （ 2）培養(yǎng)分析問題、解決問題和獨(dú)立工作的能力； （ 3）通過畢 業(yè)實(shí)習(xí)、畢業(yè)設(shè)計(jì)及畢業(yè)答辯全過程的訓(xùn)練，加強(qiáng) 老師與學(xué)生之間、學(xué)生與學(xué)生之間知識(shí)的相互交流，互相滲透，培養(yǎng)學(xué)術(shù)研討的好學(xué)風(fēng)； （ 4）要求同學(xué)們以滿腔的熱情、科學(xué)的態(tài)度，嚴(yán)謹(jǐn)?shù)淖黠L(fēng)、 高度的責(zé)任感從事畢業(yè)設(shè)計(jì)工作；不得敷衍了事、馬馬虎虎、得過且過；提倡周密思考、大膽創(chuàng)新，反對(duì)死搬硬套、墨守陳規(guī)；提倡共同研究，反對(duì)相互抄襲； （ 5）要求遵守學(xué)校的各項(xiàng)規(guī)章制度，確保畢業(yè)設(shè)計(jì)順利地、高質(zhì)量地完成。 三、主要技術(shù)指標(biāo) 過去處理排序問題，大多采用兩種方式 :一種是根據(jù)以往經(jīng)驗(yàn)，必要時(shí)作些修改，另一種是事物并不復(fù)雜，作些考 慮即可奏效，排序問題不成其為一門學(xué)問。計(jì)算不周即可造成重大損失，依靠拍拍腦袋已不能解決問題 ；而且產(chǎn)品更新很快，新產(chǎn)品的生產(chǎn)、銷售等沒有成法可資參考，此時(shí)各種新的組合優(yōu)化問題便涌現(xiàn)出來，排序問題便是其中之一。 1. 翻譯文獻(xiàn) 1500 2000字 2. 討論單機(jī)排序問題 3. 利用仿真軟件對(duì)單機(jī)排序問題做出算法并給出最優(yōu)解 4. 研究學(xué)習(xí)效應(yīng)對(duì)機(jī)器的影響 四、進(jìn)度和要求 （ 1）第 1-3周收集資料，根據(jù)需要學(xué)習(xí)相關(guān)的硬軟件； （ 2）第 4周進(jìn)行系統(tǒng)概要設(shè)計(jì)，提出設(shè)計(jì)的總體思想； （ 3）第 5周，初步確定設(shè)計(jì)方案； 設(shè)計(jì) 論文 西北工業(yè)大學(xué)明德學(xué)院本科畢業(yè)設(shè)計(jì)論文 II （ 4）第 6-12 周，完 成單機(jī)，針對(duì)設(shè)計(jì)中存在的缺點(diǎn)和不足，不斷完善設(shè)計(jì)方案； （ 5）第 13-14 周，撰寫并修改論文； （ 6）第 15-16 周，完成論文，準(zhǔn)備答辯資料。 五、主要參考書及參考資料 自行確定 本頁(yè)不夠可以續(xù)頁(yè) 學(xué)生 張紅偉 指導(dǎo)教師 王劍 系主任 西北工業(yè)大學(xué)明德學(xué)院本科畢業(yè)設(shè)計(jì)論文 III 摘 要 排序問題的一大特點(diǎn)是 :模型繁多，適用于某一模型的算法，只要將模型的條件稍加變化，該算法即不適用 . 包括如何對(duì)各個(gè)部件進(jìn)行分隔、布線和布局的問題” .排序論是國(guó)際上發(fā)展最迅速、研究最活躍、成果 最豐碩、前景最誘人的學(xué)科領(lǐng)域之一特別引人注目的是 :隨著現(xiàn)代工業(yè)的發(fā)展，經(jīng)典的排序模式已被突破，新的模式層出不窮，吸引了越來越多的理論工作者和實(shí)際工作者、可控排序、多目標(biāo)排序、成組分批排序、同時(shí)加工排序、準(zhǔn)時(shí)排序和窗時(shí)排序、資源受限排序、不同時(shí)開工排序、隨機(jī)排序、模糊排序、應(yīng)用排序等，就是其中發(fā)展最為迅速的一些新方向 . 在我國(guó)，對(duì)排序問題的研究較晚，雖然早在 20 世紀(jì) 50 年代末，就有人注意到這一問題一問題的研究，并開始作一些宣傳普及的工作 ；但由于眾所周知的原因，對(duì)這，直至 70 年代中才開始，到 80 年代，對(duì)算法感興 趣的人越來越多?，F(xiàn)研究工件具有學(xué)習(xí)效應(yīng)的單臺(tái)機(jī)器流水作業(yè)排序問題與仿真。工件的學(xué)習(xí)效應(yīng)指工件的加工時(shí)間為所排位置的指數(shù)函數(shù)。目標(biāo)函數(shù)為極小化總完工時(shí)間。給出該問題的數(shù)學(xué)規(guī)劃模型。同時(shí)對(duì)大規(guī)模問題給出 3個(gè)啟發(fā)式算法 ,并給出計(jì)算結(jié)果。 ， 關(guān)鍵詞 ： 排序，流水作業(yè)，學(xué)習(xí)效應(yīng)，總完工時(shí)間 西北工業(yè)大學(xué)明德學(xué)院本科畢業(yè)設(shè)計(jì)論文 IV ABSTRACT 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 separate the various components, wiring and layout. Sort theory is one of the worlds most rapid development, research the most active, the most fruitful achievements, the most attractive prospects disciplines are particularly striking: With the development of modern industry, the classic sort mode has been a breakthrough, new pattern emerging, attracting a growing number of theorists and practitioners, controlled sorting, multi-objective sort, group scheduling, while processing sort, sort, and when the time window of sorting, resource-constrained sort, is not the same start sorting, random order, fuzzy sort, sorting applications, is one of the fastest growing number of new directions. In China, the problem of sorting study late, although in the late 1950s, it was noted that a study of this issue of the problem and begin to make some outreach work.However, due to reasons known to all, this, until the mid-1970s began, to the 1980s, to more and more people interested in the algorithm. In this paper we consider single machine flowshop scheduling problem with a learning effect.The learning effect of a job is assumed to be an exponent function of its position.The objective is to find a sequence that minimizes the total completion time. A mathematical programming model is developed for the problem and three heuristic algorithms are proposed for solving the problem with large scale. Compuational results show that the proposed heuristic algorithms are effective in solving the problem with large scale. KEYWORDS: scheduling， flow shop， learning effect， the total completion time西北工業(yè)大學(xué)明德學(xué)院本科畢業(yè)設(shè)計(jì)論文 - 5 - 目 錄 錯(cuò)誤 ! 未 找 到 引 用 源 。西北工業(yè)大學(xué)明德學(xué)院本科畢業(yè)設(shè)計(jì)論文 6 第一章 緒 論 1.1 流水作業(yè)排序問題 1.1.l 引例 排序 (scheduling)問題產(chǎn)生的背景主要是機(jī)器制造，后來被廣泛應(yīng)用于計(jì)算機(jī)系統(tǒng)、運(yùn)輸調(diào)度、生產(chǎn)管理等領(lǐng)域 .從普通的生產(chǎn)部門的計(jì)劃安排、人員調(diào)度，學(xué)校課程表的制訂，到宇宙飛船的復(fù)雜龐大的飛行計(jì)劃，都要用到排序的理論和算法。在給出排序問題的一般定義之前，我們先看幾個(gè)排序在實(shí)際領(lǐng)域中應(yīng)用的例子。 例 1.1機(jī)械加工 一個(gè)機(jī)械加工車間要加工一批機(jī)器零件，每一個(gè)零件都具有相同的工序， 即按相同的順序在幾個(gè)不同的機(jī)床上加工，但每個(gè)零件在每個(gè)機(jī)床上的加 工時(shí)間可能不同 .如何安排加工順序才能以最短的時(shí)間加工完所有的零件，這是一個(gè)流水線排序問題。 例 1.2進(jìn)程調(diào)度 在計(jì)算機(jī)多道程序操作系統(tǒng)中，并發(fā)執(zhí)行多個(gè)進(jìn)程，在宏觀上同時(shí)執(zhí)行多個(gè)進(jìn)程，在微觀上在任何時(shí)刻 CPU只能執(zhí)行一個(gè)進(jìn)程。進(jìn)程的到達(dá)時(shí)間是不同的，怎樣調(diào)度這些進(jìn)程才能使 CPU 的利用率最高或進(jìn)程的平均周轉(zhuǎn)時(shí)間最短 ?這也是一個(gè)排序問題。另外，每個(gè)進(jìn)程的到達(dá)時(shí)間和執(zhí)行時(shí)間事先是不知道的，但隨機(jī)到達(dá)時(shí)間和執(zhí)行時(shí)間的分布、它們的數(shù)學(xué)期望、方差等是已知的，這時(shí)的目標(biāo)是極小化平均周轉(zhuǎn)時(shí)間的數(shù)學(xué)期望。排序問題中出現(xiàn)了隨 機(jī)變量稱作隨機(jī)排序問題。 例 1.3機(jī)場(chǎng)調(diào)度 在一個(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ù)和裝卸行李等西北工業(yè)大學(xué)明德學(xué)院本科畢業(yè)設(shè)計(jì)論文 7 服務(wù)。如果飛機(jī)在下一個(gè)機(jī)場(chǎng)不能按時(shí)降落，此時(shí)為了節(jié)省燃料，飛機(jī)不能起飛，登機(jī)時(shí)間推遲，飛機(jī)需要占有一個(gè)登機(jī)門，而其他的飛機(jī) 不能使用。 機(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ī)定是約束條件。 1.2 排序問題的定義 排序 (scheduling)問題是一類重要的組合最優(yōu)化問題，它是利用一些處理機(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ī)的利用率的描述。 在排序問題中，處理機(jī)的數(shù)量和種類，任務(wù)或作業(yè)的順序、到達(dá)時(shí)間、完工限制，資源的種類和性能等情況是錯(cuò)綜復(fù)雜的，很難用精確的數(shù)學(xué)描述給出一般的排序定義。在本書中，我們用如下方式來描述排序問題 : 給定 n個(gè)任務(wù)的任務(wù)集 T = , , m個(gè)處理機(jī)的處理機(jī)集 P =, , 和 s種資源的資源 集 R =, , 排序問題指的是在一定條件下，為了完成各項(xiàng)任務(wù)，把沙中的處理機(jī)和 (如果有 )中的資源分配給了中的任務(wù)，使目標(biāo)函數(shù)達(dá)到最優(yōu)。排序問題基本上是由處理機(jī)的數(shù)量、種類與環(huán)境，以及任務(wù)或作業(yè)的性質(zhì)和目標(biāo)函數(shù)所組成。 處理機(jī)只有一個(gè)處理機(jī)的排序問題稱為單 (處理 )機(jī) (single processor, single machine)排序問題，否則稱為多 (處理 )機(jī)排序問題。在多處理機(jī)排序問題中，如果所有的處理機(jī)都具有相同的功能，稱它們?yōu)橥悪C(jī)或平行機(jī) (parallel processors)。同類機(jī)按處理的速度又分為三種類型 :如果所有的處理機(jī)都具有相西北工業(yè)大學(xué)明德學(xué)院本科畢業(yè)設(shè)計(jì)論文 8 同的速度，稱之為同速機(jī) (identical processors )；如果處理機(jī)的速度不同，但每個(gè)處理機(jī)的速度都是常數(shù)，不依賴被加工的任務(wù)，稱它們?yōu)楹闼贆C(jī) (uniform processors)；如果處理機(jī)的速度依賴被加工的任務(wù)，它們被稱為變速機(jī)(unrelated processors)。 多處理機(jī)的另一種情況是多類型機(jī) (dedicated processors)。多類型機(jī)指的是 m個(gè)處理機(jī)具有不同的功能。在多處理 機(jī)環(huán)境中，被加工的任務(wù)需要在不同的處理機(jī)上加工 .在這種情況下，把任務(wù) (task )稱為作業(yè) (job)。設(shè)有作業(yè)集 J=, , 每個(gè)作業(yè) ,有，道工序 (operation) ， .工序指的是作業(yè)在某處理機(jī)上被加工的這部分任務(wù)。 如果每個(gè)作業(yè)需要在每個(gè)處理機(jī)上加工，即 =m ,j二 1， 2， n.而且每個(gè)作業(yè)的工序也相同，即在處理機(jī)上加工的順序相同，把這種多類機(jī)的環(huán)境稱為同順序作業(yè)或流水作業(yè) (flow shop)。 如果每個(gè)作業(yè)需要在每個(gè)處理機(jī)上加工，每 個(gè)作業(yè)有自己的加工順序，稱之為異順序作業(yè) (job shop)。 如果每個(gè)作業(yè)需要在每個(gè)處理機(jī)上加工，每個(gè)作業(yè)可按任意順序加工，把它稱為自由順序作業(yè)或開放作業(yè) (open shop ) 。 在多處理機(jī)中，還有一種更復(fù)雜的情況，這就是柔性流水作業(yè) (flexible flow shop)，它是流水作業(yè)和平行機(jī)的推廣。在柔性流水作業(yè)中，有，類處理機(jī)，第 J類有個(gè)平行機(jī)，每個(gè)作業(yè)有 s道工序，每道工序需要在每類平行機(jī)中的一個(gè)處理機(jī)上加工，且每個(gè)作業(yè)的加工順序相同。 為方便起見，以后我們把同順序作業(yè)、 異順序作業(yè)、開放作業(yè)、柔性流水作 業(yè)通稱為車間作業(yè)。 處理機(jī)的各種類型和環(huán)境總結(jié)如下 : 單處理機(jī) 同速機(jī) 同類機(jī)（平行機(jī)） 恒速機(jī) 自由順序作業(yè)（開放作業(yè)） 柔性流水作業(yè) 西北工業(yè)大學(xué)明德學(xué)院本科畢業(yè)設(shè)計(jì)論文 9 任務(wù)和作業(yè)排序問題中的約束條件，主要指的是任 務(wù)或作業(yè)的性質(zhì)以及它們?cè)诩庸み^程中的要求和限制。下邊的數(shù)據(jù)描述了任務(wù)的一些性質(zhì) (1)加工時(shí)間向量 任務(wù)的加工時(shí)間向量是 =(, ,) 其中是任務(wù) 在處理機(jī)，上所需要的加工時(shí)間，對(duì)同速機(jī)有 =， i=1,2， ， m，對(duì)恒速機(jī)有 ,= /， i=1,2， ,m。其中 是標(biāo)準(zhǔn)的加工時(shí)間 (一般是速度最慢的處理機(jī)的加工時(shí)間 )，是處理機(jī)的速度因子，在車間作業(yè)的排序問題中，作業(yè)的加工時(shí)間向量是 =(, ,) 其中 ,是工序。在對(duì)應(yīng)的處理機(jī)上的加工時(shí)間。 (2)到 達(dá)時(shí)間 到達(dá)時(shí)間 ( arrival time)或準(zhǔn)備時(shí)間 (ready time) 是任務(wù)已經(jīng)準(zhǔn)備好可以被加工的時(shí)間如果所有的任務(wù)的準(zhǔn)備時(shí)間相同，取 =0 ；j=1,2, ,n。 (3)工期和截止期限 工期 (due date) 表示對(duì)任務(wù)限定的完工時(shí)間 .如果不按期完工，應(yīng)受到一定的懲罰。絕對(duì)不準(zhǔn)許延誤的工期稱為截止期限 (deadline) 。 (4)優(yōu)先因子 優(yōu)先因子瑪是一個(gè)權(quán)，它表示任務(wù)相對(duì)于其他任務(wù)的重要程度 .為了敘述方便起見，我們假設(shè)以上參數(shù)，和都是整數(shù) .實(shí)際上這等價(jià)于它們可以是任意的有理數(shù)。 我們經(jīng) 常用向量和矩陣的列給出這些數(shù)據(jù)。例如用 r=(, ,) d=(, ,) w=(, ,) 分別表示 n個(gè)任務(wù)的到達(dá)時(shí)間、工期和優(yōu)先因子。用 的第 i行 (, ,)表示 n個(gè)任務(wù)在第 i個(gè)處理機(jī)上的加工時(shí)間。 西北工業(yè)大學(xué)明德學(xué)院本科畢業(yè)設(shè)計(jì)論文 10 任務(wù)被加工時(shí)的一個(gè)重要約束是可中斷 (preemptive)或不可中斷(nonpreemptive).如果排序問題中，每一個(gè)任務(wù)在加工時(shí)的任一時(shí)刻都可暫停加工，加工該任務(wù)的處理機(jī)可去加工任何其他任務(wù)，以后可在任何時(shí)刻在任意處理機(jī)上重新繼續(xù)加工，這種排序問題稱之為可中斷排序 .任何任務(wù)都不允許中斷的排序問題稱為不可中斷排序。 加工任務(wù)時(shí)的另一個(gè)重要限制是任務(wù)之間的優(yōu)先約束 (precedence constraints)。任務(wù)之間的優(yōu)先約束是任務(wù)集上的一個(gè)偏序關(guān)系。 味著必須加工完才能開始加工。如果任務(wù)集 T 中至少有兩個(gè)任務(wù)受到優(yōu)先約束的限制，集 T 的任務(wù)稱為相關(guān)的 (dependent)，否則稱為無關(guān)的 (indepent)。 1.2.1 排序問題的分類 在排序問題中，如果所有的數(shù)據(jù)在進(jìn)行決策之前都是己知的，排序問題稱為確定性排序 (deterministic scheduling)問題。如果有的數(shù)據(jù)，例如加工時(shí)間、準(zhǔn)備時(shí)間和工期等，在做決策時(shí)是未知的，它們是一些隨機(jī)變量，但它們的分布是己知的，這樣的排序問題稱為隨機(jī)排序 (stochastic scheduling)問題。無論是確定性排序還是隨機(jī)排序，我們都假設(shè) : (1)任務(wù)或作業(yè)和處理機(jī)都是有限的。 (2)在任一時(shí)刻，任何處理機(jī)只能加工一個(gè)任務(wù)或一道工序。 (3)極小化單一目標(biāo)函數(shù)，在隨機(jī)排序中，極小化目標(biāo)函數(shù)的數(shù)學(xué)期望。 處理機(jī)、任務(wù)或作業(yè)和目標(biāo)函數(shù)三要素組成了排序問題 。處理機(jī)的數(shù)量、類型和環(huán)境有近十種情況，任務(wù)或作業(yè)和資源的約束條件更是錯(cuò)綜復(fù)雜，再加上度量不同指標(biāo)的目標(biāo)函數(shù)，形成了種類繁多的排序類型。我們用 Graham 等人首先使用的三元組來描述排序問題的類型，這樣能大大簡(jiǎn)化排序問題的表示。 1.3 排序問題的求解 1.3.1 可行排序和最優(yōu)排序 排序問題是一類組合最優(yōu)化問題 .由于排序問題中的處理機(jī)、任務(wù)或作業(yè)都是有限的，絕大部分排序問題是從有限個(gè)可行解中找出一個(gè)最優(yōu)解，使目標(biāo)函數(shù)達(dá)到極小。在排序問題中，把可行解稱為可行排序 (feasible schedule)，最優(yōu)解稱為 最優(yōu)排序 (optimal schedule)。 在排序問題中，一個(gè)可行排序是一個(gè)順序 (sequence)或排列 (permutalion)，按照這個(gè)順序，在給定的處理機(jī)上加工所有的任務(wù)或作業(yè)。 西北工業(yè)大學(xué)明德學(xué)院本科畢業(yè)設(shè)計(jì)論文 11 例 1.1給定排序問題 1|，其中 n=4, P=(3， 2， 5， i)， r=(0， 1， 0， 0) ,是一個(gè)可行排序，對(duì)應(yīng)的總加工時(shí)間是 31,是一個(gè)最優(yōu)排序，最優(yōu)總加工時(shí)間是 21。 符號(hào)說明 第 J個(gè)任務(wù) T 一一任務(wù)集 第 j個(gè)作業(yè) J 一一作業(yè)集 第 J種資源 R 一一資源集 任務(wù)的加工時(shí)間 P n個(gè)任務(wù)的加工時(shí)間向量 任務(wù)的隨機(jī)加工時(shí)間 任務(wù)在處理機(jī)上的加工時(shí)間 任務(wù)在處理機(jī)上的隨機(jī)加工時(shí)間 任務(wù)或作業(yè)的到達(dá)時(shí)間 r n個(gè)任務(wù)的到達(dá)時(shí)間向量 任務(wù)或作業(yè)的工期或截止期限 d - n個(gè)任務(wù)的工期向量 任務(wù)的優(yōu)先因子 (權(quán) ) W n個(gè)任務(wù)的優(yōu)先因子向量 任務(wù)或作業(yè)的完工時(shí)間 時(shí)間表長(zhǎng) 任務(wù)或作業(yè)的延誤時(shí)間 任務(wù)或作業(yè)的誤工時(shí)間 對(duì)任務(wù)或作業(yè)誤工的單位懲罰 m個(gè)同速機(jī) 西北工業(yè)大學(xué)明德學(xué)院本科畢業(yè)設(shè)計(jì)論文 12 第二章 具有學(xué)習(xí)效應(yīng)的總完工時(shí)間流水線排序 2.1 問題描述 西北工業(yè)大學(xué)明德學(xué)院本科畢業(yè)設(shè)計(jì)論文 13 具有學(xué)習(xí)效應(yīng)的流水作業(yè)排序問題的一般描述如下 :設(shè)有 n 個(gè)工件 , ,依次在機(jī)器上加工。工件在 2臺(tái)機(jī)器和上加工 ,在每個(gè)機(jī)器上的加工順序相同 ,工件在機(jī)器的工序記為 ,工序的正常加工時(shí)間為。設(shè)工序排在第 r 個(gè)位置的實(shí)際加工時(shí)間為。 = （ 2 1） 式中 :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è)問題 ,用三參數(shù)表示法表示為 F2|=| 對(duì)于經(jīng)典流水作業(yè)問題 F2是 NP-難的 ,所以問題 F2|=|也是 NP-難的。 2.2 預(yù)備知識(shí) 2.2.1 學(xué)習(xí)效應(yīng)的概念 在制造業(yè)系統(tǒng)中 ,排序問題是一類重要的問題 ,多年來人們一直致力于該問題的研究。在大多數(shù)排序問題中 ,工件的加工是一個(gè)獨(dú)立的且與加工位置無關(guān)的常數(shù)。然而 ,在一些實(shí)際排序問題中 ,由于工人 (機(jī)器 )在長(zhǎng)時(shí)間加工相同或類似的工件時(shí) ,加工效率有可能逐漸提高 ,使后加工的工件的加工時(shí)間變小 ,這種現(xiàn)象被稱為具有學(xué)習(xí)效應(yīng)。 學(xué)習(xí)曲線又叫經(jīng)驗(yàn)曲線，是一種可以顯示單位產(chǎn)品生產(chǎn)時(shí)間與所生產(chǎn)的產(chǎn)品總數(shù)之間的關(guān)系的曲線。學(xué)習(xí)曲線可以用于個(gè)人和組織。當(dāng)人們重復(fù)同一過程工作中并從他們自己的作業(yè)經(jīng)歷中獲得技能和提高效率，個(gè)人的學(xué)習(xí)能力將得到提高，即所謂的 “ 熟能生巧 ” 。組織的學(xué)習(xí)能力同樣來源于實(shí)踐，但也來源于管理、設(shè)備和產(chǎn)品設(shè)計(jì)等方面的變化。在組織學(xué)習(xí)中我們期望能夠同時(shí)達(dá)到兩種學(xué)習(xí)能力的提高，通常用一條學(xué)習(xí)曲線來 描述兩者相結(jié)合的結(jié)果。 學(xué)習(xí)曲線基于以下三條假設(shè)： 1、每次完成同一性質(zhì)的工作后，下次完成該性質(zhì)的工作或生產(chǎn)單位產(chǎn)品的時(shí)間將減少； 2、單位產(chǎn)品生產(chǎn)時(shí)間將以一種遞減的速率下降； 3、單位產(chǎn)品生產(chǎn)時(shí)間的減少將遵循一個(gè)可預(yù)測(cè)的模式。 學(xué)習(xí)曲線方程的一般形式是 : 西北工業(yè)大學(xué)明德學(xué)院本科畢業(yè)設(shè)計(jì)論文 14 Yx=K（ n為 X的指數(shù)） 式中 : X =單位數(shù)量 = 生產(chǎn)第 X個(gè)產(chǎn)品所需的直接勞動(dòng)小時(shí)數(shù) K = 生產(chǎn)第一個(gè)產(chǎn)品所需的直接勞動(dòng)小時(shí)數(shù) n = lgb/lg X，其中 b 為學(xué)習(xí)比例 以上三條假設(shè)最初是從飛機(jī)制造過程中得到驗(yàn)證 的，也就是學(xué)習(xí)曲線最先被應(yīng)用在飛機(jī)制造業(yè)。在飛機(jī)制造過程中發(fā)現(xiàn)，每當(dāng)產(chǎn)量翻倍，用于制造飛機(jī)的時(shí)間就會(huì)減少 20%。也就是說，假設(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í)率。 學(xué)習(xí)曲線理論有兩種主要的模型：?jiǎn)挝划a(chǎn)品生產(chǎn)時(shí)間學(xué)習(xí)曲線和累計(jì)平均時(shí)間學(xué)習(xí)曲線。單位產(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í)間 不同的人或者組織或者工作，由于環(huán)境、方法、素質(zhì)等因素的差異，學(xué)習(xí)率會(huì)有不同。一般來說，對(duì)于簡(jiǎn)單的任務(wù)，傾向于采用 95%的學(xué)習(xí)率，中等復(fù)雜的任務(wù)采用 80%-90%的學(xué)習(xí)率，高復(fù)雜程度的任務(wù)傾向于使用 70%-80%的學(xué)習(xí)率。 2.3 單機(jī)排序問題 單機(jī)排序問題是最簡(jiǎn)單的一類排序問題，同時(shí)也是最重要的排序問題之一首先單機(jī)排序問題比較容易求出解決方法，這些方法對(duì)于研究比較復(fù)雜的排序問題具有指 導(dǎo)作用，可以為處理復(fù)雜排序問題提供近似算法 ；其次，單機(jī)排序問題大量存在于現(xiàn)實(shí)生活中，具有廣泛的實(shí)際背景，許多實(shí)際問題都可以歸結(jié)為單機(jī)排序問題。因此，單機(jī)排序問題對(duì)于有效地利用資源，提高生產(chǎn)效率，具有十分重要的指導(dǎo)意義。 2.3.1 加權(quán)總完工時(shí)間問題 西北工業(yè)大學(xué)明德學(xué)院本科畢業(yè)設(shè)計(jì)論文 15 單機(jī)排序問題的一個(gè)重要目標(biāo)函數(shù)是加權(quán)平均流時(shí)間。由于極小化加權(quán)平均流時(shí)間等價(jià)于極小化加權(quán)總完工時(shí)間，因此下面僅以加權(quán)總完工時(shí)間為目標(biāo)函數(shù)討論問題 .首先討論問題 1 (21) 其中是任務(wù)的完工時(shí)間，是賦予 任務(wù)的權(quán)，它表示的重要程度 .對(duì)于問題(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ī)則。 定理 2.1對(duì)于問題 (2.1),WSPT規(guī)則得到的是最優(yōu)排序。 證明假定某最優(yōu)排序 違反了 WSPT 規(guī)則，則在此排序中，至少有兩 個(gè)相鄰任務(wù)與 (在前 )，使 /( ) 與是最優(yōu)排序矛盾 .定理證畢。 2.4 數(shù)學(xué)規(guī)劃模型 下面給出問題 F2|=|的數(shù)學(xué)規(guī)劃模型。 目標(biāo)函數(shù) : 約束條件 : 西北工業(yè)大學(xué)明德學(xué)院本科畢業(yè)設(shè)計(jì)論文 16 i=1,2； r=1,2， n , r 1,2, ,n （ 2 5） ， r 1,2, ,n (2 6) (2 7) r 1,2, ,n； 0 式中 :j 為工件數(shù) ,j=1,2, ,n；i 為機(jī)器數(shù)， 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)說明在第 r個(gè)位置只有一個(gè)工件 ；約束 (3)說明每個(gè)工件只排在一個(gè)位置 ； 約束 (4)表示第 r個(gè)工件在機(jī)器上的實(shí)際加工時(shí)間 ； 約束 (5、 6、 7)分別表示第 r 個(gè)工件的開始時(shí)間、完工時(shí)間與空閑時(shí)間約束。所有的變量都是大于等于 0 且 Zjr 只能等于 1或 0。 決策變量： 1 如果工件 Jj排在第 r 個(gè)位置 = 0 否則 j,r=1,2,n 式 (1)中的與式 (4)中的表達(dá)的意思不同 ,式 (1)中的 表示在機(jī)器上的工件排在第 r個(gè)位置的實(shí)際加工時(shí)間 ；而式 (4)中的表達(dá)的是在機(jī)器上排在第 r個(gè)位置的實(shí)際加工時(shí)間。 2.5 啟發(fā)式算法 西北工業(yè)大學(xué)明德學(xué)院本科畢業(yè)設(shè)計(jì)論文 17 前面已把求 F2|=|的最優(yōu)解問題轉(zhuǎn)化為求解相應(yīng)的數(shù)學(xué)規(guī)劃模型 ,數(shù)學(xué)規(guī)劃問題通過數(shù)學(xué)軟件 Lingo 或 Lindo 進(jìn)行計(jì)算 ,得到最優(yōu)解 ,但是 ,數(shù)學(xué)規(guī)劃模型只能解決小規(guī)模問題 ,大規(guī)模問題運(yùn)行的時(shí)間過長(zhǎng) ,很難求到最優(yōu)解。 引理 1 對(duì)于問題 1 |=| ,SPT(把工件按非減順序排列 )規(guī)則產(chǎn)生最優(yōu)排序。 受單機(jī)排序問題的啟發(fā) (引理 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ì)步驟 : 2.5.1 啟發(fā)式算法 1 (1)把工件按 (表示工件在第 1臺(tái)機(jī)器上的加工時(shí)間 )非減 (SPT規(guī)則 )順序排列 ,即把工件按 排列得到的排序 ； (2)設(shè)由步驟 (1)得到的排序?yàn)?； (3)置 k=1； (4)置 i=k+1； (5)通過交換第 k 和第 i 個(gè)工件得到新的排序。如果排序的目標(biāo)函數(shù)值小于排序的目標(biāo)函數(shù)值 ,則用代替 ； (6)如果 i n,則置 i=i+1,轉(zhuǎn) (5)； (7)如果 k n-1,則置 k=k+1,轉(zhuǎn) (4)；否則 ,停止。 2.5.2 啟發(fā)式算法 2 (1)把工件按 (表示工件在第 2臺(tái)機(jī)器上的加工時(shí)間 )非減 (SPT規(guī)則 )順序排列 ,即 排列得到的排序 ； (2)設(shè)由步驟 (1)得到的排序?yàn)?； (3)置 k=1； (4)置 i=k+1； (5)通過交換第 k 和第 i 個(gè)工件得到新的排序。如果排序的目標(biāo)函數(shù)值小于排序的目標(biāo)函數(shù)值 ,則用代替 ； (6)如果 i n,則置 i=i+1,轉(zhuǎn) (5)； (7)如果 k n-1,則置 k=k+1,轉(zhuǎn) (4)；否則 ,停止。 2.5.3 啟發(fā)式算法 3 西北工業(yè)大學(xué)明德學(xué)院本科畢業(yè)設(shè)計(jì)論文 18 (1)把工件按 +非減 (SPT 規(guī)則 )順序規(guī)列 ,即 + + +排列得到的排序 ； (2)設(shè)由步驟 (1)得到的排序?yàn)?； (3)置 k=1； (4)置 i=k+1； (5)通過交換第 k 和第 i 個(gè)工件得到新的排序。如果排序的目標(biāo)函數(shù)值小于排序的目標(biāo)函數(shù)值 ,則用代替 ； (6)如果 in,則置 i=i+1,轉(zhuǎn) (5)； (7)如果 kn-1,則置 k=k+1,轉(zhuǎn) (4),否則 ,停止。 2.6 數(shù)值試驗(yàn) 2.6.1 基本假設(shè) （ 1）工件數(shù)為 5個(gè)，機(jī)器數(shù)為 2臺(tái) （ 2）假設(shè)第 1 臺(tái)機(jī)器上第 r 個(gè)工件的 完工時(shí)間和它在第 2 臺(tái)機(jī)器上的開始時(shí)間之差皆為 5min，即。 （ 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è)批次。 （ 4）假設(shè)學(xué)習(xí)因子 =0.9 （ 5）假設(shè)第二臺(tái)機(jī)器上第 r 個(gè)工件的開始時(shí)間與第 r-1 個(gè)工件的完工時(shí)間之間的空閑時(shí)間為 0，即。 2.6.2 數(shù)據(jù)模擬 對(duì)于問題 F2|=|，令 表示得到的最優(yōu)解 ,令表示按啟發(fā)式算法 1得到的排序 , ()表示用啟發(fā)式算法 1 得到的總完工時(shí)間。令表示按啟發(fā)式算 法 2 得到的排序 , ()表示用啟發(fā)式算法 2 的總完工時(shí)間。令表示按啟發(fā)式算法 3 得到的排序 , Cj()表示用啟發(fā)式算法 3排序得到的總完工時(shí)間。 由以上假設(shè)我們可以得到 |=| 代入數(shù)據(jù)后可知： 目標(biāo)函數(shù)： 根據(jù) 2.4數(shù)學(xué)規(guī)劃模型我們可得出： 西北工業(yè)大學(xué)明德學(xué)院本科畢業(yè)設(shè)計(jì)論文 19 即第一種工件的五個(gè)批次的完工時(shí)間分別為 4,3.6,3.24,2.92,2.62min。那么第一種工件五個(gè)批次的總完工時(shí)間為 18.74min。即 。 以此類推可知， ， r 1,2, ,5 則 目 標(biāo) 函 數(shù) 西北工業(yè)大學(xué)明德學(xué)院本科畢業(yè)設(shè)計(jì)論文 20 第三章 流水線作業(yè)排序模型仿真 3.1 仿真軟件介紹 Lekin一款很好的生產(chǎn)運(yùn)作管理研究與教學(xué)軟件，可以快速建立單機(jī)，流水，柔性流水車間，作業(yè)車間等模型。包含許多調(diào)度算法和啟發(fā)式算法。 3.2 Liken 仿真軟件算法介紹 3.2.1 EDD 算法規(guī)則 最早交期法則（ EDD）：最大延誤時(shí)間最小化。交期越早者排越前面。 1955年 Jackson提出 EDD（ Early Due Date）派工法則其應(yīng)用在最小化最大延誤時(shí)間和最大延遲時(shí)間，但是此法會(huì)有增加延遲工作數(shù)目和增加平均延遲時(shí)間的傾向。 3.2.2 加權(quán)最短作業(yè)時(shí)間法則（ WSPT） 最小化平均加權(quán)流程時(shí)間。將作業(yè)時(shí)間除以權(quán)重所得之值越小者排越前面。 當(dāng)工作附有重要性的屬性時(shí)，排序人員可給予個(gè)別的權(quán)重權(quán)重值越大表示重要性越大。 WSPT 法則即是將作業(yè)時(shí)間除以權(quán)重所得的值越小者表示越重要的工作，而它將排至順序的第一位，以此類推。加權(quán)平均流程時(shí)間的計(jì)算方法為： 3.2.3 SPT 算法規(guī)則 最短作業(yè)時(shí)間法則 (SPT) ： 最小化平均流程時(shí)間。 job作業(yè)時(shí)間越小者排越西北工業(yè)大學(xué)明德學(xué)院本科畢業(yè)設(shè)計(jì)論文 21 前面，亦可以使平均延誤時(shí)間，平均等候時(shí)間最小化。 最短作業(yè)時(shí)間法則 最小化平均流程時(shí)間 當(dāng) n 個(gè)作業(yè)要排至單一機(jī)臺(tái)上時(shí)，利用 SPT (Shortest Process Time) 法則排序可使得平均流程時(shí)間最小化，也就是。 范例 3.1 給予一組工作集如下表所示，目標(biāo)為最小化平均流程時(shí)間 表 3.1 工作 i 作業(yè)時(shí)間 ti 1 4 2 8 3 7 4 3 5 10 6 12 7 6 8 5 依 SPT派工法則排序，順序?yàn)?4-1-8-7-3-2-5-6。其流程時(shí)間計(jì)算如下表 表 3.2 工作 i 流程時(shí)間 ti 4 3 1 3+4 8 3+4+5 7 3+4+5+6 3 3+4+5+6+7 2 3+4+5+6+7+8 5 3+4+5+6+7+8+10 6 3+4+5+6+7+8+10+12 西北工業(yè)大學(xué)明德學(xué)院本科畢業(yè)設(shè)計(jì)論文 22 所以平均流程時(shí)間為 由以上可知工作流程時(shí)間的計(jì)算方式為 除了最小化平均流程時(shí)間以外，在單機(jī)排序問題中 SPT法則亦可以最小化平均延誤時(shí)間、最小化平均等候時(shí)間。 3.3 仿真 3.3.1 仿真前提條件 （ 1）工件數(shù)為 5個(gè)，機(jī)器數(shù)為 2臺(tái) （ 2）假設(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è)批次。 （ 3）假設(shè)學(xué)習(xí)因子 =0.9 （ 4）假 設(shè)第 1 臺(tái)機(jī)器上第 r 個(gè)工件的完工時(shí)間和它在第 2 臺(tái)機(jī)器上的開始時(shí)間之差皆為 5min，即。 （ 5）假設(shè) 5個(gè)作業(yè)的優(yōu)先級(jí)都為 1。 3.3.2 仿真計(jì)算 利用車間排序軟件 Lekin，設(shè)置參數(shù)如下圖： （ 1）如圖 3.1 與圖 3.2，進(jìn)入 lekin 軟件后，點(diǎn)擊如圖中的 Flow。并設(shè)置兩臺(tái)機(jī)器，五個(gè)作業(yè)，點(diǎn)擊 OK。 西北工業(yè)大學(xué)明德學(xué)院本科畢業(yè)設(shè)計(jì)論文 23 圖 3.1 圖 3.2 （ 2）圖 3.3與圖 3.4 為對(duì)機(jī)器和進(jìn)行參數(shù)設(shè)置。 圖 3.3 圖 3.4 （ 3）圖 3.5與圖 3.6 為對(duì)工作 1進(jìn)行的各種參數(shù)設(shè)置。 西北工業(yè)大學(xué)明德學(xué)院本科畢業(yè)設(shè)計(jì)論文 24 圖 3.5 圖 3.6 （ 4）圖 3.7與圖 3.8 為對(duì)工作 2進(jìn)行的各種參數(shù)設(shè)置。 圖 3.7 圖 3.8 （ 5）圖 3.9與圖 3.10 為對(duì)工作 3進(jìn)行的各種參數(shù)設(shè)置。 圖 3.9 圖 3.10 （ 6）圖 3.11與圖 3.12為對(duì)工作 4進(jìn)行的各種參數(shù)設(shè)置。 西北工業(yè)大學(xué)明德學(xué)院本科畢業(yè)設(shè)計(jì)論文 25 圖 3.11 圖 3.12 （ 7）圖 3.13與圖 3.14為對(duì)工作 5進(jìn)行的各種參數(shù)設(shè)置。 圖 3.13 圖 3.14 （ 8）下圖為兩 臺(tái)機(jī)床，五個(gè)作業(yè)由的排序圖。 西北工業(yè)大學(xué)明德學(xué)院本科畢業(yè)設(shè)計(jì)論文 26 圖 3.15 （ 9）以下為經(jīng)過 Lekin 軟件 SPT排序所得結(jié)果。 圖 3.16 圖 3.17 西北工業(yè)大學(xué)明德學(xué)院本科畢業(yè)設(shè)計(jì)論文 27 圖 3.18 從圖 3.17，我們可以看出，各自對(duì)應(yīng)黃色，淺藍(lán)，紫色，綠色，灰色。由此與圖 3.16做對(duì)比，可知由 最短作業(yè)時(shí)間法則 (SPT)所 得的排序?yàn)?。 第四章 仿真分析與算法優(yōu)化 4.1 車間作業(yè)排序問題仿真優(yōu)化系統(tǒng)的構(gòu)建思想、方法與框架 傳統(tǒng)的仿真優(yōu)化集成思想如圖 4.1所示。對(duì)系統(tǒng)建立仿真模型 ,將仿真輸出信息作為優(yōu)化器的輸入 ,對(duì)仿真輸出進(jìn)行分析與評(píng)價(jià)后 ,得出新的系統(tǒng)參數(shù)或決策變量再作為仿真模型的新輸入 ,以上過程不斷重復(fù) ,直至滿足一定的停止規(guī)則。這種思想實(shí)現(xiàn)了優(yōu)化算法與仿真的外部集成 ,提高了對(duì)問題的建模能力和靈活性。 輸入（決策變量） 輸出（性能指標(biāo)） 仿真模型 西北工業(yè)大學(xué)明德學(xué)院本科畢業(yè)設(shè)計(jì)論文 28 輸出（優(yōu)化解） 輸入（優(yōu)化參數(shù)） 圖 4.1 4.2 算法優(yōu)化 為了分析啟發(fā)式算法的好壞 ,通過與最優(yōu)解之間的平均誤差和最大誤差的比較 ,得到啟發(fā)式算法的好壞。按啟發(fā)式算法 1 得到排序的相對(duì)誤差 平均誤差 其中 ,10 表示對(duì)每個(gè)問題取 10 組實(shí)例進(jìn)行計(jì)算 ,最大誤差 R1 為相對(duì)誤差中最大的誤差 ； 按啟發(fā)式算法 2 得到排序的相對(duì)誤差 平均誤差 最大誤差為相對(duì)誤差中最大的誤差 ；按啟發(fā)式算法 3得到排序的相對(duì)誤差 平均誤差 最大誤差為相對(duì)誤差中最大的誤差。 通過 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)解的平均誤差和最大誤差。從數(shù)據(jù)轉(zhuǎn)換 優(yōu)化算法 數(shù)據(jù)轉(zhuǎn)換 西北工業(yè)大學(xué)明德學(xué)院本科畢業(yè)設(shè)計(jì)論文 29 計(jì)算的結(jié)果我們是可以得到一個(gè)相應(yīng)的結(jié)論的，即 3個(gè)啟發(fā)式算法之間沒有明顯的好壞 ,對(duì)于參數(shù) =0.1,所求之解更加接近最優(yōu)解 ,且大部分會(huì)產(chǎn)生最優(yōu)的排序。 第四章 總結(jié)與展望 5.1 論文總結(jié) 2014年 3月，我開始了我的畢業(yè)論文工作，時(shí)至今日，論文基本完成。從最初的茫然，到慢慢的進(jìn)入狀態(tài)，再到對(duì)思路逐漸的清晰，整個(gè)寫作過程難以用語(yǔ)言來表達(dá)。歷經(jīng)了幾個(gè)月的奮戰(zhàn)，緊張而又充實(shí)的畢業(yè)設(shè)計(jì) 終于落下了帷幕?；叵脒@段日子的經(jīng)歷和感受，我感慨萬千，在這次畢業(yè)設(shè)計(jì)的過程中，我擁有了無數(shù)難忘的回憶和收獲。 在 整個(gè)設(shè)計(jì)過程 中遇到困難我就及時(shí)和導(dǎo)師聯(lián)系，并和同學(xué)互相交流，請(qǐng)教專業(yè)課老師。在大家的幫助下，困難一個(gè)一個(gè)解決掉，論文也慢慢成型。 當(dāng)我終于完成了所有打字、 編算法 、排版、校對(duì) 等 任務(wù)后整個(gè)人都很累，但同時(shí)看著電腦熒屏上的畢業(yè)設(shè)計(jì)稿件我的心里是甜的，我覺得這一切都值了。這次畢業(yè)論文的制作過程是我的一次再學(xué)習(xí)，再提高的過程。在論文中我充分地運(yùn)用了大學(xué)期間所學(xué)到的知識(shí)。 西北工業(yè)大學(xué)明德學(xué)院本科畢業(yè)設(shè)計(jì)論文 30 我不會(huì)忘記這難忘的幾 個(gè)月的時(shí)間。畢業(yè)論文的制作給了我難忘的回憶。在整個(gè)過程中，我學(xué)到了新知識(shí)，增長(zhǎng)了見識(shí)。在今后的日子里，我仍然要不斷地充實(shí)自己，爭(zhēng)取在所學(xué)領(lǐng)域有所作為。 腳踏實(shí)地，認(rèn)真嚴(yán)謹(jǐn)，實(shí)事求是的學(xué)習(xí)態(tài)度，不怕困難、堅(jiān)持不懈、吃苦耐勞的精神是我在這次設(shè)計(jì)中最大的收益。我想這是一次意志的磨練，是對(duì)我實(shí)際能力的一次提升，也會(huì)對(duì)我未來的學(xué)習(xí)和工作有很大的幫助。 通過這一學(xué)期的畢業(yè)設(shè)計(jì)，我對(duì)流水線排序問題有了一個(gè)基本的了解和掌握，但是每一種排序算法根據(jù)其實(shí)際生產(chǎn)線的要求卻又是各有不同的，所以我在今后的工作和學(xué)習(xí)中將會(huì)繼續(xù)努力學(xué)習(xí) ，了解與應(yīng)用各種流水線排序算法仿真軟件，結(jié)合自己大學(xué)以來學(xué)習(xí)的各種加工軟件，我相信在以后的工作中一定能有很大的幫助。 5.2 后續(xù)與展望 此次畢業(yè)設(shè)計(jì)在此就將有一個(gè)階段性的成果，但是在此過程中，自己還是有很多的不足之處，專業(yè)知識(shí)有很強(qiáng)烈的匱乏感，這都源于知識(shí)面不夠廣闊，未能深刻鉆研專業(yè)相關(guān)的知識(shí)，針對(duì)這次的畢業(yè)設(shè)計(jì)，我認(rèn)為還有必要進(jìn)一步進(jìn)行完善工作。 流水線排序軟件如 Lekin、 Arena 等是一款很好的流水線排序軟件，雖然在畢業(yè)設(shè)計(jì)階段對(duì)此軟件有所學(xué)習(xí)，但我感覺操作還是生疏，需要投入更多的精力在此項(xiàng)學(xué)習(xí)。 在實(shí)際生產(chǎn)中，排序問題影響因素眾多我們能想到的如各種機(jī)器故障，所用機(jī)床的實(shí)際效能，車間流水線加工的學(xué)習(xí)效應(yīng)，工件的特殊性等等都可使排序問題變得復(fù)雜，我們應(yīng)盡可能地減少或避免它們。 另外， 因時(shí)間的關(guān)系，我對(duì)很多參數(shù)了解很膚淺，排序算法軟件中的參 數(shù)較多，尤其一些功用繁多的算法軟件，這些參數(shù)的意義都非常重要，應(yīng)在今后的工作中重點(diǎn)掌握。 西北工業(yè)大學(xué)明德學(xué)院本科畢業(yè)設(shè)計(jì)論文 31 致 謝 在此論文撰寫過程中，要特別感謝我的導(dǎo)師王劍老師，沒有她的幫助也就沒有今天的這篇論文。求學(xué)歷程是艱苦的，但是有時(shí)快樂 的。在這個(gè)過程中，王老師一直嚴(yán)格要求我，督促著我們，針對(duì)同學(xué)們提出的一些問題，總能夠提出針對(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ì)幫助過我的老師和同學(xué)們表達(dá)由衷的謝意，感謝大家四年以來對(duì)我的幫助與照顧！同時(shí)，我還要感謝我所在的大學(xué) 西北工業(yè)大學(xué)明德學(xué)院，是她為我提供了舒適的生活條件及良好的學(xué)習(xí)環(huán)境 。本文參考了大量的文獻(xiàn)資料，在此，向?qū)W術(shù)界的前輩們致敬！ 西北工業(yè)大學(xué)明德學(xué)院本科畢業(yè)設(shè)計(jì)論文 32 參考文獻(xiàn) 1 Badiru A B.Computational survey of univariate and multivariate learning curve modelsJ.IEEE transactions on Engineering Management 1992；39(2):176-188. 2BiskupD.Single-machine scheduling with learning considerations J.European Journal of Operational Research 1999；115(1):173-178. 3 Cheng T C E,Wang G.Single machine scheduling with learning effect considerationsJ.