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

【參考文獻】

相關期刊論文 前3條

1 楊素芳;李文華;;具有前瞻區(qū)間的兩個工件組單機在線排序問題[J];運籌學學報;2012年02期

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

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

相關博士學位論文 前1條

1 田記;多臺平行批處理機在線排序和帶有運輸時間的在線排序[D];鄭州大學;2009年

，

本文編號：2437397