Improved Upper Bounds on the Competitive Ratio for Online Realtime Scheduling
Improved Upper Bounds on the Competitive Ratio for Online Realtime Scheduling
复制标题
DOI：
10.1007/978-3-540-75520-3_42
复制
发表时间：
2007-10
影响因子：
2.5
通讯作者：
Koji M. Kobayashi;K. Okamoto
中科院分区：
文献类型：
--
作者：
Koji M. Kobayashi;K. Okamoto
我们研究了在线调度问题的一个变种，在线实时调度。它可以定义在一个完整的图上，其中每个节点代表一个通信代理，两个代理之间的通信可以被认为是一条边。一个输入是一个通信作业序列，每个作业都需要两个指定的代理在指定的时间段内进行通信。每个代理最多只能参与一个通信作业。在线算法的任务是调度作业，使已完成的通信作业的利润之和最大化。本文将基于最大匹配的通用货架算法（GSMM）的竞争比从提高到提高。我们还证明了这个比例是最佳的GSMM。此外，我们还研究了工件没有空闲时间的情况，即工件必须立即开始或在发布时被拒绝的情况，并给出了GSMM的竞争比。
We study a variant of online scheduling problems, the online realtime scheduling. It can be defined on a complete graph, where each node represents a communication agent, and a communication between two agents can be considered as an edge. An input is a sequence of communication jobs, each of which requires two specified agents to communicate during specified time period. Each agent can participate in at most one communication job. The task of an online algorithm is to schedule jobs so that the sum of the profits of completed communication jobs is maximized. In this paper, we improve the competitive ratio of the General Shelf based Max Matching (GSMM) algorithm fromto. We also prove that this ratio is optimal forGSMM. In addition, we study the case where each job has no slack time, namely, it must be either started immediately or rejected at its release time, and show the competitive ratio ofGSMMis.