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

1、單資源條件下具有部分延展性的地面效力中的調(diào)度問題許保光，侯思祥，池宏中國科學(xué)院科技政策與管文科學(xué)研討所海軍配備研討院戰(zhàn)略與政策研討所.摘要本文根據(jù)實踐地面作業(yè)背景，提出了一個單資源分配模型。在一定時間范圍內(nèi)，具有件任務(wù)和個同樣的資源，每件任務(wù)有一個到達(dá)時辰，一個要求完工期限；幾種能夠的任務(wù)方式及其相應(yīng)的處置時間。本文以極小化最大的延誤時間為目的給出了一個多項式算法?；趯σ粋€簡單的情況的分析，和最優(yōu)解比較其差小于等于其中 為單工件需求資源數(shù)量的最大值 為單工件處置時間的最大值。 .問題背景.問題背景本文思索的問題來源于航空地面作業(yè)系統(tǒng)，類似的問題也存在于多個運用領(lǐng)域，如計算機的共用內(nèi)存的分配問

2、題，運輸系統(tǒng)中的車輛分配問題。在航空運輸中，航班在某時辰降落在一個機場，等待地面效力系統(tǒng)完成各種作業(yè)后，如清掃、裝貨、裝食品、旅客上下等工序，在某個預(yù)定時辰起飛。在這段時間怎樣對航班的效力進(jìn)展安排，有效利用資源是每個管理人員思索的問題。 排序問題中的延展性malleable是指某工件的處置時間長短和運用的資源數(shù)量有關(guān)系。對Boeing 737航班清潔任務(wù)的可以運用的人數(shù)可以為6人、8人和12人三種情況。 .相關(guān)文獻(xiàn)早期的文獻(xiàn)討論具有釋放時間和完工期限有Baker & Su1，Grabowski8，McMahon & Florian13，他們把完工期限(due-date)的限制轉(zhuǎn)換成一個完工后需

3、求的清理的時間限制(release tail )或者是運輸時間(delivery time)的要求，要求是總完工時間最小。早期的對該類問題的算法的有效性的研討多關(guān)注于單加工機器問題，后來Carlier4討論了多個一樣機器的加工問題，他們的研討的模型和本文的不同之處在于，他們要求同一時辰每臺機器能且只能加工一個工件，本文模型要求多個資源同時處置一個工件。 .相關(guān)文獻(xiàn)關(guān)于資源約束下的調(diào)度問題，有時叫做多處置機調(diào)度(Multiprocessor Task Scheduling)5,10或并行義務(wù)調(diào)度(Parallel Job Scheduling)12,15。和資源約束下的調(diào)度問題研討親密相關(guān)的一個

4、領(lǐng)域是，假設(shè)我們把加工工件時所用的資源作為1-維，加工的時間作為1-維，該類問題可以看成一個2-維裝箱問題，但是二者之間具有不同點，由于2-維裝箱中每個貨物將占有一個固定的長方形面積，這相當(dāng)于調(diào)度任務(wù)中把機器編上序號，每次只能用序號相鄰的一段 。.問題描畫工件數(shù)n，資源數(shù)量m。 為m種資源需求量的形狀集合，其中 表示需求i個資源。每件工件具有一個四元組 ，這里ri是工件i的到達(dá)時間釋放時間；di是i完工限制時間，其中， 是對應(yīng)于任務(wù)形狀集合 處置時間集合。我們賦予每工件一個清理時間(release tail)， 其中 。目的：最小化最大延誤 ，這里 等價于極小化最大的加工時間長度。 .算法.一

5、些下界結(jié)論1 是最優(yōu)任務(wù)時間長度的一個下界。把的工件按照到達(dá)的時辰由小到大的順序陳列，記 為前面的s個工件的到達(dá)時間，滿足 且 。 把的工件按照 由小到大的順序陳列， 記 為前面的t個工件，滿足 且結(jié)論 2 是最優(yōu)任務(wù)時間長度的一個下界。.主要結(jié)論 .參考文獻(xiàn)：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