本文關(guān)鍵詞：考慮延誤的平行機(jī)可拒絕排序

  更多相關(guān)文章： 可拒絕排序 平行機(jī) 到達(dá)時(shí)間 最大延誤 動(dòng)態(tài)規(guī)劃

【摘要】：平行機(jī)排序問(wèn)題是多處理機(jī)排序問(wèn)題的一種情況,在理論及其應(yīng)用過(guò)程中都有著重要的意義.從理論上來(lái)看,平行機(jī)排序問(wèn)題是單機(jī)排序問(wèn)題的推廣;而從應(yīng)用角度來(lái)看,它的研究與我們的生活息息相關(guān),有著廣泛的應(yīng)用背景.本文我們主要研究工件可拒絕約束下的平行機(jī)排序問(wèn)題.第一章主要介紹一些排序問(wèn)題的背景、近年來(lái)的研究現(xiàn)狀以及相關(guān)的一些基礎(chǔ)知識(shí).然后簡(jiǎn)單介紹了一下本文的主要研究成果.第二章主要研究同速機(jī)可拒絕的排序問(wèn)題,主要分了三個(gè)模型：(1)工件不同時(shí)到達(dá)、可拒絕的同速機(jī)排序問(wèn)題.在拒絕工件的懲罰費(fèi)用之和不超過(guò)一給定上界U的約束下,目標(biāo)為極小化接受工件的最大完工時(shí)間.通過(guò)動(dòng)態(tài)規(guī)劃算法可在O(mn(rmax+P)m)時(shí)間內(nèi)得到最優(yōu)值,其中m是機(jī)器臺(tái)數(shù);n是工件個(gè)數(shù);rmax表示工件的最大到達(dá)時(shí)間;pj是工件Jj的加工時(shí)間,P=∑j=1Pjn表示所有工件的加工時(shí)間之和.此外,我們還給出了這一排序問(wèn)題的一個(gè)FPTAS算法;(2)工件可拒絕的同速機(jī)排序問(wèn)題.目標(biāo)為極小化接受工件的最大延誤與拒絕工件的懲罰費(fèi)用之和.通過(guò)動(dòng)態(tài)規(guī)劃可在O(mnPm∑j=1nWi)時(shí)間內(nèi)得到最優(yōu)值,其中wj,(j=1,2,…,n)表示工件Ji的懲罰費(fèi)用;(3)工件可拒絕的同速機(jī)排序問(wèn)題.在拒絕工件的懲罰費(fèi)用之和不超過(guò)一給定上界U的約束下,目標(biāo)為極小化接受工件的最大延誤.通過(guò)動(dòng)態(tài)規(guī)劃算法可在O(mnUPm)時(shí)間內(nèi)得到最優(yōu)值.第三章主要研究恒速機(jī)可拒絕的排序問(wèn)題,主要分了四個(gè)模型：(1)工件不同時(shí)到達(dá)、可拒絕的恒速機(jī)排序問(wèn)題.目標(biāo)為極小化接受工件的最大完工時(shí)間與拒絕工件的懲罰費(fèi)用之和.通過(guò)動(dòng)態(tài)規(guī)劃算法可在O(mn(rmax +P/bm)m)時(shí)間內(nèi)得到最優(yōu)值,其中bi,(i=1,2,…,m)表示機(jī)器M,的加工速度;(2)工件不同時(shí)到達(dá)、可拒絕的恒速機(jī)排序問(wèn)題.在拒絕工件的懲罰費(fèi)用之和不超過(guò)一給定上界U的約束下,目標(biāo)為極小化接受工件的最大完工時(shí)間.通過(guò)動(dòng)態(tài)規(guī)劃算法可在O(mn(rmax+P/bm)m)時(shí)間內(nèi)得到最優(yōu)值;(3)工件可拒絕的恒速機(jī)排序問(wèn)題.目標(biāo)為極小化接受工件的最大延誤與拒絕工件的懲罰費(fèi)用之和.通過(guò)動(dòng)態(tài)規(guī)劃算法可在O(mn(P/bm)m∑i=1nWi)時(shí)間內(nèi)得到最優(yōu)值;(4)工件可拒絕的恒速機(jī)排序問(wèn)題.在拒絕工件的懲罰費(fèi)用之和不超過(guò)一給定上界U的約束下,目標(biāo)為極小化接受工件的最大延誤.通過(guò)動(dòng)態(tài)規(guī)劃算法可在O(mnU(P/bm)m)時(shí)間內(nèi)得到最優(yōu)值.
【關(guān)鍵詞】：可拒絕排序 平行機(jī) 到達(dá)時(shí)間 最大延誤 動(dòng)態(tài)規(guī)劃
【學(xué)位授予單位】：曲阜師范大學(xué)
【學(xué)位級(jí)別】：碩士
【學(xué)位授予年份】：2015
【分類(lèi)號(hào)】：O223
【目錄】：

