本文關(guān)鍵詞：預(yù)防性維護(hù)下的混合型平行機(jī)調(diào)度問(wèn)題研究

  更多相關(guān)文章： 調(diào)度 維護(hù) 數(shù)學(xué)規(guī)劃模型 啟發(fā)式算法 最壞情況分析 數(shù)值實(shí)驗(yàn)

【摘要】：傳統(tǒng)的調(diào)度研究假設(shè)機(jī)器可以一直被使用,直到加工完所有需要加工的工件.然而,在現(xiàn)實(shí)生產(chǎn)活動(dòng)中,往往需要對(duì)機(jī)器進(jìn)行預(yù)防性的維護(hù).常見(jiàn)的維護(hù)類型有:單次維護(hù)、周期維護(hù)和工具更換維護(hù).本文研究了預(yù)防性維護(hù)下一類混合型平行機(jī)調(diào)度問(wèn)題:有n個(gè)工件需要加工,有兩臺(tái)平行機(jī)可供使用,其中一臺(tái)需要工具更換維護(hù),另一臺(tái)需要周期維護(hù),目標(biāo)是確定每次工具更換維護(hù)的開(kāi)始時(shí)刻和每個(gè)工件所對(duì)應(yīng)的機(jī)器及其開(kāi)始加工時(shí)刻使得這n個(gè)工件的時(shí)間表長(zhǎng)(即最后完工的工件的完工時(shí)刻)最小.本文的主要工作如下.(1)分析了該問(wèn)題的計(jì)算復(fù)雜性和不可逼近性.證明了該問(wèn)題是強(qiáng)NP-難的并且不存在最壞情況界小于2的多項(xiàng)式時(shí)間算法除非P=NP.(2)為求解中小規(guī)模的調(diào)度實(shí)例,基于“把維護(hù)看作工件”、“機(jī)器拼接”和“工件與加工位置一一對(duì)應(yīng)”的思想給出了兩個(gè)數(shù)學(xué)規(guī)劃模型,基于“裝箱問(wèn)題”的思想給出了另外兩個(gè)數(shù)學(xué)規(guī)劃模型,并編程實(shí)現(xiàn)了上述四個(gè)模型.(3)為求解大規(guī)模的調(diào)度實(shí)例,基于“工件完成時(shí)間優(yōu)先分配機(jī)制”,“機(jī)器完成時(shí)間優(yōu)先分配機(jī)制”,經(jīng)典的“LPT規(guī)則”和“LS規(guī)則”設(shè)計(jì)了四個(gè)啟發(fā)式算法.通過(guò)對(duì)上述四個(gè)算法所生成的調(diào)度方案的研究,提出了對(duì)上述算法得到的調(diào)度方案進(jìn)行“后優(yōu)化”想法并以此為基礎(chǔ)設(shè)計(jì)了四個(gè)新的算法.注意到存在實(shí)例表明沒(méi)有一個(gè)算法占絕對(duì)優(yōu)勢(shì),于是把上述八個(gè)算法的輸出結(jié)果中最好的一個(gè)做為最終輸出,這樣就得到了第九個(gè)啟發(fā)式算法.(4)從理論上對(duì)上述九個(gè)算法進(jìn)行了最壞情況分析.證明了當(dāng)最后一個(gè)非空維護(hù)間隔中至少有兩個(gè)工件時(shí),上述九個(gè)算法的最壞情況界均為2.(5)通過(guò)數(shù)值實(shí)驗(yàn)對(duì)上述九個(gè)算法進(jìn)行了平均誤差分析和最大誤差分析.為了避免使用數(shù)學(xué)規(guī)劃模型求解大規(guī)模的調(diào)度實(shí)例,根據(jù)機(jī)器的特點(diǎn)設(shè)計(jì)了“逐次半毫升水量轉(zhuǎn)移算法”來(lái)求最優(yōu)時(shí)間表長(zhǎng)的一個(gè)下界,根據(jù)工件加工的特點(diǎn)得到了最優(yōu)時(shí)間表長(zhǎng)的另外一個(gè)下界.取這兩個(gè)下界中較大者做為數(shù)值實(shí)驗(yàn)中的比較對(duì)象,通過(guò)編程實(shí)現(xiàn)了上述九個(gè)算法和下界,給出了工件規(guī)模為20,200和2000下各36組參數(shù)(每組參數(shù)各取100個(gè)實(shí)例)對(duì)應(yīng)的平均誤差和最大誤差.結(jié)果表明,基于“機(jī)器完成時(shí)間優(yōu)先分配機(jī)制”和“LPT規(guī)則”的算法誤差較小.(6)假定維護(hù)時(shí)長(zhǎng)是其上一次維護(hù)間隔中的負(fù)載(即所加工的工件的加工時(shí)長(zhǎng)之和)的非負(fù)增函數(shù),得到了該平行機(jī)調(diào)度問(wèn)題的一個(gè)擴(kuò)展版本,給出了四個(gè)數(shù)學(xué)規(guī)劃模型.
【學(xué)位授予單位】：湖南大學(xué)
【學(xué)位級(jí)別】：博士
【學(xué)位授予年份】：2016
【分類號(hào)】：O224

【相似文獻(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);;一類平行機(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ù) 前7條

1 劉珊珊;一些單機(jī)和平行機(jī)排序情形的研究[D];華東理工大學(xué);2015年

2 陳友軍;有運(yùn)送協(xié)調(diào)性的最小化最大運(yùn)送完成時(shí)間平行機(jī)排序[D];鄭州大學(xué);2016年

3 何杰;預(yù)防性維護(hù)下的混合型平行機(jī)調(diào)度問(wèn)題研究[D];湖南大學(xué);2016年

4 李松松;現(xiàn)代排序理論中的三類重要問(wèn)題：博弈排序，分批可拒絕排序和在線排序[D];曲阜師范大學(xué);2016年

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

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

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

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

1 趙云;帶等級(jí)平行機(jī)調(diào)度和MapReduce調(diào)度問(wèn)題的算法研究[D];浙江理工大學(xué);2016年

2 張家寶;考慮維護(hù)和可中斷工件的混合型平行機(jī)調(diào)度問(wèn)題研究[D];東華理工大學(xué);2016年

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

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

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

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

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

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

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

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

，

本文編號(hào)：1259598