發(fā)布時(shí)間：2017-05-05 20:11

  本文關(guān)鍵詞：帶拒絕和釋放時(shí)間的單機(jī)批調(diào)度問題，由筆耕文化傳播整理發(fā)布。

【摘要】：隨著科技的日益革新與制造業(yè)的發(fā)展,調(diào)度問題的重要性得到了加強(qiáng)。有許多相關(guān)的研究者對(duì)于調(diào)度問題進(jìn)行了大量的研究。大部分的研究都是在工件必須被加工這一前提條件下進(jìn)行的,但是有些情況下可以選擇拒絕加工一些工件,本文就是在這一前提條件下進(jìn)行研究的。調(diào)度問題的研究方向有很多。比如車間調(diào)度問題,單機(jī)調(diào)度問題,并行機(jī)調(diào)度問題。本文主要研究單機(jī)調(diào)度問題。研究的問題具體如下：給定n個(gè)工件,其中每個(gè)工件的屬性包括：處理時(shí)間Pj；到達(dá)時(shí)間rj(在這個(gè)時(shí)刻之前,該工件不能被調(diào)度)；懲罰值ej(工件是可以被拒絕的,但是當(dāng)拒絕工件時(shí),我們必須付出一定的代價(jià),即為ej)。在加工期間,機(jī)器是不能暫停的,只能當(dāng)一批工件都被處理完時(shí),才會(huì)停止。我們只考慮一個(gè)機(jī)器的情況,即單機(jī)調(diào)度。機(jī)器最多一次同時(shí)加工b個(gè)工件,這b個(gè)工件稱為一批,批里的工件的開始時(shí)間與結(jié)束時(shí)間一樣,批的處理時(shí)間即為批中工件處理時(shí)間最大的那個(gè)。我們的目標(biāo)是求最小的被接收工件的完成時(shí)間之和加被拒絕的工件的懲罰值之和。工件的完成時(shí)間即為工件的開始被處理的時(shí)間或者說工件所在批的開始時(shí)間加上批的處理時(shí)間。我們對(duì)于目標(biāo)函數(shù)設(shè)計(jì)了一個(gè)動(dòng)態(tài)規(guī)劃算法,但是這個(gè)動(dòng)態(tài)規(guī)劃并不能求得最優(yōu)解,而是最優(yōu)解的一個(gè)近似解。因?yàn)?在算法中,我們要對(duì)給定的一部分初始條件做出改變,比如工件的到達(dá)時(shí)間與工件的處理時(shí)間,將其規(guī)整為某個(gè)數(shù)的指數(shù)倍。無規(guī)律初始條件改變?yōu)橛幸欢ㄒ?guī)律的初始條件,使得我們后續(xù)的分析變得相對(duì)簡單一些。我們將工件分成了長短兩類工件,并將它們分開處理。對(duì)于短工件我們?nèi)匀徊捎昧藙?dòng)態(tài)規(guī)劃的方式,而對(duì)于長工件,則采取了枚舉的方式。最后,我們分析了時(shí)間復(fù)雜度并證明了結(jié)果是一個(gè)多項(xiàng)式時(shí)間的近似方案。
【關(guān)鍵詞】：到達(dá)時(shí)間 懲罰值 動(dòng)態(tài)規(guī)劃 完成時(shí)間之和加懲罰值之和 批調(diào)度
【學(xué)位授予單位】：山東大學(xué)
【學(xué)位級(jí)別】：碩士
【學(xué)位授予年份】：2015
【分類號(hào)】：TB497
【目錄】：

• 摘要8-9
• ABSTRACT9-10
• 第一章 緒論10-14
• 1.1 研究的背景與意義10-11
• 1.2 問題介紹11-12
• 1.3 論文所做的工作12-13
• 1.4 論文結(jié)構(gòu)13-14
• 第二章 研究現(xiàn)狀與研究方法14-23
• 2.1 三元組的介紹14-15
• 2.2 不含拒絕的調(diào)度問題的研究15-16
• 2.2.1 FBLPT規(guī)則15
• 2.2.2 對(duì)于包含到達(dá)時(shí)間的調(diào)度問題15-16
• 2.2.3 對(duì)于包含工件尺寸的調(diào)度問題16
• 2.3 包含拒絕的調(diào)度問題的研究16-17
• 2.3.1 對(duì)于最小化最大完成時(shí)間問題的研究16-17
• 2.3.2 關(guān)于完成時(shí)間之和問題的研究17
• 2.4 解決調(diào)度問題的常用的一些研究方法17-22
• 2.4.1 優(yōu)化算法18
• 2.4.2 啟發(fā)式算法18-22
• 2.5 本章小結(jié)22-23
• 第三章 多項(xiàng)式時(shí)間近似方案23-43
• 3.1 預(yù)備知識(shí)與相關(guān)引理23-28
• 3.1.1 預(yù)備知識(shí)23-24
• 3.1.2 相關(guān)引理24-28
• 3.2 多項(xiàng)式時(shí)間算法28-42
• 3.2.1 算法的動(dòng)態(tài)規(guī)劃公式28-30
• 3.2.2 將長短工件分開30-31
• 3.2.3 對(duì)于短工件的分批處理31-35
• 3.2.4 對(duì)于長工件的處理方法35-37
• 3.2.5 在多項(xiàng)式時(shí)間內(nèi)計(jì)算t,t',U,V的選擇37-40
• 3.2.6 在多項(xiàng)式時(shí)間內(nèi)計(jì)算W_(i+1)(t,t',a-a',U-V)40-42
• 3.3 本章小結(jié)42-43
• 第四章 總結(jié)與展望43-45
• 參考文獻(xiàn)45-48
• 致謝48-49
• 附件49

