發(fā)布時(shí)間：2019-10-13 19:22

【摘要】：在現(xiàn)實(shí)生產(chǎn)中,加工工件在排序中越晚開(kāi)始加工,它的實(shí)際加工時(shí)間就會(huì)越大。比如金融管理、鋼鐵生產(chǎn)、消防、資源分配和國(guó)防等等,任何延遲都會(huì)導(dǎo)致退化現(xiàn)象的產(chǎn)生。同時(shí),工件在加工之前一般需要預(yù)加工的過(guò)程,預(yù)加工所用的時(shí)間就稱(chēng)為釋放時(shí)間。而且,機(jī)器通常需要進(jìn)行保養(yǎng),或發(fā)生故障時(shí)進(jìn)行維修等原因,導(dǎo)致機(jī)器在某一時(shí)間段內(nèi)無(wú)法工作,該時(shí)間段即為機(jī)器的不可用區(qū)間。經(jīng)典的排序問(wèn)題一般假設(shè)所有的工件都進(jìn)行加工,對(duì)于工件可拒絕的排序問(wèn)題,廠家通常會(huì)拒絕一些獲利相對(duì)較小的工件,拒絕工件雖然可以節(jié)約生產(chǎn)成本,但是需要付出一定的懲罰費(fèi)用,該懲罰費(fèi)用即為拒絕懲罰。比如航空業(yè)、電子工業(yè)等等。本文研究帶有釋放時(shí)間、退化效應(yīng)、拒絕工件及不可用區(qū)間的排序問(wèn)題。該問(wèn)題中,所有工件的釋放時(shí)間是相同的。工件可以被排在機(jī)器上進(jìn)行加工,也可以被拒絕,但是需要支付一定的拒絕懲罰。機(jī)器帶有一個(gè)不可用區(qū)間,在這段時(shí)間內(nèi),機(jī)器無(wú)法工作。具體內(nèi)容概括如下:1.討論了目標(biāo)函數(shù)是所有加工工件的最大完工時(shí)間與所有拒絕工件的拒絕懲罰之和的單機(jī)排序問(wèn)題。首先給出了擬多項(xiàng)式時(shí)間的動(dòng)態(tài)規(guī)劃算法,最后得到了全多項(xiàng)式近似方案,并分析了該近似方案的時(shí)間復(fù)雜性。2.討論了目標(biāo)函數(shù)是所有加工工件的加權(quán)總完工時(shí)間與所有拒絕工件的拒絕懲罰之和的單機(jī)排序問(wèn)題。首先,說(shuō)明了這個(gè)問(wèn)題是一般意義NP-難的,然后通過(guò)劃分程序的方法得到了全多項(xiàng)式近似方案,最后,分析了該近似方案的時(shí)間復(fù)雜性。3.討論了兩臺(tái)機(jī)器排序問(wèn)題。其中一臺(tái)機(jī)器帶有一個(gè)不可用區(qū)間,在這段時(shí)間內(nèi),機(jī)器無(wú)法工作,另外一臺(tái)機(jī)器一直可用。討論的目標(biāo)函數(shù)所有加工工件的加權(quán)總完工時(shí)間與所有拒絕工件的拒絕懲罰之和。首先,說(shuō)明了這個(gè)問(wèn)題是一般意義NP-難的,然后通過(guò)劃分程序的方法得到了全多項(xiàng)式近似方案,最后,分析了該近似方案的時(shí)間復(fù)雜性。
【學(xué)位授予單位】：沈陽(yáng)師范大學(xué)
【學(xué)位級(jí)別】：碩士
【學(xué)位授予年份】：2015
【分類(lèi)號(hào)】：O223

【相似文獻(xiàn)】

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

1 周泓,張惠民;求解多目標(biāo)作業(yè)排序問(wèn)題的遺傳算法[J];系統(tǒng)工程理論與實(shí)踐;2001年08期

2 周泓,姬彬;求解作業(yè)排序問(wèn)題的通用混合遺傳算法研究[J];系統(tǒng)工程理論與實(shí)踐;2001年12期

3 陳德伍,張 峰;一類(lèi)新的可控排序問(wèn)題(英文)[J];運(yùn)籌學(xué)學(xué)報(bào);2001年04期

4 張瑞,劉國(guó)珍;單機(jī)排序問(wèn)題最優(yōu)解方法[J];聊城師院學(xué)報(bào)(自然科學(xué)版);2001年02期

5 黎群;單臺(tái)機(jī)器多目標(biāo)作業(yè)排序問(wèn)題的探討[J];系統(tǒng)工程理論方法應(yīng)用;2001年02期

6 方保昒,徐漢忠;用單親遺傳算法解具有窗口式交貨期的多機(jī)加工排序問(wèn)題[J];系統(tǒng)工程理論方法應(yīng)用;2001年04期

7 宋政芳,孫世杰,吳春燕;一個(gè)超前有獎(jiǎng)遲后受罰的排序問(wèn)題(英文)[J];運(yùn)籌學(xué)學(xué)報(bào);2002年04期

8 趙傳立,唐恒永;具有相關(guān)調(diào)整時(shí)間的排序問(wèn)題[J];沈陽(yáng)師范學(xué)院學(xué)報(bào)(自然科學(xué)版);2002年01期

9 鄭自途;關(guān)于"三臺(tái)以上機(jī)床作業(yè)排序問(wèn)題"的算法[J];天津理工學(xué)院學(xué)報(bào);2002年04期

10 張玉忠,苗翠霞;復(fù)制法及其在分批排序問(wèn)題中的應(yīng)用[J];曲阜師范大學(xué)學(xué)報(bào)(自然科學(xué)版);2004年02期

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

