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

1、单资源条件下具有部分延展性的地面效力中的调度问题许保光，侯思祥，池宏中国科学院科技政策与管文科学研讨所海军配备研讨院战略与政策研讨所.摘要本文根据实践地面作业背景，提出了一个单资源分配模型。在一定时间范围内，具有件任务和个同样的资源，每件任务有一个到达时辰，一个要求完工期限；几种能够的任务方式及其相应的处置时间。本文以极小化最大的延误时间为目的给出了一个多项式算法。基于对一个简单的情况的分析，和最优解比较其差小于等于其中 为单工件需求资源数量的最大值 为单工件处置时间的最大值。 .问题背景.问题背景本文思索的问题来源于航空地面作业系统，类似的问题也存在于多个运用领域，如计算机的共用内存的分配问

2、题，运输系统中的车辆分配问题。在航空运输中，航班在某时辰降落在一个机场，等待地面效力系统完成各种作业后，如清扫、装货、装食品、旅客上下等工序，在某个预定时辰起飞。在这段时间怎样对航班的效力进展安排，有效利用资源是每个管理人员思索的问题。 排序问题中的延展性malleable是指某工件的处置时间长短和运用的资源数量有关系。对Boeing 737航班清洁任务的可以运用的人数可以为6人、8人和12人三种情况。 .相关文献早期的文献讨论具有释放时间和完工期限有Baker & Su1，Grabowski8，McMahon & Florian13，他们把完工期限(due-date)的限制转换成一个完工后需

3、求的清理的时间限制(release tail )或者是运输时间(delivery time)的要求，要求是总完工时间最小。早期的对该类问题的算法的有效性的研讨多关注于单加工机器问题，后来Carlier4讨论了多个一样机器的加工问题，他们的研讨的模型和本文的不同之处在于，他们要求同一时辰每台机器能且只能加工一个工件，本文模型要求多个资源同时处置一个工件。 .相关文献关于资源约束下的调度问题，有时叫做多处置机调度(Multiprocessor Task Scheduling)5,10或并行义务调度(Parallel Job Scheduling)12,15。和资源约束下的调度问题研讨亲密相关的一个

4、领域是，假设我们把加工工件时所用的资源作为1-维，加工的时间作为1-维，该类问题可以看成一个2-维装箱问题，但是二者之间具有不同点，由于2-维装箱中每个货物将占有一个固定的长方形面积，这相当于调度任务中把机器编上序号，每次只能用序号相邻的一段 。.问题描画工件数n，资源数量m。 为m种资源需求量的形状集合，其中 表示需求i个资源。每件工件具有一个四元组 ，这里ri是工件i的到达时间释放时间；di是i完工限制时间，其中， 是对应于任务形状集合 处置时间集合。我们赋予每工件一个清理时间(release tail)， 其中 。目的：最小化最大延误 ，这里 等价于极小化最大的加工时间长度。 .算法.一

5、些下界结论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

6、. 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 (19

7、97), 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, Schedulin

8、g multiprocessor tasks: an overview citeseer.nj.nec/ drozdowski96scheduling.html(1996)M.X. Goemans, M. Queyranne, A.S. Schulz, M. Skutella, Y.G. Wang, Single Machine Scheduling with Release Dates, SIAM Journal on Discrete Mathematics, 15(2), 165-192,2002.R. Gopalan and Kalyan T. Talluri, Mathematica

9、l 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 modif

10、iable boxes, citeseer.nj.nec/484068.html, Operation Research Letters, 66, 79-86, (2001)M. Kurtulus, Multiprocessor Task Scheduling citeseer.nj.nec/kurtulus99multi- processor.html (1999)C.Y. Lee, Lei Lei and M. Pinedo, Current trends in Deterministic scheduling, Annals of Operations Research 70, 1-41

11、, 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