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

1、AthesissubmittedtoZhengzhouUniversityforthedegreeofMasterSomeParallelKindsofOn—lineSchedulingonBatchMachineswithLookaheadByShuainaHuangSupervisor：ProfWenhuaLiOperationsResearchandCyberneticsSchoolofMathematicsandStatisti

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

3、行機(jī)在線排序模型中共有m臺(tái)機(jī)器本文主要研究三類(lèi)平行機(jī)上的在線排序問(wèn)題研究模型用三參數(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)的基本描述：在該問(wèn)題中，我們研究在兩臺(tái)平行機(jī)上，具有前瞻區(qū)間的三個(gè)不相容工件

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

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