Competitive Algorithms for Due Date Scheduling
Competitive Algorithms for Due Date Scheduling
复制标题
到期日安排的竞争算法
DOI：
10.1007/s00453-009-9321-4
复制
发表时间：
2007
期刊：
影响因子：
1.1
通讯作者：
K. Pruhs
中科院分区：
文献类型：
--
作者：
N. Bansal;H. Chan;K. Pruhs
AbstractWe考虑几个在线调度问题时，客户要求从一家公司的产品按订单生产。在订购时，公司必须向客户提供到期日。为了使顾客满意，公司必须在到期日之前生产出产品。公司必须有一个包含两个组件的联机算法：第一个组件设置到期日，第二个组件计划生成的任务，目标是满足到期日。任务的最基本服务质量度量是报价提前期，即到期日与发放时间之间的差值。我们首先考虑最小化平均报价提前期的基本问题。我们证明了存在（1+ε）-速度
$O（\frac{\log k}{\displaystyle\log k}）$
- 这个问题的竞争算法（这里k是作业的最大工作与作业的最小工作的比率），并且该算法本质上是最优竞争的。这个结果扩展到每个工件都有一个权重的情况下，目标是加权报价提前期。然后，我们引入以下一般设置：有一个非递增的利润函数pi（t）与每个工件Ji。如果顾客对工件Ji的交货期为di，那么在交货期前完成该工件所获得的利润为pi（di）。我们考虑的目标是利润最大化。我们证明了，如果公司必须在其到期日之前完成每一项工作，那么就不存在O（1）速度的多对数竞争算法。然而，如果公司可以错过一个工作的到期日，在放弃从该工作的利润为代价，那么我们证明了存在一个（1+ε）-速度O（1+1/ε）-竞争算法，并且该算法本质上是最优竞争的。
AbstractWe consider several online scheduling problems that arise when customers request make-to-order products from a company. At the time of the order, the company must quote a due date to the customer. To satisfy the customer, the company must produce the good by the due date. The company must have an online algorithm with two components: The first component sets the due dates, and the second component schedules the resulting jobs with the goal of meeting the due dates.The most basic quality of service measure for a job is the quoted lead time, which is the difference between the due date and the release time. We first consider the basic problem of minimizing the average quoted lead time. We show that there is a (1+ε)-speed
$O(\frac{\log k}{\epsilon})$
-competitive algorithm for this problem (here k is the ratio of the maximum work of a job to the minimum work of a job), and that this algorithm is essentially optimally competitive. This result extends to the case that each job has a weight and the objective is weighted quoted lead time.We then introduce the following general setting: there is a non-increasing profit function pi(t) associated with each job Ji. If the customer for job Ji is quoted a due date of di, then the profit obtained from completing this job by its due date is pi(di). We consider the objective of maximizing profits. We show that if the company must finish each job by its due date, then there is no O(1)-speed poly-log-competitive algorithm. However, if the company can miss the due date of a job, at the cost of forgoing the profits from that job, then we show that there is a (1+ε)-speed O(1+1/ε)-competitive algorithm, and that this algorithm is essentially optimally competitive.