竞争分析
作业车间调度
上下界
调度(生产过程)
组合数学
计算机科学
在线算法
离散数学
任务(项目管理)
数学
数学优化
算法
管理
经济
操作系统
地铁列车时刻表
数学分析
作者
John F. Rudin,R. Chandrasekaran
标识
DOI:10.1137/s0097539702403438
摘要
The problem considered here is the same as the one discussed in [G. Galambos and G. J. Woeginger, eds., SIAM J. Comput., 22 (1993), pp. 349--355]. It is an m-machine online scheduling problem in which we wish to minimize the competitive ratio for the makespan objective. In this paper, we show that $\sqrt{3}$ is a lower bound on this competitive ratio for m=4. In particular, we show how to force a lower bound of $\sqrt{3\,}-\epsilon $ for any positive $\epsilon $. This reduces the gap between the performance of known algorithms [S. Albers, in Proceedings of the 29th Annual ACM Symposium on Theory of Computing, ACM, New York, 1997, pp. 130--139] and the lower bound. The method used introduces an approach to building the task master's strategy.
科研通智能强力驱动
Strongly Powered by AbleSci AI