Online scheduling of weighted equal-length jobs with hard deadlines on parallel machines
Online scheduling of weighted equal-length jobs with hard deadlines on parallel machines
复制标题
DOI：
10.1016/j.cor.2010.10.012
复制
发表时间：
2011-08
期刊：
影响因子：
--
通讯作者：
S. O. Krumke;A. Taudes;Stephan Westphal
中科院分区：
文献类型：
--
作者：
S. O. Krumke;A. Taudes;Stephan Westphal
本文研究了在m台相同机器上等长工件的最大利润排序问题。工件随时间在线到达，目标是确定一个非抢占式调度，使调度的工件的总利润最大化。设工件的公共加工要求为p>0。对于每个作业ji，i= 1，.，n，我们给出一个发布时间ri（作业在该时间变得已知）和一个截止日期ri+p+δi。如果这项工作被安排在最后期限之前完成，那么就可以获得wiis的利润。当一个新的作业到达时，在线算法必须决定是否接受该作业。在接受的情况下，在线算法必须提供一个可行的工作开始日期。竞争分析已经成为衡量在线算法质量的标准方法。对于一个最大化问题，一个在线算法被称为c-竞争的，如果在每个输入实例上，它至少实现了最优（“离线”）利润的1/c-分数。我们给出了在线算法的竞争力的下限，并提出了算法匹配这个下限到一个常数因子。
We consider the problem of scheduling a maximum profit selection of equal length jobs on m identical machines. Jobs arrive online over time and the goal is to determine a non-preemptive schedule which maximizes the total profit of the scheduled jobs. Let the common processing requirement of the jobs be p>0. For each job ji, i=1,…,n we are given a release time ri(at which the job becomes known) and a deadline ri+p+δi. If the job is scheduled and completed before the deadline, a profit of wiis earned. Upon arrival of a new job, an online algorithm must decide whether to accept the job or not. In case of acceptance, the online algorithms must provide a feasible starting date for the job. Competitive analysis has become a standard way of measuring the quality of online algorithms. For a maximization problem, an online algorithm is called c-competitive, if on every input instance it achieves at least a 1/c-fraction of the optimal (“offline”) profit. We give lower bounds for the competitivity of online algorithms and propose algorithms which match this lower bound up to a constant factor.