本文關(guān)鍵詞：若干調(diào)度問題的算法研究　出處：《大連理工大學(xué)》2016年博士論文　論文類型：學(xué)位論文

  更多相關(guān)文章： 在線算法 流水調(diào)度 啟發(fā)式算法

【摘要】：調(diào)度問題是組合最優(yōu)化領(lǐng)域和理論計(jì)算機(jī)科學(xué)領(lǐng)域中的一個(gè)重要分支,主要研究將稀缺資源分配給在一定時(shí)間內(nèi)不同任務(wù)的問題,分配過程也可以理解為一個(gè)決策過程。做決策目的是優(yōu)化一個(gè)或者多個(gè)目標(biāo),有單機(jī)調(diào)度,也有多機(jī)調(diào)度。從輸入信息的實(shí)時(shí)性來看,調(diào)度(排序)問題可以被分為離線、在線和半在線三類；從輸出結(jié)果的精確角度來看,調(diào)度問題的算法可被分為精確算法,近似算法(包含啟發(fā)式算法)。調(diào)度問題在實(shí)際生活中一直都有廣泛應(yīng)用,比如計(jì)算機(jī)領(lǐng)域的節(jié)能調(diào)度,負(fù)載平衡調(diào)度,作業(yè)調(diào)度,醫(yī)院中護(hù)士排班調(diào)度,運(yùn)輸中的動(dòng)態(tài)車輛調(diào)度,生產(chǎn)線上的流水調(diào)度,飛機(jī)的航班調(diào)度,鋼鐵生產(chǎn)過程中的批作業(yè)調(diào)度和流水調(diào)度等等,因此調(diào)度問題一直被人們所廣泛關(guān)注,并且是很多學(xué)者的研究課題。本文分別研究了帶緩沖在線平行機(jī)調(diào)度、單機(jī)在線調(diào)度、帶運(yùn)輸時(shí)間的流水調(diào)度和離線平行機(jī)調(diào)度等問題。(1)帶緩沖在線平行機(jī)調(diào)度：文中給出了三個(gè)在線算法,并給出算法的競(jìng)爭(zhēng)比分析,改進(jìn)了已有的研究成果。文中提出了一個(gè)在線算法并證明了在同型機(jī)的數(shù)量m51,緩沖區(qū)大小為[1.5m]的情況,該算法競(jìng)爭(zhēng)比為1.5；此外還提出在同型機(jī)數(shù)量為3的情況只需要6個(gè)緩沖區(qū)的最優(yōu)的在線算法,改進(jìn)了之前需要9個(gè)緩沖區(qū)的最優(yōu)在線算法；文中還證明了在同類機(jī)的數(shù)量和緩沖區(qū)的均為m時(shí),將競(jìng)爭(zhēng)比從2+ε提升到2-1/m+ε,其中m是常數(shù)即機(jī)器的數(shù)量,ε0且足夠小(2)單機(jī)在線調(diào)度：文中研究了單機(jī)調(diào)度下帶有截至期限的搶占-重啟模型,在已知的WAL算法中基礎(chǔ)上提出了一個(gè)傳統(tǒng)啟發(fā)式算法D-WAL算法,其思想就是同時(shí)關(guān)注任務(wù)和作業(yè)的收益大小,分析實(shí)驗(yàn)結(jié)果顯示D-WAL算法在性能上比只關(guān)注收益大小的WAL算法要好。(3)帶運(yùn)輸時(shí)間流水調(diào)度：文中考慮了一種特殊情況即所有的工件在機(jī)器B上加工時(shí)間都相同的時(shí)候,針對(duì)該種特殊情況可以發(fā)現(xiàn)：存在一個(gè)最優(yōu)調(diào)度使得每個(gè)工件在機(jī)器A上的加工時(shí)間是非遞減的,而且工件執(zhí)行順序在機(jī)器A上的順序和在機(jī)器B和運(yùn)輸機(jī)V是一樣的。利用這個(gè)性質(zhì),文中給出了多項(xiàng)式時(shí)間的最優(yōu)調(diào)度算法以及相應(yīng)的證明。(4)離線平行機(jī)調(diào)度：本文基于經(jīng)典的粒子群算法,結(jié)合Levy飛行方法優(yōu)化粒子群算法,提出了LPSO算法。分析實(shí)驗(yàn)結(jié)果發(fā)現(xiàn)Levy飛行方法可以使PSO算法本身容易陷入早熟的劣勢(shì)得到很顯著的緩解,并且同時(shí)充分發(fā)揮了PSO算法的簡(jiǎn)便快捷特性。
[Abstract]:......
【學(xué)位授予單位】：大連理工大學(xué)
【學(xué)位級(jí)別】：博士
【學(xué)位授予年份】：2016
【分類號(hào)】：TP301.6

