《平行機(jī)排序問(wèn)題》PPT課件.ppt

上傳人:xin****828 文檔編號(hào):15539736 上傳時(shí)間:2020-08-19 格式:PPT 頁(yè)數(shù):24 大?。?45.50KB
收藏 版權(quán)申訴 舉報(bào) 下載
《平行機(jī)排序問(wèn)題》PPT課件.ppt_第1頁(yè)
第1頁(yè) / 共24頁(yè)
《平行機(jī)排序問(wèn)題》PPT課件.ppt_第2頁(yè)
第2頁(yè) / 共24頁(yè)
《平行機(jī)排序問(wèn)題》PPT課件.ppt_第3頁(yè)
第3頁(yè) / 共24頁(yè)

下載文檔到電腦,查找使用更方便

9.9 積分

下載資源

還剩頁(yè)未讀,繼續(xù)閱讀

資源描述:

《《平行機(jī)排序問(wèn)題》PPT課件.ppt》由會(huì)員分享,可在線閱讀,更多相關(guān)《《平行機(jī)排序問(wèn)題》PPT課件.ppt(24頁(yè)珍藏版)》請(qǐng)?jiān)谘b配圖網(wǎng)上搜索。

1、平行機(jī)排序問(wèn)題 Parallel Machine Scheduling,平行機(jī)排序問(wèn)題,有多份文件需安排給幾個(gè)打字員打印,若每個(gè) 打字員的打字速度相同,應(yīng)該如何安排使得這 些文件在最短時(shí)間內(nèi)完成。,問(wèn)題描述,設(shè)有m臺(tái)完全相同的機(jī)器 , n個(gè)互相獨(dú)立的工 件 ,每個(gè)工件只需在一臺(tái)機(jī)器上不中斷的加工 一次,并設(shè)m

2、我們想要的目標(biāo)函數(shù)為 ,它表示所有的工件加工工 作在最短時(shí)間內(nèi)完成。若記 為機(jī)器 所要加工的所有 工件所需的總的時(shí)間,那么顯然有 。 討論這種所需加工時(shí)間最小的平行機(jī)排序問(wèn)題也稱(chēng)為使時(shí) 間跨度最小的平行機(jī)排序問(wèn)題。,,,,,,,,整數(shù)線性規(guī)劃(PMS),,,,說(shuō)明,整數(shù)線性規(guī)劃的解中不能說(shuō)明次序,但是由于平行機(jī)排序 問(wèn)題中,每臺(tái)機(jī)器加工的總時(shí)間不受這臺(tái)機(jī)器的加工次序 影響,所以這個(gè)整數(shù)線性規(guī)劃的最優(yōu)解即也就給出了最優(yōu) 排序.,平行機(jī)排序問(wèn)題與裝箱問(wèn)題,這兩個(gè)問(wèn)題成為對(duì)偶問(wèn)題。把這兩個(gè)問(wèn)題中的箱子和機(jī)器 對(duì)應(yīng),物品與工件對(duì)應(yīng)。那么裝箱問(wèn)題就是箱子長(zhǎng)度固 定,目標(biāo)是使箱子數(shù)最?。欢叫?/p>

3、機(jī)排序問(wèn)題是箱子數(shù)固 定,目標(biāo)是使得箱子長(zhǎng)度最短。,平行機(jī)排序問(wèn)題最優(yōu)解的下界,定理:最優(yōu)解值的一個(gè)下界為 。,,近似算法,LS算法(List Scheduling) LPT算法(Largest Processing Time) Multifit算法 多項(xiàng)式時(shí)間近似方案,,LS算法,將每一個(gè)工件分給最早空閑的機(jī)器。 為在線算法,時(shí)間復(fù)雜度 。,,算法描述,,,絕對(duì)性能比,定理: 。,,實(shí)例,5臺(tái)相同機(jī)器,20個(gè)工件,加工時(shí)間分別為 10,13,15,8,5,9,21,17,12,7, 11,3,6,16,23,22,4,19,26,31,LPT算法,先將物品按照

