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

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