【摘要】：在恒同機(jī)中每臺機(jī)器都有相同的速度,這里我們假設(shè)所有機(jī)器的速度為1.這樣工件的加工時(shí)間與機(jī)器沒有關(guān)系,僅與它自身的長度有關(guān).限選機(jī)器是指機(jī)器因功能不同導(dǎo)致工件在選擇機(jī)器加工時(shí)受到限制,從而工件只能在允許加工的特殊機(jī)器子集上加工.將允許加工工件的機(jī)器組成的集合稱為加工集.在線排序是指只有在工件到達(dá)之后才能知道工件的信息,甚至它的存在性.工件按到達(dá)方式可分為按時(shí)在線和按序在線兩類.在本文第二章中,我們主要探討了 m臺限選恒同機(jī)上的在線分批排序問題.平行分批是指一臺機(jī)器一次可以同時(shí)加工B個(gè)工件.當(dāng)B ≥ n時(shí),我們稱該分批為無界平行批.當(dāng)Bn時(shí),我們稱它為有界平行批.其中n表示工件數(shù)目.在這里工件是按時(shí)到達(dá)的(即當(dāng)有工件出現(xiàn)時(shí),我們可以選擇立即加工或等待),且所有工件的加工長度都相同.目標(biāo)函數(shù)是最小化所有工件被運(yùn)輸完成的時(shí)間.我們假定有充分多的運(yùn)輸工具.即工件一旦完工便可被運(yùn)輸.對于工件具有嵌套加工集的情形,我們分別討論了批容量有界和批容量無界兩種情況.其中嵌套的定義為:對任意兩個(gè)工件J和Jj的加工集Mi和Mj有Mi(?)Mj或Mj(?)Mi或Mi(?)Mj=(?)當(dāng)批容量無界時(shí),可用三參數(shù)法表示為Pm|Mj(nested),pj=,p,qj,P-batch,B ≥ n,online|Lmax.我們給出了競爭比為(?)的最好可能的在線算法.當(dāng)批容量有界時(shí),我們考慮運(yùn)輸時(shí)間有如下限制:對任意兩個(gè)工件Ji和Jj的加工集M和Mj,若Mi(?)Mj,則有qi≥qj成立.對Pm|Mj(nested),pj=p,rj,qj,P-ba]ch,Bn,Online|Lmax,我們給出競爭比為(?)的最好可能的在線算法.另外,我們考慮了工件具有分層加工集(即任意兩個(gè)工件的加工集具有包含與被包含的關(guān)系)的情形,即問題Pm|Mj(GOS),pj =p,rj,qj,P-batch,5n,online|Lmax.此處運(yùn)輸時(shí)間的限制于第三節(jié)中的限制相同.當(dāng)B ≥ 2時(shí),問題的在線算法的競爭比的下界也是(?),上述嵌套情形的算法對該問題亦是最好可能的.當(dāng)B = 1時(shí),我們證明該問題的下界是3/2,同時(shí)給出競爭比為3/2的最好可能的在線算法.在本文第三章中,我們研究了 m臺恒同機(jī)上工件長度在固定區(qū)間內(nèi)取值的在線排序問題,且工件具有兩層加工集(即g = 2).所有工件的加工長度屬于[1,β](β1).目標(biāo)函數(shù)是最大化最小機(jī)器裝載量,用三參數(shù)表示法表示為P|GOS(q = 2),pj ∈1l,β],online,over-list|Cnmin.這里的工件是按順序到達(dá)的,只有當(dāng)前已經(jīng)到達(dá)的工件被安排之后,下一個(gè)工件才會到達(dá).工件到達(dá)之后會被立即安排.在本章中機(jī)器被分為兩層.第一層機(jī)器可以加工所有的工件,但第二層機(jī)器只能加工特定的工件.我們給出了競爭比為1+kβ的最好可能的在線算法,其中= 1或k = m-1.其中k表示第一層機(jī)器的數(shù)目.
【學(xué)位授予單位】：鄭州大學(xué)
【學(xué)位級別】：碩士
【學(xué)位授予年份】：2018
【分類號】：O223

【相似文獻(xiàn)】

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

1 韓飛;;高中數(shù)學(xué)一道數(shù)列典型題解法的探究[J];數(shù)學(xué)學(xué)習(xí)與研究;2016年23期

2 豆俊梅;孫彩賢;;單機(jī)排序問題的研究[J];數(shù)學(xué)學(xué)習(xí)與研究;2017年24期

