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

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,单资源条件下具有部分延展性的地面服务中的调度问题,许保光，侯思祥，池宏,中国科学院科技政策与管理科学研究所,海军装备研究院战略与政策研究所,摘要,本文根据实际地面作业背景，提出了一个单资源分配模型在一定时间范围内，具有件工作和个同样的资源，每件工作有一个到达时刻，一个要求完工期限；几种可能的工作方式及其相应的处理时间本文以极小化最大的延误时间为目标给出了一个多项式算法基于对一个简单的情况的分析，和最优解比较其差小于等于其中 为单工件需求资源数量的最大值 为单工件处理时间的最大值问题背景,问题背景,本文考虑的问题来源于航空地面作业系统，类似的问题也存在于多个应用领域，如计算机的共用内存的分配问题，运输系统中的车辆分配问题在航空运输中，航班在某时刻降落在一个机场，等待地面服务系统完成各种作业后，如清扫、装货、装食品、旅客上下等工序，在某个预定时刻起飞在这段时间怎样对航班的服务进行安排，有效利用资源是每个管理人员考虑的问题排序问题中的延展性（malleable）是指某工件的处理时间长短和使用的资源数量有关系。

对Boeing 737航班清洁工作的可以使用的人数可以为6人、8人和12人三种情况相关文献,早期的文献讨论具有释放时间和完工期限有Baker&Su1，Grabowski8，McMahon&Florian13，他们把完工期限(due-date)的限制转换成一个完工后需要的清理的时间限制(release tail)或者是运输时间(delivery time)的要求，要求是总完工时间最小早期的对该类问题的算法的有效性的研究多关注于单加工机器问题，后来Carlier4讨论了多个相同机器的加工问题，他们的研究的模型和本文的不同之处在于，他们要求同一时刻每台机器能且只能加工一个工件，本文模型要求多个资源同时处理一个工件相关文献,关于资源约束下的调度问题，有时叫做多处理机调度(Multiprocessor Task Scheduling)5,10或并行任务调度(Parallel Job Scheduling)12,15和资源约束下的调度问题研究密切相关的一个领域是，如果我们把加工工件时所用的资源作为1-维，加工的时间作为1-维，该类问题可以看成一个2-维装箱问题，但是二者之间具有不同点，因为2-维装箱中每个货物将占有一个固定的长方形面积，这相当于调度工作中把机器编上序号，每次只能用序号相邻的一段。

问题描述,工件数n，资源数量m为m种资源需求量的状态集合，其中 表示需要i个资源每件工件具有一个四元组 ，这里r,i,是工件i的到达时间（释放时间）；d,i,是i完工限制时间，其中，是对应于工作状态集合 处理时间集合我们赋予每工件一个清理时间(release tail)，其中 目标：最小化最大延误 ，这里 等价于极小化最大的加工时间长度算法,一些下界,论断1,是最优工作时间长度的一个下界把的工件按照到达的时刻由小到大的顺序排列，记 为前面的s个工件的到达时间，满足 且 把的工件按照 由小到大的顺序排列，记 为前面的t个工件，,满足 且,论断 2,是最优工作时间长度的一个下界主要结论,参考文,献,献：,K.R.Baker and Z.S.Su,Sequencing with due dates and early start times to minimize tardiness,Naval Research Logistics Quarterly 21,171-176,1974.,A.Barnoy,S.Guha,J.Naor and B.Schieber,Approximting the throughput of multiple machines in real-time scheduling,SIAM J.Computing 31,331-352,2001.,L.Bianco,J.Blazewicz,P.DellOlmo and M.Drozdowski,Preemptive multi-processor task scheduling with release and time windows,Annals of Operations Research 70(1997),43-55.,J.Carlier,The one-machine sequencing problem,European Journal of Operation Research,11,42-47,1982.,J.Carlier,Scheduling jobs with release dates and tails on identical machines to minimize the makespan,European Journal of Operation Research 29,298-305,1987,M.Drozdowski,Scheduling multiprocessor tasks:an overview http:/ Machine Scheduling with Release Dates,SIAM Journal on Discrete Mathematics,15(2),165-192,2002.,R.Gopalan and Kalyan T.Talluri,Mathematical models in airline schedule planning:A Survey,Annalsof Operations Research 76,J.Grabowski,E.Skubalska and C.Smutnicki,On folw-shop with release and due dates to minimize maximum lateness,Journal of the Operational Research Society 34,615-620,1983.,C.Imreh,Online strip packing with modifiable boxes,http:/ Research Letters,66,79-86,(2001),M.Kurtulus,Multiprocessor Task Scheduling http:/ Lei and M.Pinedo,Current trends in Deterministic scheduling,Annals of Operations Research 70,1-41,1997.,Li Keqin,Analysis of an approximation algorithm for scheduling independent parallel tasks,Discrete Mathematics and Theoretical Computer Science 3,155-166,1999.,G.B.McMahon and M.Florian,On scheduling with ready times and due dates to minimize maximum lateenss,Operation Research 23,475-482,1975.,C.N.Potts,Analysis of a heuristic for one machine with release dates and delivery times,Operation Research 28,1436-1441,1980.,J.M.J.Schutten and Leussink,R.A.M.,Parallel machine scheduling with release dates,due dates and family setup times.International journal of production economics 46,119-126,1996,9,、静,夜,夜四,无,无邻,，,，荒,居,居旧,业,业贫,。