【相似文獻(xiàn)】

相關(guān)期刊論文 前10條

1 劉文濤,張群,孫肅清;關(guān)于煉鋼廠重調(diào)度問題的研究[J];冶金自動(dòng)化;2004年06期

2 張居陽 ,禮欣 ,孫吉貴;基于約束的調(diào)度研究和實(shí)現(xiàn)[J];計(jì)算機(jī)工程與應(yīng)用;2004年33期

3 劉琳;谷寒雨;席裕庚;;工件到達(dá)時(shí)間未知的動(dòng)態(tài)車間滾動(dòng)重調(diào)度[J];機(jī)械工程學(xué)報(bào);2008年05期

4 黃峰;丁亞武;;人機(jī)協(xié)同模式下的手工調(diào)度技術(shù)研究[J];黑龍江科技信息;2011年35期

5 郭艷東;黃敏;王慶;;鎖定初始調(diào)度的緊急工作單機(jī)重調(diào)度問題[J];東北大學(xué)學(xué)報(bào)(自然科學(xué)版);2013年05期

6 姜洋;孫偉;丁秋雷;張旭;;考慮行為主體的單機(jī)調(diào)度干擾管理模型[J];機(jī)械工程學(xué)報(bào);2013年14期

7 李向軍,王書振;網(wǎng)絡(luò)化集成制造模式下調(diào)度問題的混合遺傳算法[J];西安聯(lián)合大學(xué)學(xué)報(bào);2002年04期

8 王中杰,吳啟迪,有杰;基于多目標(biāo)的半導(dǎo)體生產(chǎn)線滿意調(diào)度[J];控制與決策;2002年06期

9 李云峰;凌曉冬;武小悅;;調(diào)度問題中的沖突研究[J];兵工自動(dòng)化;2007年06期

10 徐群嶺;;基于免疫優(yōu)化的公交駕駛員調(diào)度問題[J];計(jì)算機(jī)工程;2010年24期

相關(guān)會(huì)議論文 前10條

1 李建更;涂凍生;馬海濤;;單機(jī)拖后時(shí)間總和問題交付期擾動(dòng)時(shí)最優(yōu)調(diào)度不變范圍的一種求法[A];第十九屆中國控制會(huì)議論文集（一）[C];2000年

2 劉海龍;黃小原;;總的未完工費(fèi)用最小的多機(jī)調(diào)度問題[A];1995中國控制與決策學(xué)術(shù)年會(huì)論文集[C];1995年

3 沈吟東;曾西洋;;公共交通駕駛員調(diào)度的復(fù)雜性及解決方法[A];’2004計(jì)算機(jī)應(yīng)用技術(shù)交流會(huì)議論文集[C];2004年

4 李兵;蔣慰孫;;Job shop問題的建模及調(diào)度[A];1996中國控制與決策學(xué)術(shù)年會(huì)論文集[C];1996年

5 王海星;申金升;;智能蟻群算法解決公交區(qū)域調(diào)度問題研究[A];2006年首屆ICT大會(huì)信息、知識(shí)、智能及其轉(zhuǎn)換理論第一次高峰論壇會(huì)議論文集[C];2006年

6 王成堯;汪定偉;;模糊加工時(shí)間的單機(jī)調(diào)度問題[A];1996中國控制與決策學(xué)術(shù)年會(huì)論文集[C];1996年

