【摘要】：排序論是運(yùn)籌學(xué)中最有活力的領(lǐng)域之一,大量不同機(jī)器環(huán)境下的排序模型已經(jīng)被學(xué)者們廣泛研究.我們根據(jù)工件的不同特點(diǎn),排序問(wèn)題分為離線排序和在線排序.在離線排序問(wèn)題中,工件的所有信息是在排序之前就已經(jīng)知道的.而本文所要研究的是按時(shí)在線排序問(wèn)題,也就是指工件的到達(dá)時(shí)刻,加工時(shí)間等只有在到達(dá)之后才被了解,決策者只能根據(jù)當(dāng)前已到達(dá)工件的信息來(lái)進(jìn)行排序決策.在LKβ模型下,在時(shí)刻t,在線算法能預(yù)見(jiàn)到將在時(shí)間區(qū)間(t,t + β]內(nèi)到達(dá)的所有工件的信息;不可相容的工件組是指屬于不同組的工件不能被安排在同一批中加工.分批排序模型按分批方式的不同分兩大類(lèi):平行分批排序模型和繼列分批排序模型.平行分批排序是指多個(gè)工件可以放在同一批在一臺(tái)機(jī)器上同時(shí)開(kāi)工同時(shí)完工,每一批的加工時(shí)間等于該批中工件的最大加工時(shí)間.繼列分批排序是指一批中的工件是相繼加工的,它們的完工時(shí)間等于批中最后一個(gè)工件的完工時(shí)間.每批的加工時(shí)間等于該批中所有工件的加工時(shí)間之和.批容量b是指每批至多可以加工b工件,一般分為有界和無(wú)界兩種情形.本文我們研究的是幾種特殊的在線分批排序問(wèn)題,研究的模型用三參數(shù)法表示記為:(1) 1|online, p-batch,pj = 1,b = ∞, LKβ|Dmax(= maxj{Cj + qj});(2) 1|online,p-batch,pj = 1,b = ∞,f-family|Dmax(= maxj{Cj + qi});(3) Pm|on-line, s-batch|Fmax(= maxj{Cj - rj})模型(1)的基本描述:在該問(wèn)題中,我們研究的是具有前瞻區(qū)間和運(yùn)輸時(shí)間的單機(jī)無(wú)界平行分批在線排序問(wèn)題,工件具有相同的加工時(shí)間,目標(biāo)是最小化最大運(yùn)輸完工時(shí)間.對(duì)于我們研究的模型,在本文第二章中給出了該問(wèn)題的一個(gè)在線算法:當(dāng)0 ≤ β ≤1/6時(shí),該算法是競(jìng)爭(zhēng)比為1+α*的最好可能的在線算法,其中α*= α是方程α2 + (β + 1)α +β-1 = 0的正根;當(dāng)β 1/6,該算法的競(jìng)爭(zhēng)比為3/2.模型(2)的基本描述:在該問(wèn)題中,我們研究的是具有f個(gè)互不相容工件組和運(yùn)輸時(shí)間的單機(jī)無(wú)界平行分批在線排序問(wèn)題,工件具有相同的加工時(shí)間,目標(biāo)是最小化最大運(yùn)輸完工時(shí)間.對(duì)于我們研究的模型.在本文第三章中給出了一個(gè)競(jìng)爭(zhēng)比為1 + αf的最好可能的在線算法,其中αf是方程fαf2 + αf - f = 0的正根.模型(3)的基本描述:我們討論了最小化最大流程時(shí)間的繼列分批在線排序問(wèn)題.在本文第四章中證明了當(dāng)m ≥ 2時(shí),問(wèn)題Pm|on-line,s-batch|Fmax不存在競(jìng)爭(zhēng)比小于1 + αm的在線算法,其中αm為方程αm2 + (m+ 1)αm = 1的正根;當(dāng)m = 1時(shí),問(wèn)題1|on-line,s-batch|Fnax不存在競(jìng)爭(zhēng)比小于1 + α的在線算法,其中α = (?);同時(shí)我們也證明了問(wèn)題Pm|on-line,s-batch,pj=1|Fmax不存在競(jìng)爭(zhēng)比小于1 +βm的在線算法,其中βm為方程(s + 1)βm2+(ms + m + s + 2)βm - s = 0 (βm 0)的正根.在本章4.3節(jié)中我們嘗試給出m = 1時(shí)的一個(gè)在線算法H1,并證明該算法的競(jìng)爭(zhēng)比為2,說(shuō)明了這個(gè)算法的界是緊的,在m ≥ 2時(shí),在線算法就變得較為復(fù)雜,目前無(wú)法得知比2更好的在線算法.
[Abstract]:......
【學(xué)位授予單位】：鄭州大學(xué)
【學(xué)位級(jí)別】：碩士
【學(xué)位授予年份】：2017
【分類(lèi)號(hào)】：O223

【參考文獻(xiàn)】

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

1 楊素芳;李文華;;具有前瞻區(qū)間的兩個(gè)工件組單機(jī)在線排序問(wèn)題[J];運(yùn)籌學(xué)學(xué)報(bào);2012年02期

2 胡覺(jué)亮;張瑋虹;蔣義偉;;生產(chǎn)和運(yùn)輸時(shí)間具有一致性的單機(jī)在線最優(yōu)算法[J];浙江理工大學(xué)學(xué)報(bào);2010年05期

3 唐國(guó)春;;排序問(wèn)題的定義、分類(lèi)和在國(guó)內(nèi)的某些研究進(jìn)展[J];運(yùn)籌學(xué)雜志;1990年02期

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

1 田記;多臺(tái)平行批處理機(jī)在線排序和帶有運(yùn)輸時(shí)間的在線排序[D];鄭州大學(xué);2009年

，

本文編號(hào)：2437397