| Optimal Preemptive Online Algorithms for Scheduling with Known Largest Size on Two Uniform Machines |
| |
| 作者姓名： | Yong HE Yi Wei JIANG Hao ZHOU |
| |
| 作者单位： | [1]Department of Mathematics, Zhejiang University. Hangzhou 310027. P. R. China [2]Faculty of Science, Zhejiang Sci- Tech University Hangzhou 310018, P. R. China. [3]Department of Mathematics, Zhejiang University Hangzhou 310027. P. R. China [4]Basic Course Department, Zhejiang Shorten University Hangzhou 310015. P. R. China |
| |
| 基金项目： | This research is supported by National Natural Science Foundation of China （10271110, 60021201） and the Teaching and Research Award Program for 0utstanding Young Teachers in Higher Education Institutions of M0E, China |
| |
| 摘 要： | In this paper, we consider the seml-online preemptive scheduling problem with known largest job sizes on two uniform machines. Our goal is to maximize the continuous period of time （starting from time zero） when both machines are busy, which is equivalent to maximizing the minimum machine completion time if idle time is not introduced. We design optimal deterministic semi-online algorithms for every machine speed ratio s ∈ 1, ∞）, and show that idle time is required to achieve the optimality during the assignment procedure of the algorithm for any s 〉 （s^2 ＋ 3s ＋ 1）/（s^2 ＋ 2s ＋ 1）. The competitive ratio of the algorithms is （s^2 ＋ 3s ＋ 1）/（s^2 ＋ 2s ＋ 1）, which matches the randomized lower bound for every s ≥ 1. Hence randomization does not help for the discussed preemptive scheduling problem.
|
| 关 键 词： | 准在线 抢先时序列安排 统一机械 竞争比率 |
| 收稿时间： | 30 April 2005 |
| 修稿时间： | 2005-04-302005-09-05 |
Optimal Preemptive Online Algorithms for Scheduling with Known
Largest Size on Two Uniform Machines |
| |
| Yong HE Yi Wei JIANG Hao ZHOU.Optimal Preemptive Online Algorithms for Scheduling with Known Largest Size on Two Uniform Machines[J].Acta Mathematica Sinica,2007,23(1):165-174. |
| |
| Authors: | Yong He Yi Wei Jiang Hao Zhou |
| |
| Institution: | (1) Department of Mathematics, Zhejiang University, Hangzhou 310027, P. R. China;(2) Faculty of Science, Zhejiang Sci-Tech University, Hangzhou 310018, P. R. China;(3) Department of Mathematics, Zhejiang University, Hangzhou 310027, P. R. China;(4) Basic Course Department, Zhejiang Shuren University, Hangzhou 310015, P. R. China |
| |
| Abstract: | In this paper, we consider the semi-online preemptive scheduling problem with known largest job sizes on two uniform machines. Our goal is to maximize the continuous period of time (starting from time zero) when both machines are busy, which is equivalent to maximizing the minimum machine completion time if idle time is not introduced. We design optimal deterministic semi-online algorithms for every machine speed ratio s ∈¸ 1,∞), and show that idle time is required to achieve the optimality during the assignment procedure of the algorithm for any s > (s 2 + 3s + 1 / (s 2 + 2s + 1). The competitive ratio of the algorithms is (s 2 + 3s + 1) / (s 2 + 2s + 1), which matches the randomized lower bound for every s ≥ 1. Hence randomization does not help for the discussed preemptive scheduling problem. |
| |
| Keywords: | semi-online preemptive scheduling uniform machines competitive ratio |
| 本文献已被 维普 SpringerLink 等数据库收录！ |
