29488.幾種特殊的平行機(jī)上具有前瞻區(qū)間的在線分批排序問題

1、AthesissubmittedtoZhengzhouUniversityforthedegreeofMasterSomeParallelKindsofOn—lineSchedulingonBatchMachineswithLookaheadByShuainaHuangSupervisor：ProfWenhuaLiOperationsResearchandCyberneticsSchoolofMathematicsandStatisti

2、csMay2014摘要在離線排序問題中，工件信息在排序之前已經(jīng)知道本文我們研究的是具有前瞻區(qū)間的按時在線(online—over—time)排序問題按時在線排序是指工件各種信息在加工之初并不清楚，而是隨著時間推移逐個到達(dá)之后才被了解工件按時在線到達(dá)，具有前瞻區(qū)間是指在時刻t在線算法能預(yù)見到時間區(qū)間(t，t岡內(nèi)到達(dá)的所有工件的信息不可相容的工件組是指屬于不同工件組的工件不能被安排在同一批中加工平行機(jī)在線排序是現(xiàn)代排序領(lǐng)域中的一類重要問題平

3、行機(jī)在線排序模型中共有m臺機(jī)器本文主要研究三類平行機(jī)上的在線排序問題研究模型用三參數(shù)法表示為：(1)P2[online，P—batch，鰳=1，b=00，p，3familyI％缸；(2)Pmlonline，P—batch，功=1，b=oo，p，ffamilylCm馘(其中，為偶數(shù))；(3)Pmlonline，p—batch，脅=1，b=00，盧IFm敞模型(1)的基本描述：在該問題中，我們研究在兩臺平行機(jī)上，具有前瞻區(qū)間的三個不相容工件

4、組的在線排序目標(biāo)函數(shù)是最小化最大完工時間在此模型中，所有工件的加工長度都是1其特點(diǎn)是工件的所有信息都是分階段逐步釋放給決策者，決策者只能根據(jù)已有的信息來做出排序決策在線算法的優(yōu)良程度通常用它的競爭比來衡量對問題1Ionline，P—batch，紡=1，b=∞，聲，twofamilyfGax付等人11】給出了一個競爭比Tv／雨3的最好可能在線算法在本文第二章中，我們先給出了問題的一個下界1a，其中Q是方程2Q2(1p)Q盧一2=0的正根并

5、提供了一個最好可能的在線算法模型(2)的基本描述：在該問題中，我們研究m臺平行機(jī)上具有前瞻區(qū)間的多個不相容工件組的在線排序，目標(biāo)函數(shù)是最小化最大完工時間平行批排序是一類重要的現(xiàn)代排序問題，在這種模型中，機(jī)器可以同時將無數(shù)個屬于同一工件組的工件作為一批進(jìn)行加工，但不同工件組不能放在同一批加工批容量有兩種不同的類型，一種是批容量有限，一種是批容量無限本文研究的是批容量無限的情形同一批中的工件具有相同的開工時間和完工時間一個批的加工時間定義為