Improved Bounds for the Online Scheduling Problem

竞争分析 作业车间调度 上下界 调度(生产过程) 组合数学 计算机科学 在线算法 离散数学 任务(项目管理) 数学 数学优化 算法 管理 经济 操作系统 地铁列车时刻表 数学分析
作者
John F. Rudin,R. Chandrasekaran
出处
期刊:SIAM Journal on Computing [Society for Industrial and Applied Mathematics]
卷期号:32 (3): 717-735 被引量:102
标识
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.
最长约 10秒,即可获得该文献文件

科研通智能强力驱动
Strongly Powered by AbleSci AI
科研通是完全免费的文献互助平台,具备全网最快的应助速度,最高的求助完成率。 对每一个文献求助,科研通都将尽心尽力,给求助人一个满意的交代。
实时播报
seet完成签到,获得积分10
1秒前
爆米花的应助被蔡慧学采纳,获得10
1秒前
赤道的雪发布了新的文献求助10
1秒前
跳跃的紫文完成签到 ,获得积分10
1秒前
1秒前
阳光奎发布了新的文献求助30
1秒前
tiptip的应助被211107采纳,获得30
2秒前
科研通AI6.4的应助被211107采纳,获得10
2秒前
Cheryl完成签到,获得积分10
2秒前
终梦的应助被211107采纳,获得10
2秒前
科研通AI6.4的应助被211107采纳,获得10
2秒前
科研通AI6.4的应助被211107采纳,获得10
2秒前
搞怪的老九的应助被211107采纳,获得10
3秒前
3秒前
邦尼老师发布了新的文献求助10
3秒前
新楚发布了新的文献求助10
3秒前
OK关注了科研通微信公众号
3秒前
3秒前
杜仲_商陆完成签到,获得积分10
4秒前
热心小蕊发布了新的文献求助10
4秒前
开什么开发布了新的文献求助10
4秒前
cgl155410完成签到,获得积分10
5秒前
孙朱珠发布了新的文献求助10
5秒前
5秒前
孙琪峰完成签到,获得积分10
5秒前
李爱国的应助被kkk采纳,获得10
5秒前
英俊的铭的应助被ZM采纳,获得10
6秒前
张森阳发布了新的文献求助10
6秒前
6秒前
6秒前
一路顺风发布了新的文献求助10
7秒前
SEEME完成签到,获得积分10
7秒前
Camellia发布了新的文献求助10
7秒前
阳光代容完成签到,获得积分0
7秒前
7秒前
7秒前
patom发布了新的文献求助10
7秒前
8秒前
10秒前
NexusExplorer的应助被huanhuan采纳,获得10
10秒前
高分求助中
(应助此贴封号)【重要!!请各用户(尤其是新用户)详细阅读】【科研通的精品贴汇总】 10000
拉伸高分子熔体中缠结行为的模拟和小角中子散射研究 1700
奈特基础组织学:配套组织病理学(第4版)(Netter's Essential Histology With Correlated Histopathology) 800
John McDowells Bildungstheorie 800
八旗制度の研究 600
plantTFDB 508
Resource Recovery Handbook 500
热门求助领域 (近24小时)
化学 材料科学 医学 生物 纳米技术 计算机科学 工程类 有机化学 化学工程 生物化学 物理 复合材料 内科学 催化作用 光电子学 人工智能 细胞生物学 无机化学 物理化学 数学
热门帖子
关注 科研通微信公众号,转发送积分 8175707
求助须知:如何正确求助?哪些是违规求助? 9567353
关于积分的说明 21792214
捐赠科研通 7770334
什么是DOI,文献DOI怎么找? 3431908
关于科研通互助平台的介绍 2556260
邀请新用户注册赠送积分活动 2477417