1 柏孟卓;唐國(guó)春;;加工時(shí)間可控的同時(shí)加工排序問(wèn)題[A];2006年中國(guó)運(yùn)籌學(xué)會(huì)數(shù)學(xué)規(guī)劃分會(huì)代表會(huì)議暨第六屆學(xué)術(shù)會(huì)議論文集[C];2006年

2 張蓮珠;;關(guān)于六角鏈的極值和排序問(wèn)題的一些結(jié)果[A];中國(guó)運(yùn)籌學(xué)會(huì)第六屆學(xué)術(shù)交流會(huì)論文集（上卷）[C];2000年

3 周支立;李懷祖;;有重疊區(qū)域的兩抓鉤周期性排序問(wèn)題的求解[A];Systems Engineering, Systems Science and Complexity Research--Proceeding of 11th Annual Conference of Systems Engineering Society of China[C];2000年

4 孫世杰;陳躍;;參數(shù)可控的排序問(wèn)題[A];2001年全國(guó)數(shù)學(xué)規(guī)劃及運(yùn)籌研討會(huì)論文集[C];2001年

5 張玉忠;;分批排序問(wèn)題研究[A];中國(guó)運(yùn)籌學(xué)會(huì)第七屆學(xué)術(shù)交流會(huì)論文集（上卷）[C];2004年

6 張玉忠;;分批排序問(wèn)題研究[A];中國(guó)運(yùn)籌學(xué)會(huì)第七屆學(xué)術(shù)交流會(huì)論文集（中卷）[C];2004年

7 譚萬(wàn)達(dá);;二元對(duì)比排序中的最少逆序原理[A];中國(guó)系統(tǒng)工程學(xué)會(huì)模糊數(shù)學(xué)與模糊系統(tǒng)委員會(huì)第五屆年會(huì)論文選集[C];1990年

8 呂緒華;楊漢興;;求解裝配式排序問(wèn)題的歸并算法及其性能比研究[A];中國(guó)運(yùn)籌學(xué)會(huì)第六屆學(xué)術(shù)交流會(huì)論文集（下卷）[C];2000年

9 樊保強(qiáng);;帶倉(cāng)儲(chǔ)約束的準(zhǔn)時(shí)排序問(wèn)題[A];中國(guó)運(yùn)籌學(xué)會(huì)第九屆學(xué)術(shù)交流會(huì)論文集[C];2008年

10 陳榮軍;唐國(guó)春;;自由作業(yè)環(huán)境下的供應(yīng)鏈排序問(wèn)題[A];中國(guó)運(yùn)籌學(xué)會(huì)第九屆學(xué)術(shù)交流會(huì)論文集[C];2008年

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

1 山東 趙玉勇;數(shù)組，你的規(guī)律機(jī)器[N];電腦報(bào);2004年

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

1 仲維亞;供應(yīng)鏈管理中的若干排序問(wèn)題研究[D];浙江大學(xué);2008年

2 尹曉;基因組重組排序問(wèn)題的算法研究[D];山東大學(xué);2010年

3 余煒;若干網(wǎng)絡(luò)排序問(wèn)題的算法和復(fù)雜性研究[D];華東理工大學(xué);2010年

4 張安;帶服務(wù)等級(jí)的在線(xiàn)排序問(wèn)題及相關(guān)問(wèn)題研究[D];浙江大學(xué);2009年

5 鄭睿;鋼鐵生產(chǎn)中的批處理機(jī)作業(yè)排序問(wèn)題算法研究[D];復(fù)旦大學(xué);2009年

6 季敏;當(dāng)代工業(yè)中的若干排序問(wèn)題研究[D];浙江大學(xué);2006年

7 李好好;若干排序問(wèn)題研究[D];浙江大學(xué);2014年

8 丁國(guó)生;多代理競(jìng)爭(zhēng)排序問(wèn)題的研究[D];上海大學(xué);2009年

9 葉德仕;通訊網(wǎng)絡(luò)中排序問(wèn)題的若干在線(xiàn)和高性能算法[D];浙江大學(xué);2005年

10 王成飛;幾類(lèi)新型在線(xiàn)分批排序問(wèn)題[D];曲阜師范大學(xué);2011年

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

1 董柳毅;與誤工有關(guān)的多目標(biāo)排序問(wèn)題[D];重慶師范大學(xué);2009年

2 王迅娣;成組加工排序和供應(yīng)鏈在線(xiàn)排序問(wèn)題[D];曲阜師范大學(xué);2010年

3 王潔明;有關(guān)代理競(jìng)爭(zhēng)排序問(wèn)題的研究[D];華東理工大學(xué);2011年

4 劉麗麗;分批排序問(wèn)題[D];曲阜師范大學(xué);2000年

5 鄢楚楠;2，，4-逆序變換的置換排序問(wèn)題[D];浙江大學(xué);2006年

6 張兵權(quán);單位加工時(shí)間的公共時(shí)間窗單機(jī)分組排序問(wèn)題[D];浙江大學(xué);2006年

7 姜冠成;分批排序問(wèn)題和資源約束排序問(wèn)題[D];蘇州大學(xué);2005年

8 胡榮;一類(lèi)分裝式排序問(wèn)題的計(jì)算方法和計(jì)算復(fù)雜性研究[D];武漢科技大學(xué);2006年

9 馬蕾;帶傳遞時(shí)間的通信模型中的樹(shù)約束排序問(wèn)題[D];蘭州大學(xué);2007年

10 王小明;不允許等待的混合流水兩車(chē)間排序問(wèn)題[D];清華大學(xué);2002年

本文編號(hào)：2548848