【相似文獻(xiàn)】

中國期刊全文數(shù)據(jù)庫 前10條

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

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

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

4 席裕庚,王長軍;控制、規(guī)劃和調(diào)度問題中的博弈論應(yīng)用[J];中國計(jì)量學(xué)院學(xué)報(bào);2005年01期

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

6 喻道遠(yuǎn);史登松;劉盛強(qiáng);張三強(qiáng);;帶模糊排序的移動(dòng)瓶頸法求解不確定調(diào)度問題[J];機(jī)械制造;2011年02期

7 劉鵬;周曉曄;衣娜;;帶有減少線性惡化效應(yīng)的雙代理調(diào)度問題[J];系統(tǒng)工程學(xué)報(bào);2011年03期

8 劉曉東;陳英武;龍運(yùn)軍;賀仁杰;李菊芳;;同型機(jī)在線調(diào)度問題研究進(jìn)展[J];計(jì)算機(jī)集成制造系統(tǒng);2012年03期

9 姚君遺，楊善林，左春榮;基于實(shí)例FMS的AGV調(diào)度數(shù)學(xué)模型與算法[J];合肥工業(yè)大學(xué)學(xué)報(bào)(自然科學(xué)版);1995年01期

10 董平;機(jī)器調(diào)度問題及求解方法[J];物流技術(shù)與應(yīng)用;1997年01期

中國重要會(huì)議論文全文數(shù)據(jù)庫 前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年

中國重要報(bào)紙全文數(shù)據(jù)庫 前2條

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

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

中國博士學(xué)位論文全文數(shù)據(jù)庫 前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 左燕;大規(guī)模復(fù)雜生產(chǎn)調(diào)度問題瓶頸分解方法研究[D];上海交通大學(xué);2007年

4 王磊;OKP企業(yè)分散式項(xiàng)目計(jì)劃與調(diào)度優(yōu)化方法研究[D];哈爾濱工業(yè)大學(xué);2013年

5 李小林;平行機(jī)環(huán)境下批處理機(jī)調(diào)度問題研究[D];中國科學(xué)技術(shù)大學(xué);2012年

6 金毅;模糊集合論在生產(chǎn)計(jì)劃和調(diào)度中的應(yīng)用研究[D];東南大學(xué);1994年

7 李玉慶;動(dòng)態(tài)不確定環(huán)境下航天器觀測調(diào)度問題研究[D];哈爾濱工業(yè)大學(xué);2008年

8 劉志雄;調(diào)度問題中的粒子群優(yōu)化方法及其應(yīng)用研究[D];武漢理工大學(xué);2005年

9 湯健超;基于混合進(jìn)化算法的若干調(diào)度問題研究[D];華南理工大學(xué);2012年

10 江維;任務(wù)關(guān)鍵實(shí)時(shí)系統(tǒng)的可信感知調(diào)度研究[D];電子科技大學(xué);2009年

中國碩士學(xué)位論文全文數(shù)據(jù)庫 前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 鮑和映;航空公司不正常航班調(diào)度研究[D];南京航空航天大學(xué);2013年

9 羊曉飛;基于場景和模糊描述的不確定Job Shop魯棒調(diào)度[D];山東大學(xué);2009年

10 王建波;基于綜合利益最優(yōu)的集成調(diào)度優(yōu)化模型應(yīng)用研究[D];大連交通大學(xué);2010年

  本文關(guān)鍵詞：帶拒絕和釋放時(shí)間的單機(jī)批調(diào)度問題，由筆耕文化傳播整理發(fā)布。

，

本文編號(hào)：347014