带机器费用的排序问题的半在线算法
Semi-Online Algorithms for Scheduling with Machine Cost
-
摘要: 排序(又称为调度)问题是组合最优化领域中的一类重要问题,它在计算机系统控制,机器加工制造业,生产计划调度管理等方面有着广泛的实际应用背景,在理论上它又和算法设计与分析、计算复杂性理论密切相关。在经典排序理论中,根据在确定排序时了解的工件信息的多少,常将排序问题分为“在线”和“离线”两种。在在线问题中,工件一个个地到达,每个工件只有在到达后才知道它的信息,某工件加工方案一旦决定就不允许改变;在离线问题中,所有工件的信息都事先已知。但是事实上,在实际应用中,大量存在的问题是所谓“半在线”的,即所知道的工件信息介于在线和离线之间,或者说知道部分信息,且仍然要求工件加工方案一旦决定就不允许改变。 我们称求解在线(半在线)问题的算法为在线(半在线)算法。如何利用这些部分信息,设计出比在线算法更好的半在线算法是这类研究的核心问题。近几年来,半在线排序由于更加符合实际问题的应用背景,日益受到越来越多的重视。本文研究一个带机器费用半在线排序问题,其中已知总加工时间. 给定一个工件序列,每个工件都有非负的长度(即加工时间),并且必须分给机器加工. 开始时没有机器可使用,一旦工件被释放,算法必须决定是否购买新机器. 通过标准化所有工件长度和机器费用,我们可假设购买一台机器的费用是1. 所讨论的半在线模型假设已知所有工件的总加工时间. 目标是使makespan与购买机器费用的总和尽可能小. 文章讨论如何设计该问题的半在线近似算法,并用竞争比来衡量算法的近似优程度。 本文的主要结果为:对不可中断的情况,我们给出了该问题的下界是6/5,从而改进了文献中的给出的结果1.161. 对可中断的情况,所谓工件加工允许中断, 即加工过程中允许机器暂停某工件的加工, 而改为加工另一工件。 对这种情况,如果工件的总加工时间不超过4,我们给出了竞争比为1的最优算法;当总加工时间超过4时,我们给出了竞争比为5/4的算法,并给出问题的下界至少是1.0957.Abstract: In this paper, we consider the following semi-online List Model problemwith known total size. We are given a sequence of independent jobs withpositive sizes, which must be assigned to be processed on machines. Nomachines are initially provided, and when a job is revealed thealgorithm has the option to purchase new machines. By normalizing alljob sizes and machine cost, we assume that the cost of purchasing onemachine is 1. We further know the total size of all jobs in advance. Theobjective is to minimize the sum of the makespan and the number ofmachines to be purchased. Both non-preemptive and preemptive versions areconsidered. For the non-preemptive version, we present a new lower bound6/5 which improves the known lower bound 1.161. For the preemptiveversion, we present an optimal semi-online algorithm with a competitiveratio of 1 in the case that the total size is not greater than 4, and analgorithm with a competitive ratio of 5/4 otherwise, while a lowerbound 1.0957 is also presented for general case.
-
Keywords:
- semi-online /
- preemptive scheduling /
- machine cost /
- competitive ratio
-
-
[1] Imreh C, Noga J. Scheduling with machine cost. In -\it Proc. RANDOM-APPROX'99}, Berkley, USA, -\it Lecture Notes in Computer Science}, 1999, 1671: 168--176.
[2] D\'-o}sa G, He Y. Better on-line algorithms for scheduling with machine cost. -\it SIAM J. Computing}, 2004, 33: 1035--1051.
[3] Jiang Y, He Y. Preemptive online algorithms for scheduling with machine cost. -\it Acta Informatica}, 2005, 41: 315--340. %2004. Published online: DOI: 10.1007/s00236-004-0156-9.
[4] He Y, Cai S. Semi-online scheduling with machine cost. -\it Journal of Computer Science and Technology}, 2002, 17: 781--787.
[5] Cai S, He Y. Quasi-online algorithms for scheduling non-increasing processing jobs with processor cost. -\it Acta Automatica Sinica}, 2003, 29: 917--921. (in Chinese)
[6] Graham R L. Bounds on multiprocessing finishing anomalies. -\it SIAM Journal on Applied Mathematics}, 1969, 17(4): 416--429.
[7] He Y, Zhang G. Semi-online scheduling on two identical machines. -\it Computing}, 1999, 62: 179--187.
[8] Kellerer H, Kotov V, Speranza M R, Tuza Z. Semi on-line algorithms for the partition problem. -\it Operations Research Letters}, 1997, 21: 235--242.
[9] D\'-o}sa G, He Y. Semi-online algorithms for parallel machine scheduling problems. -\it Computing}, 2004, 72: 355--363.
[10] Epstein L. Bin stretching revisited. -\it Acta Informatica}, 2003, 39: 97--117.
[11] He Y, Jiang Y. Optimal algorithms for semi-online preemptive scheduling problems on two uniform machines. -\it Acta Informatica}, 2004, 40: 367--383.
[12] Seiden S. A guessing game and randomized online algorithms. In -\it Proc. the 32nd Annual ACM Symposium on the Theory of Computing}, ACM, New York, 2000, pp.592--601.
[13] McNaughton R. Scheduling with deadlines and loss functions. -\it Management Sciences}, 1959, 6: 1--12.
计量
- 文章访问数: 22
- HTML全文浏览量: 0
- PDF下载量: 1420