7 齊向彤;涂奉生;;雙交付期E／T調(diào)度問題[A];1997年中國控制會(huì)議論文集[C];1997年

8 吳斌;方葉祥;崔志勇;;基于人工蜂群算法的越庫調(diào)度問題研究[A];第25屆中國控制與決策會(huì)議論文集[C];2013年

9 方濤;吳受章;;FMS的自適應(yīng)調(diào)度:結(jié)構(gòu)與算法研究[A];1992年中國控制與決策學(xué)術(shù)年會(huì)論文集[C];1992年

10 劉興初;趙千川;鄭大鐘;;具有不同準(zhǔn)備時(shí)間和交付期的單機(jī)E／T調(diào)度問題研究[A];1998年中國控制會(huì)議論文集[C];1998年

相關(guān)重要報(bào)紙文章 前2條

1 本報(bào)記者 賈科華;火電機(jī)組叫苦調(diào)度不合理[N];中國能源報(bào);2012年

2 本報(bào)記者 高芳;牽住“牛鼻子” 巧解“推進(jìn)難”[N];湖南經(jīng)濟(jì)報(bào);2008年

相關(guān)博士學(xué)位論文 前10條

1 郭鵬;具有分段惡化效應(yīng)生產(chǎn)過程的智能優(yōu)化調(diào)度研究[D];西南交通大學(xué);2014年

2 元野;基于圖著色模型的零擔(dān)物流調(diào)度優(yōu)化問題研究[D];哈爾濱工業(yè)大學(xué);2015年

3 李雪松;模糊環(huán)境下若干單機(jī)批加工調(diào)度問題的模型及其算法研究[D];哈爾濱工業(yè)大學(xué);2015年

4 湯雅連;關(guān)聯(lián)物流運(yùn)輸調(diào)度問題研究[D];廣東工業(yè)大學(xué);2015年

5 周理;高效可重構(gòu)陣列計(jì)算：體系結(jié)構(gòu)，設(shè)計(jì)方法與程序映射技術(shù)研究[D];國防科學(xué)技術(shù)大學(xué);2014年

6 馮大光;一類批處理機(jī)調(diào)度的理論和方法研究[D];東北大學(xué);2011年

7 孟盈;鋼鐵企業(yè)并行批生產(chǎn)決策與調(diào)度問題研究[D];東北大學(xué);2011年

8 楊磊;內(nèi)容網(wǎng)絡(luò)中內(nèi)容調(diào)度技術(shù)研究[D];重慶大學(xué);2015年

9 李亞志;流水制造單元調(diào)度智能優(yōu)化方法[D];東南大學(xué);2015年

10 丁寧;若干調(diào)度問題的算法研究[D];大連理工大學(xué);2016年

相關(guān)碩士學(xué)位論文 前10條

1 張亮;云計(jì)算環(huán)境下的資源調(diào)度技術(shù)的研究[D];江南大學(xué);2015年

2 馮卓鵬;重載運(yùn)輸卸車組織優(yōu)化研究[D];西南交通大學(xué);2015年

3 崔雪源;基于遺傳模擬退火算法的航班著陸調(diào)度問題[D];華中師范大學(xué);2015年

4 王翠;基于超圖模型和相繼干擾消除的鏈路調(diào)度問題的研究[D];曲阜師范大學(xué);2015年

5 張勇;帶拒絕和釋放時(shí)間的單機(jī)批調(diào)度問題[D];山東大學(xué);2015年

6 吳凡;基于粒子群優(yōu)化算法的風(fēng)電-火電機(jī)組組合調(diào)度研究[D];華北電力大學(xué);2015年

7 趙虎;MTO模式下的制造企業(yè)穩(wěn)健型調(diào)度問題研究[D];重慶理工大學(xué);2015年

8 吉佳紅;基于細(xì)菌覓食算法的改進(jìn)及應(yīng)用研究[D];江蘇科技大學(xué);2015年

9 周超;柔性作業(yè)車間批量問題研究[D];寧波大學(xué);2014年

10 趙興野;工序順序柔性作業(yè)車間描述與調(diào)度研究[D];大連理工大學(xué);2015年

，

本文編號(hào)：1352370