單資源條件下具有部分延展性的地面服務(wù)中的調(diào)度問題

單資源條件下具有部分延展性的地面服務(wù)中的調(diào)度問題許保光，侯思祥，池宏中國科學(xué)院科技政策與管理科學(xué)研究所海軍裝備研究院戰(zhàn)略與政策研究所摘要本文根據(jù)實(shí)際地面作業(yè)背景，提出了一個(gè)單資源分配模型。在一定時(shí)間范圍內(nèi)，具有件工作和個(gè)同樣的資源，每件工作有一個(gè)到達(dá)時(shí)刻，一個(gè)要求完工期限；幾種可能的工作方式及其相應(yīng)的處理時(shí)間。本文以極小化最大的延誤時(shí)間為目標(biāo)給出了一個(gè)多項(xiàng)式算法?；趯σ粋€(gè)簡單的情況的分析，和最優(yōu)解比較其差小于等于

其中為單工件需求資源數(shù)量的最大值

為單工件處理時(shí)間的最大值。問題背景問題背景本文考慮的問題來源于航空地面作業(yè)系統(tǒng)，類似的問題也存在于多個(gè)應(yīng)用領(lǐng)域，如計(jì)算機(jī)的共用內(nèi)存的分配問題，運(yùn)輸系統(tǒng)中的車輛分配問題。在航空運(yùn)輸中，航班在某時(shí)刻降落在一個(gè)機(jī)場，等待地面服務(wù)系統(tǒng)完成各種作業(yè)后，如清掃、裝貨、裝食品、旅客上下等工序，在某個(gè)預(yù)定時(shí)刻起飛。在這段時(shí)間怎樣對航班的服務(wù)進(jìn)行安排，有效利用資源是每個(gè)管理人員考慮的問題。排序問題中的延展性（malleable）是指某工件的處理時(shí)間長短和使用的資源數(shù)量有關(guān)系。對Boeing737航班清潔工作的可以使用的人數(shù)可以為6人、8人和12人三種情況。相關(guān)文獻(xiàn)早期的文獻(xiàn)討論具有釋放時(shí)間和完工期限有Baker&Su[1]，Grabowski[8]，McMahon&Florian[13]，他們把完工期限(due-date)的限制轉(zhuǎn)換成一個(gè)完工后需要的清理的時(shí)間限制(releasetail)或者是運(yùn)輸時(shí)間(deliverytime)的要求，要求是總完工時(shí)間最小。早期的對該類問題的算法的有效性的研究多關(guān)注于單加工機(jī)器問題，后來Carlier[4]討論了多個(gè)相同機(jī)器的加工問題，他們的研究的模型和本文的不同之處在于，他們要求同一時(shí)刻每臺(tái)機(jī)器能且只能加工一個(gè)工件，本文模型要求多個(gè)資源同時(shí)處理一個(gè)工件。相關(guān)文獻(xiàn)關(guān)于資源約束下的調(diào)度問題，有時(shí)叫做多處理機(jī)調(diào)度(MultiprocessorTaskScheduling)[5,10]或并行任務(wù)調(diào)度(ParallelJobScheduling)[12,15]。和資源約束下的調(diào)度問題研究密切相關(guān)的一個(gè)領(lǐng)域是，如果我們把加工工件時(shí)所用的資源作為1-維，加工的時(shí)間作為1-維，該類問題可以看成一個(gè)2-維裝箱問題，但是二者之間具有不同點(diǎn)，因?yàn)?-維裝箱中每個(gè)貨物將占有一個(gè)固定的長方形面積，這相當(dāng)于調(diào)度工作中把機(jī)器編上序號，每次只能用序號相鄰的一段。問題描述工件數(shù)n，資源數(shù)量m。為m種資源需求量的狀態(tài)集合，其中表示需要i個(gè)資源。每件工件具有一個(gè)四元組，這里ri是工件i的到達(dá)時(shí)間（釋放時(shí)間）；di是i完工限制時(shí)間，其中，是對應(yīng)于工作狀態(tài)集合處理時(shí)間集合。我們賦予每工件一個(gè)清理時(shí)間(releasetail)，其中。目標(biāo)：最小化最大延誤，這里等價(jià)于極小化最大的加工時(shí)間長度。算法一些下界論斷1

是最優(yōu)工作時(shí)間長度的一個(gè)下界。把的工件按照到達(dá)的時(shí)刻由小到大的順序排列，記為前面的s個(gè)工件的到達(dá)時(shí)間，滿足且。把的工件按照由小到大的順序排列，記為前面的t個(gè)工件，滿足且論斷2

是最優(yōu)工作時(shí)間長度的一個(gè)下界。主要結(jié)論

參考文獻(xiàn)：K.R.BakerandZ.S.Su,Sequencingwithduedatesandearlystarttimestominimizetardiness,NavalResearchLogisticsQuarterly21,171-176,1974.A.Barnoy,S.Guha,J.NaorandB.Schieber,Approximtingthethroughputofmultiplemachinesinreal-timescheduling,SIAMJ.Computing31,331-352,2001.L.Bianco,J.Blazewicz,P.Dell'OlmoandM.Drozdowski,Preemptivemulti-processortaskschedulingwithreleaseandtimewindows,AnnalsofOperationsResearch70(1997),43-55.J.Carlier,Theone-machinesequencingproblem,EuropeanJournalofOperationResearch,11,42-47,1982.J.Carlier,Schedulingjobswithreleasedatesandtailsonidenticalmachinestominimizethemakespan,EuropeanJournalofOperationResearch29,298-305,1987M.Drozdowski,Schedulingmultiprocessortasks:anoverviewhttp:///drozdowski96scheduling.html(1996)M.X.Goemans,M.Queyranne,A.S.Schulz,M.Skutella,Y.G.Wang,SingleMachineSchedulingwithReleaseDates,SIAMJournalonDiscreteMathematics,15(2),165-192,2002.R.GopalanandKalyanT.Talluri,Mathematicalmodelsinairlinescheduleplanning:ASurvey,AnnalsofOperationsResearch76,J.Grabowski,E.SkubalskaandC.Smutnicki,Onfolw-shopwithreleaseandduedatestominimizemaximumlateness,JournaloftheOperationalResearchSociety34,615-620,1983.C.Imreh,Onlinestrippackingwithmodifiableboxes,/484068.html,OperationResearchLetters,66,79-86,(2001)M.Kurtulus,

MultiprocessorTaskScheduling/kurtulus99multi-processor.html(1999)

C.Y.Lee,LeiLeiandM.Pinedo,CurrenttrendsinDeterministicscheduling,AnnalsofOperationsResearch70,1-41,1997.LiKeqin,Analysisofanapproximationalgorithmforschedulingindependentparalleltasks,DiscreteMathematicsandTheoreticalComputerScience3,155-166,1999.G.B.McMahonandM.Florian,Onschedulingwithreadytimesandduedatestominimizemaximumlateenss,OperationResearch23,475-482,1975.C.N.Potts,Analysisofaheuristicforonemachinewithreleasedatesanddeliverytimes,OperationResearch28,14