Online Scheduling with Known Arrival Times
Online Scheduling with Known Arrival Times
复制标题
DOI：
10.1287/moor.1080.0346
复制
发表时间：
2009-02
期刊：
影响因子：
--
通讯作者：
Nicholas G. Hall;M. Posner;C. Potts
中科院分区：
文献类型：
--
作者：
Nicholas G. Hall;M. Posner;C. Potts
我们考虑一个在线调度环境，在不知道可能稍后到达的作业数据的情况下做出决策。然而，额外的作业只能在已知的未来时间到达。该环境在经典的离线调度环境和在线调度环境之间进行插值，并在存在许多等间隔的潜在作业到达时间时接近经典的在线环境。目标是最小化加权完成时间的总和，这是一种广泛使用的测量在制品库存成本和客户服务的方法。对于一个无抢占的单机环境，我们证明了任何在线算法的竞争比的下界是一个数学程序的解。这个下限介于(1 + SQRT(5))/2和2之间，确切的值取决于潜在的作业到达时间。我们还提供了一个“最佳可能”的在线调度算法，并证明了它的竞争比符合这个下界。我们分析了两种实际驱动的特殊情况，其中潜在的作业到达时间具有特殊的结构。当存在许多等间隔的潜在作业到达时间时，我们的在线算法的竞争比接近经典在线问题的最佳竞争比2。
We consider an online scheduling environment where decisions are made without knowledge of the data of jobs that may arrive later. However, additional jobs can only arrive at known future times. This environment interpolates between the classical offline and online scheduling environments and approaches the classical online environment when there are many equally spaced potential job arrival times. The objective is to minimize the sum of weighted completion times, a widely used measure of work-in-process inventory cost and customer service. For a nonpreemptive single machine environment, we show that a lower bound on the competitive ratio of any online algorithm is the solution of a mathematical program. This lower bound is between (1 + SQRT(5))/2 and 2, with the exact value depending on the potential job arrival times. We also provide a “best possible” online scheduling algorithm and show that its competitive ratio matches this lower bound. We analyze two practically motivated special cases where the potential job arrival times have a special structure. When there are many equally spaced potential job arrival times, the competitive ratio of our online algorithm approaches the best possible competitive ratio of 2 for the classical online problem.