具有學習效應(yīng)的總完工時間流水線排序問題與仿真答辯稿

具有學習效應(yīng)的總完工時間流水線排序與仿真 導(dǎo)師： 班級： 學號： 姓名： （一） 排序問題 排序問題的定義： 排序 (scheduling)問題是一類重要的組合最優(yōu)化問題，它是利用一些處理機 (processor)、機器(machine)或資源 ( resource )，最優(yōu)地完成一批給定的任務(wù) (task)或作業(yè) (job)。 第一章 緒論 （二） 排序問題的分類 1.根據(jù)處理機的數(shù)量 處理機只有一個處理機的排序問題稱為單 (處理 )機 (single processor, single machine)排序問題，否則稱為多 (處理 )機排序問題。 2.根據(jù)處理機的功能 如果所有的處理機都具有相同的功能，稱它們?yōu)橥悪C或平行機。同類機亦有同速機、恒速機、變速機之分。 3.根據(jù)加工順序的特征 （ 1） 如果每個作業(yè)需要在每個處理機上加工，而且每個作業(yè)的工序也相同，這種多類機的環(huán)境稱為同順序作業(yè)或流水作業(yè) (flow shop)。 （ 2） 如果每個作業(yè)需要在每個處理機上加工，每個作業(yè)有自己的加工順序，稱之為異順序作業(yè) (job shop) （ 3）如果每個作業(yè)需要在每個處理機上加工，每個作業(yè)可按任意順序加工，把它稱為自由順序作業(yè)或開放作業(yè) (open shop ) 。 (4)柔性流水線 例 1.1 給定排序問題 1| | 其中 n=4, P=(3，2， 5， i)， r=(0， 1， 0， 0) ， ， ， 是一個可行排序，對應(yīng)的總加工時間是 31, ， ， ， 是一個最優(yōu)排序，最優(yōu)總加工時間是 21。 jr jC1P34P24P2P1P3符號說明 第二章 具有學習效應(yīng)的總完工時間流水線排序 2.1 問題描述 2.2學習效應(yīng)的概念 2.3 單機排序問題 2.4數(shù)學規(guī)劃模型 2.5 啟發(fā)式算法 2.6 數(shù)值試驗 2.1 問題描述 n個工件依次在機器 M1、 M2上加工。在每個機器上的加工順序相同 ,其實際加工時間為 ，公式可表示為： 對于 2臺機器上具有指數(shù)學習效應(yīng)的最大完工時間的流水作業(yè)問題 ,用三參數(shù)表示法表示為 ijP2.學習效應(yīng) 學習曲線方程的一般形式是 : Yx=K（ n為 X的指數(shù)） 式中 : X =單位數(shù)量 = 生產(chǎn)第 X個產(chǎn)品所需的直接勞動小時數(shù) K = 生產(chǎn)第一個產(chǎn)品所需的直接勞動小時數(shù) n = lgb/lg X，其中 b 為學習比例 2.4 數(shù)學規(guī)劃模型 2.6 數(shù)值試驗 1. 基本假設(shè) （ 1）工件數(shù)為 5個，機器數(shù)為 2臺 （ 2）假設(shè)第 1臺機器上第 r個工件的完工時間和它在第2臺機器上的開始時間之差皆為 5min。 （ 3）假設(shè) 5個不同工件在第一臺機器每一個批次的實際加工時間分別為 4,6,7,5,9。在第二臺機器實際加工時間分別為 7,11,10,9,6。另外，每種工件各有 5個批次。 （ 4）假設(shè)學習因子 =0.9 （ 5）假設(shè)第二臺機器上第 r個工件的開始時間與第 r-1個工件的完工時間之間的空閑時間為 0 第三章 流水線作業(yè)排序模型仿真 SPT算法規(guī)則 最短作業(yè)時間法則 (SPT) ：最小化平均流程時間。 job作業(yè)時間越小者排越前面，亦可以使平均延誤時間，平均等候時間最小化。 致 謝 : 經(jīng)過幾周的奮戰(zhàn)我的畢業(yè)設(shè)計終于完成了。在我還沒有做畢業(yè)設(shè)計以前覺得畢業(yè)設(shè)計只是對這幾年來所學知識的單純性的總結(jié)，但是通過這次做畢業(yè)設(shè)計發(fā)現(xiàn)自己的看法有點太片面和簡單了。通過這次畢業(yè)設(shè)計使我明白了自己原來的知識還是比較欠缺。自己要學習的東西還太多太多，以前總是覺得自己什么東西都會，什么東西都懂，有點眼高手低。通過這次畢業(yè)設(shè)計的收集編制等等，我才明白學習是一個長期積累的過程，在以后的工作和生活當中我們都應(yīng)該不斷的努力學習，努力的去提高自己