单资源条件下具有部分延展性的地面服务中的调度问题

单资源条件下具有部分延展性的地面服务中的调度问题许保光，侯思祥，池宏中国科学院科技政策与管理科学研究所海军装备研究院战略与政策研究所摘要•本文根据实际地面作业背景，提出了一个单资源分配模型。在一定时间范围内，具有件工作和个同样的资源，每件工作有一个到达时刻，一个要求完工期限；几种可能的工作方式及其相应的处理时间。本文以极小化最大的延误时间为目标给出了一个多项式算法。基于对一个简单的情况的分析，和最优解比较其差小于等于其中为单工件需求资源数量的最大值为单工件处理时间的最大值。maxmax121busyfTpmmaxfmaxp问题背景问题背景•本文考虑的问题来源于航空地面作业系统，类似的问题也存在于多个应用领域，如计算机的共用内存的分配问题，运输系统中的车辆分配问题。在航空运输中，航班在某时刻降落在一个机场，等待地面服务系统完成各种作业后，如清扫、装货、装食品、旅客上下等工序，在某个预定时刻起飞。在这段时间怎样对航班的服务进行安排，有效利用资源是每个管理人员考虑的问题。•排序问题中的延展性（malleable）是指某工件的处理时间长短和使用的资源数量有关系。对Boeing737航班清洁工作的可以使用的人数可以为6人、8人和12人三种情况。相关文献•早期的文献讨论具有释放时间和完工期限有Baker&Su[1]，Grabowski[8]，McMahon&Florian[13]，他们把完工期限(due-date)的限制转换成一个完工后需要的清理的时间限制(releasetail)或者是运输时间(deliverytime)的要求，要求是总完工时间最小。•早期的对该类问题的算法的有效性的研究多关注于单加工机器问题，后来Carlier[4]讨论了多个相同机器的加工问题，他们的研究的模型和本文的不同之处在于，他们要求同一时刻每台机器能且只能加工一个工件，本文模型要求多个资源同时处理一个工件。相关文献•关于资源约束下的调度问题，有时叫做多处理机调度(MultiprocessorTaskScheduling)[5,10]或并行任务调度(ParallelJobScheduling)[12,15]。•和资源约束下的调度问题研究密切相关的一个领域是，如果我们把加工工件时所用的资源作为1-维，加工的时间作为1-维，该类问题可以看成一个2-维装箱问题，但是二者之间具有不同点，因为2-维装箱中每个货物将占有一个固定的长方形面积，这相当于调度工作中把机器编上序号，每次只能用序号相邻的一段。问题描述•工件数n，资源数量m。为m种资源需求量的状态集合，其中表示需要i个资源。每件工件具有一个四元组，这里ri是工件i的到达时间（释放时间）；di是i完工限制时间，其中，是对应于工作状态集合处理时间集合。我们赋予每工件一个清理时间(releasetail)，其中。•目标：最小化最大延误，这里等价于极小化最大的加工时间长度。12{,,,}mFfffif{,,,}iiiirdPF1,,{,,}kiiiiiPpp1,,{,,}kiiiiiFffFiiqKdmaxiIiKdmaxmaxiIiLLiiiiLtpd算法一些下界•论断1是最优工作时间长度的一个下界。•把的工件按照到达的时刻由小到大的顺序排列，记为前面的s个工件的到达时间，满足且。把的工件按照由小到大的顺序排列，记为前面的t个工件，•满足且•论断2是最优工作时间长度的一个下界。()min()/miniJiiiiJiiJGJrfpmq12,,,siiirrrjq12,,,tjjiqqqmfffsiii21mfffsiii121mffftjjj21mffftjjj1211211()1/{}stiiiiijjjiJGJmrrrfpqqq主要结论参考文献：1.K.R.BakerandZ.S.Su,Sequencingwithduedatesandearlystarttimestominimizetardiness,NavalResearchLogisticsQuarterly21,171-176,1974.2.A.Barnoy,S.Guha,J.NaorandB.Schieber,Approximtingthethroughputofmultiplemachinesinreal-timescheduling,SIAMJ.Computing31,331-352,2001.3.L.Bianco,J.Blazewicz,P.Dell'OlmoandM.Drozdowski,Preemptivemulti-processortaskschedulingwithreleaseandtimewindows,AnnalsofOperationsResearch70(1997),43-55.4.J.Carlier,Theone-machinesequencingproblem,EuropeanJournalofOperationResearch,11,42-47,1982.5.J.Carlier,Schedulingjobswithreleasedatesandtailsonidenticalmachinestominimizethemakespan,EuropeanJournalofOperationResearch29,298-305,19876.M.Drozdowski,Schedulingmultiprocessortasks:anoverview(1996)7.M.X.Goemans,M.Queyranne,A.S.Schulz,M.Skutella,Y.G.Wang,SingleMachineSchedulingwithReleaseDates,SIAMJournalonDiscreteMathematics,15(2),165-192,2002.8.R.GopalanandKalyanT.Talluri,Mathematicalmodelsinairlinescheduleplanning:ASurvey,AnnalsofOperationsResearch76,9.J.Grabowski,E.SkubalskaandC.Smutnicki,Onfolw-shopwithreleaseandduedatestominimizemaximumlateness,JournaloftheOperationalResearchSociety34,615-620,1983.10.C.Imreh,Onlinestrippackingwithmodifiableboxes,(2001)11.M.Kurtulus,MultiprocessorTaskScheduling(1999)12.C.Y.Lee,LeiLeiandM.Pinedo,CurrenttrendsinDeterministicscheduling,AnnalsofOperationsResearch70,1-41,1997.13.LiKeqin,Analysisofanapproximationalgorithmforschedulingindependentparalleltasks,DiscreteMathematicsandTheoreticalComputerScience3,155-166,1999.14.G.B.McMahonandM.Florian,Onschedulingwithreadytimesandduedatestominimizemaximumlateenss,OperationResearch23,475-482,1975.15.C.N.Potts,Analysisofaheuristicforonemachinewithreleasedatesanddeliverytimes,OperationResearch28,1436-1441,1980.16.J.M.J.SchuttenandLeussink,R.A.M.,Parallelmachineschedulingwithreleasedates,duedatesandfamilysetuptimes.Internationaljournalofproductioneconomics46,119-126,1996