3 胡覺亮;楊佳雯;蘇曉彤;董建明;;機(jī)器帶周期性維護(hù)時(shí)段的加工與運(yùn)輸協(xié)同排序問題[J];浙江理工大學(xué)學(xué)報(bào)(自然科學(xué)版);2016年06期

4 仲維亞;馬曉茹;;帶有運(yùn)輸且加工具有靈活性的無等待流水作業(yè)排序問題[J];運(yùn)籌學(xué)學(xué)報(bào);2016年04期

5 隋楠;羅成新;;具有維護(hù)活動及公共工期的加工時(shí)間依賴資源的單機(jī)排序問題[J];沈陽航空航天大學(xué)學(xué)報(bào);2016年06期

6 林浩;何程;;關(guān)于工期分配與加權(quán)誤工數(shù)的雙指標(biāo)排序問題（英文）[J];工程數(shù)學(xué)學(xué)報(bào);2017年01期

7 趙傳立;張蕾;;帶有交貨期窗口和加工時(shí)間可控的排序問題[J];沈陽師范大學(xué)學(xué)報(bào)(自然科學(xué)版);2016年04期

8 王申重;杜海龍;;具有學(xué)習(xí)效應(yīng)和遺忘效應(yīng)的單機(jī)排序問題研究[J];棗莊學(xué)院學(xué)報(bào);2017年02期

9 陳蕾;張安;陳永;陳光亭;;資源定時(shí)投放的單機(jī)排序問題[J];杭州電子科技大學(xué)學(xué)報(bào)(自然科學(xué)版);2017年02期

10 竇文卿;范靜;;一類資源費(fèi)用可變的平行機(jī)排序問題[J];上海第二工業(yè)大學(xué)學(xué)報(bào);2017年02期

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

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

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

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

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

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

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

7 胡榮;呂緒華;;3TMF排序問題的計(jì)算復(fù)雜性及分支定界法[A];中國運(yùn)籌學(xué)會第八屆學(xué)術(shù)交流會論文集[C];2006年

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

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

10 吳翠連;;有尺寸的單機(jī)分批排序問題的近似算法[A];中國企業(yè)運(yùn)籌學(xué)[2011（1）][C];2011年

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

1 楊文波;淺談方位詞“東、西、南、北”的詞語排序問題[N];語言文字周報(bào);2018年

2 山東 趙玉勇;小博士編程[N];電腦報(bào);2004年

3 何靖;全國計(jì)算機(jī)應(yīng)用技術(shù)證書考試（NIT）[N];中國電腦教育報(bào);2003年

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

1 沈佳煜;不確定情形下若干排序問題的研究[D];南京理工大學(xué);2017年

2 高園;新型排序問題的計(jì)算復(fù)雜性研究[D];鄭州大學(xué);2018年

3 殷娜;依賴于資源分配的排序問題研究[D];上海大學(xué);2015年

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

5 王吉波;工件加工時(shí)間可變的現(xiàn)代排序問題[D];大連理工大學(xué);2005年

6 羅潤梓;平行機(jī)半在線排序問題[D];上海大學(xué);2005年

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

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

9 李文華;關(guān)于分批排序問題的研究[D];鄭州大學(xué);2006年

10 趙洪鑾;窗時(shí)排序問題中的最優(yōu)化算法研究[D];山東大學(xué);2007年

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

1 王穆清;同類機(jī)上的在線分批排序問題[D];曲阜師范大學(xué);2018年

2 王曉連;模糊數(shù)空間上的排序問題[D];杭州電子科技大學(xué);2018年

3 李丹;兩類資源受限的排序問題研究[D];杭州電子科技大學(xué);2018年

4 張潔;按外包工件個(gè)數(shù)不同折扣率的單機(jī)排序問題[D];鄭州大學(xué);2018年

5 周松濤;帶約束的單機(jī)雙代理排序問題[D];鄭州大學(xué);2018年

6 朱月娟;限選機(jī)器上的在線排序問題[D];鄭州大學(xué);2018年

7 孫振霞;機(jī)器具有不可用區(qū)間且工件可拒絕的排序問題[D];鄭州大學(xué);2018年

8 陳耀寧;與資源有關(guān)的多次維修和加工時(shí)間可變的排序問題研究[D];重慶師范大學(xué);2018年

9 孟凡曉;基于退化效應(yīng)的可拒絕分批排序問題[D];曲阜師范大學(xué);2018年

10 潘婷婷;帶資源、學(xué)習(xí)效應(yīng)、惡化效應(yīng)、維護(hù)活動和工期窗口的排序問題的研究[D];蘇州大學(xué);2018年

，

本文編號：2653034