4、加工時(shí)間從大到小排序,然后按照LS算法排 序。 此算法為離線算法,時(shí)間復(fù)雜度,,絕對(duì)性能比,定理: 。,,實(shí)例,5臺(tái)相同機(jī)器,20個(gè)工件,加工時(shí)間分別為 10,13,15,8,5,9,21,17,12,7, 11,3,6,16,23,22,4,19,26,31,Multifit算法,將m臺(tái)機(jī)器看成m個(gè)箱子,n個(gè)工件看成有長(zhǎng)度的物 品,其長(zhǎng)度為該工件在機(jī)器上所需的加工時(shí)間。 先確定箱子容量的上下界 ,然后用FFD算法 判斷是否能將所有物品放入容量為 的m個(gè) 箱子中,以調(diào)整上下界,迭代k次后以上界作為輸出。,,,算法描述,該算法初始上界為CU取LPT算法所得到的解值,初始

5、下界 為CL.,,絕對(duì)性能比,定理:當(dāng)Multifit算法中FFD算法迭代了k次,則對(duì)任意實(shí) 例I , 且常數(shù)部分 不可改進(jìn),即 。,,,,實(shí)例,5臺(tái)相同機(jī)器,20個(gè)工件,加工時(shí)間分別為 10,13,15,8,5,9,21,17,12,7, 11,3,6,16,23,22,4,19,26,31 迭代2次,多項(xiàng)式時(shí)間近似方案,取出mk個(gè)加工時(shí)間最長(zhǎng)的工件,若mkn,則取出所有工件。 對(duì)取出的所有工件用枚舉法求出最優(yōu)排序。 由得到的mk個(gè)工件最優(yōu)排序出發(fā),將剩下的n-mk個(gè)工件用LS算法,安排它們的加工。,,絕對(duì)性能比、時(shí)間復(fù)雜性,定理 : , 的時(shí)間復(fù)雜性為,,,,實(shí)例,5臺(tái)相同機(jī)器,20個(gè)工件,加工時(shí)間分別為 10,13,15,8,5,9,21,17,12,7, 11,3,6,16,23,22,4,19,26,31 取k=2,練習(xí),6臺(tái)相同機(jī)器,25個(gè)工件,加工時(shí)間分別為 10,13,15,27,18,8,5,9,21, 17,12,7,11,3,6,16,23,22,4, 19,26,31,1,2,9 分別用LS算法,LPT算法, Multifit算法 (迭 代3次), 算法(取k=3)進(jìn)行排序,,

展開(kāi)閱讀全文
溫馨提示:
1: 本站所有資源如無(wú)特殊說(shuō)明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請(qǐng)下載最新的WinRAR軟件解壓。
2: 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請(qǐng)聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
3.本站RAR壓縮包中若帶圖紙,網(wǎng)頁(yè)內(nèi)容里面會(huì)有圖紙預(yù)覽,若沒(méi)有圖紙預(yù)覽就沒(méi)有圖紙。
4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
5. 裝配圖網(wǎng)僅提供信息存儲(chǔ)空間,僅對(duì)用戶上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理,對(duì)用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對(duì)任何下載內(nèi)容負(fù)責(zé)。
6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請(qǐng)與我們聯(lián)系,我們立即糾正。
7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時(shí)也不承擔(dān)用戶因使用這些下載資源對(duì)自己和他人造成任何形式的傷害或損失。

最新文檔

相關(guān)資源

更多
正為您匹配相似的精品文檔
關(guān)于我們 - 網(wǎng)站聲明 - 網(wǎng)站地圖 - 資源地圖 - 友情鏈接 - 網(wǎng)站客服 - 聯(lián)系我們

copyright@ 2023-2025  zhuangpeitu.com 裝配圖網(wǎng)版權(quán)所有   聯(lián)系電話:18123376007

備案號(hào):ICP2024067431號(hào)-1 川公網(wǎng)安備51140202000466號(hào)


本站為文檔C2C交易模式,即用戶上傳的文檔直接被用戶下載,本站只是中間服務(wù)平臺(tái),本站所有文檔下載所得的收益歸上傳人(含作者)所有。裝配圖網(wǎng)僅提供信息存儲(chǔ)空間,僅對(duì)用戶上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理,對(duì)上載內(nèi)容本身不做任何修改或編輯。若文檔所含內(nèi)容侵犯了您的版權(quán)或隱私,請(qǐng)立即通知裝配圖網(wǎng),我們立即給予刪除!

五月丁香婷婷狠狠色,亚洲日韩欧美精品久久久不卡,欧美日韩国产黄片三级,手机在线观看成人国产亚洲