12月-2212月-22,Saturday,December 31,2022,10,、雨中,黄,黄叶树,，,，灯下,白,白头人,05:11:5205:11:5205:11,12/31/2022 5:11:52AM,11,、以,我,我独,沈,沈久,，,，愧,君,君相,见,见频,12,月,月-2205:11:5205:11,Dec-2231-Dec-22,12,、故,人,人江,海,海别,，,，几,度,度隔,山,山川,05:11:5205:11:5205:11,Saturday,December31,2022,13,、乍见,翻,翻疑梦,，,，相悲,各,各问年,12月-2212月-2205:11:5205:11:52,December31,2022,14,、他乡生,白,白发，旧,国,国见青山,31 十,二,二月 20225:11:52,上,上午05:11:5212月-22,15,、比不了得,就,就不比，得,不,不到的就不,要,要十二月 225:11,上,上午12月-2205:11,December 31,2022,16,、,行,行,动,动,出,出,成,成,果,果,，,，,工,工,作,作,出,出,财,财,富,富,。

2022/12/315:11:5205:11:52,31December2022,17,、做前,，,，能够,环,环视四,周,周；做,时,时，你,只,只能或,者,者最好,沿,沿着以,脚,脚为起,点,点的射,线,线向前,5:11:52 上,午,午5:11 上,午,午05:11:5212月-22,9,、没,有,有失,败,败，,只,只有,暂,暂时,停,停止,成,成功,！,！12,月,月-2212,月,月-22,Saturday,December31,2022,10,、很,多,多事,情,情努,力,力了,未,未必,有,有结,果,果，,但,但是,不,不努,力,力却,什,什么,改,改变,也,也没,有,有05:11:5205:11:5205:11,12/31/20225:11:52AM,11,、成功,就,就是日,复,复一日,那,那一点,点,点小小,努,努力的,积,积累12月-2205:11:5205:11,Dec-2231-Dec-22,12,、世间成事,，,，不求其绝,对,对圆满，留,一,一份不足，,可,可得无限完,美,美05:11:5205:11:5205:11,Saturday,December 31,2022,13,、不,知,知香,积,积寺,，,，数,里,里入,云,云峰,。

12,月,月-2212,月,月-2205:11:5305:11:53,December31,2022,14,、,意,意,志,志,坚,坚,强,强,的,的,人,人,能,能,把,把,世,世,界,界,放,放,在,在,手,手,中,中,像,像,泥,泥,块,块,一,一,样,样,任,任,意,意,揉,揉,捏,捏,31,十,十,二,二,月,月20225:11:53,上,上,午,午05:11:5312,月,月-22,15,、楚塞,三,三湘接,，,，荆门,九,九派通,十二月225:11 上,午,午12月-2205:11,December31,2022,16,、少年,十,十五二,十,十时，,步,步行夺,得,得胡马,骑,骑2022/12/31 5:11:5305:11:53,31December2022,17,、空山新雨,后,后，天气晚,来,来秋5:11:53 上午5:11,上,上午05:11:5312月-22,9,、杨柳散,和,和风，青,山,山澹吾虑,12月-2212月-22,Saturday,December 31,2022,10,、阅读一,切,切好书如,同,同。