• 摘要3-5
• Abstract5-8
• 第1章 緒論8-14
• §1.1 排序問(wèn)題8
• §1.2 平行機(jī)排序和可拒絕排序8-9
• §1.3 預(yù)備知識(shí)9-11
• §1.4 符號(hào)說(shuō)明11
• §1.5 研究現(xiàn)狀11-13
• §1.6 本文的主要工作13-14
• 第2章 考慮延誤的同速機(jī)可拒絕排序14-22
• §2.1 問(wèn)題描述14
• §2.2 P_m|rej,r_j,∑_(j∈R)w_j≤U|C_(max)14-17
• §2.3 P_m|rej|L_(max)+∑_(j∈R)w_j17-20
• §2.4 P_m|rej,∑_(j∈R)w_j≤U|L_(max)20-21
• §2.5 總結(jié)21-22
• 第3章 考慮延誤的恒速機(jī)可拒絕排序22-29
• §3.1 問(wèn)題描述22
• §3.2 Q_m|rej,r_j|C_(max)+∑_(j∈R)w_j22-24
• §3.3 Q_m|rej,r_j,∑_(j∈R)w_j≤U|C_(max)24-26
• §3.4 Q_m|rej|L_(max)+∑_(j∈R)w_j26-27
• §3.5 Q_m|rej,∑_(j∈R)w_j≤U|L_(max)27-28
• §3.6 總結(jié)28-29
• 參考文獻(xiàn)29-32
• 在讀期間發(fā)表的學(xué)術(shù)論文及研究成果32-33
• 致謝33

【相似文獻(xiàn)】

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

1 張智聰;鄭力;翁小華;;基于增強(qiáng)學(xué)習(xí)的平行機(jī)調(diào)度研究[J];計(jì)算機(jī)集成制造系統(tǒng);2007年01期

2 陳榮軍;唐國(guó)春;;平行機(jī)的供應(yīng)鏈排序[J];系統(tǒng)科學(xué)與數(shù)學(xué);2010年02期

3 陳榮軍;張峰;唐國(guó)春;;平行機(jī)及自由作業(yè)的排序與轉(zhuǎn)包[J];系統(tǒng)工程學(xué)報(bào);2011年05期

4 陳榮軍;唐國(guó)春;;平行機(jī)的排序與轉(zhuǎn)包(英文)[J];數(shù)學(xué)季刊;2012年04期

5 蔣大奎;李波;;平行機(jī)作業(yè)環(huán)境下的訂單分配與排序[J];管理學(xué)報(bào);2013年06期

6 王成堯,汪定偉;有模機(jī)配合約束的平行機(jī)臺(tái)調(diào)度方法[J];東北大學(xué)學(xué)報(bào);1999年04期

7 曾歡歡,胡建華;可換速平行機(jī)工件帶起止值的搶先進(jìn)度表[J];數(shù)學(xué)理論與應(yīng)用;1999年02期

8 蔣大奎;李波;曹立思;;考慮轉(zhuǎn)包的平行機(jī)供應(yīng)鏈排序[J];控制與決策;2014年05期

9 陳仕平,張國(guó)川;兩臺(tái)平行機(jī)的實(shí)時(shí)到達(dá)在線排序[J];應(yīng)用數(shù)學(xué)學(xué)報(bào);2000年01期

10 周偉剛;高成修;黃凱;;加工時(shí)間可控和簡(jiǎn)單線性增長(zhǎng)的平行機(jī)排序[J];應(yīng)用數(shù)學(xué)學(xué)報(bào);2010年04期

中國(guó)重要會(huì)議論文全文數(shù)據(jù)庫(kù) 前1條

1 聞?wù)裥l(wèi);;一類(lèi)平行機(jī)上的任務(wù)指派問(wèn)題及其動(dòng)態(tài)規(guī)劃算法[A];中國(guó)運(yùn)籌學(xué)會(huì)第九屆學(xué)術(shù)交流會(huì)論文集[C];2008年

中國(guó)博士學(xué)位論文全文數(shù)據(jù)庫(kù) 前3條

1 程貞敏;平行機(jī)調(diào)度問(wèn)題研究的若干結(jié)果[D];北京師范大學(xué);2008年

2 蔡圣義;同類(lèi)平行機(jī)在線半在線排序參數(shù)界的若干研究[D];浙江大學(xué);2010年

3 何龍敏;一類(lèi)平行機(jī)和批處理機(jī)組成的二階段柔性流水作業(yè)問(wèn)題[D];上海大學(xué);2006年

中國(guó)碩士學(xué)位論文全文數(shù)據(jù)庫(kù) 前10條

1 洪文益;與平行機(jī)排序相關(guān)的幾個(gè)組合問(wèn)題研究[D];清華大學(xué);2013年

2 李松松;在平行機(jī)博弈排序中的近似強(qiáng)納什均衡問(wèn)題[D];曲阜師范大學(xué);2013年

3 王君麗;有加工權(quán)限平行機(jī)在線問(wèn)題研究[D];浙江大學(xué);2012年

4 財(cái)玉華;具有非交叉維修時(shí)間的平行機(jī)在線排序[D];鄭州大學(xué);2007年

5 莫禎貞;改進(jìn)粒子群算法在模糊環(huán)境下平行機(jī)批調(diào)度問(wèn)題中的應(yīng)用研究[D];中國(guó)科學(xué)技術(shù)大學(xué);2010年

6 林琳;具有同時(shí)性約束的平行機(jī)排序問(wèn)題[D];鄭州大學(xué);2006年

7 徐武來(lái);具有完工期和工裝數(shù)量約束的平行機(jī)調(diào)度方法[D];廣東工業(yè)大學(xué);2012年

8 何曉瓊;一致平行機(jī)上在線排序[D];湖南師范大學(xué);2009年

9 袁俊嶺;鏈組約束下的平行機(jī)在線排序[D];鄭州大學(xué);2008年

10 崔婉良;平行機(jī)上工件具有鏈組約束及可預(yù)測(cè)的在線排序[D];鄭州大學(xué);2013年

，

本文編號(hào)：824590