Resource Constrained Scheduling (Energy Harvesting Communication)

计算机科学 调度(生产过程) 能量收集 资源(消歧) 分布式计算 能量(信号处理) 环境科学 计算机网络 工程类 运营管理 数学 统计
作者
Rahul Vaze
出处
期刊:Cambridge University Press eBooks [Cambridge University Press]
卷期号:: 409-420
标识
DOI:10.1017/9781009349178.020
摘要

Introduction In this chapter, we consider a more complicated scheduling problem than Chapter 15, where the resource needed for the processing of packets, energy, itself arrives over time, and the algorithm has only causal knowledge about it. This paradigm is relevant for communication systems powered by renewable energy sources, where the amount of energy arriving at each time slot is unpredictable. This scenario also models scheduling problems on factory floors where the availability time of, say, raw materials or multiple machines needed to complete a complicated job is uncertain and is revealed causally to the algorithm. Conventionally, in online scheduling, unlimited energy is available, and the objective is to minimize a combination of energy used and relevant performance metrics, e.g., makespan, completion time, flow time, and the only uncertainty is about the packet or job arrival times and their sizes. For the online scheduling problem considered in the chapter, both the amount of energy and its arrival slots in the future are unknown to the algorithm and are possibly controlled by the adversary. With energy arriving over time and in arbitrary amounts, the generic scheduling problem is to minimize any performance metric, subject to the energy neutrality constraint, i.e., the amount of energy used by any time is at most the amount of energy that has arrived so far. With arbitrary energy arrivals, we consider a canonical problem of transmitting a single packet (with a fixed number of bits) to minimize its completion time. Without loss of generality, we assume that the total amount of energy that arrives over time is sufficient to transmit the packet completely by the optimal offline algorithm OPT. The challenge is to propose an algorithm that can compete with OPT. We show that a Lazy algorithm has a competitive ratio of 2, which is also the best possible. The considered problem in this chapter is fairly versatile. For example, it can model a scheduling paradigm where there are multiple servers but their availability is unknown, and the amount of work done in each slot is a concave function of the number of servers used in that slot. Then a scheduling problem (with any usual performance metric such as flow time, makespan, completion time) emerges where the decision is: how many servers to use among the available ones at each time.
最长约 10秒,即可获得该文献文件

科研通智能强力驱动
Strongly Powered by AbleSci AI
科研通是完全免费的文献互助平台,具备全网最快的应助速度,最高的求助完成率。 对每一个文献求助,科研通都将尽心尽力,给求助人一个满意的交代。
实时播报
多吃青菜发布了新的文献求助10
刚刚
猪猪hero发布了新的文献求助50
刚刚
刚刚
刚刚
1秒前
皎皎完成签到,获得积分10
1秒前
lina完成签到 ,获得积分10
1秒前
evilbatuu发布了新的文献求助10
1秒前
Kiritoshi发布了新的文献求助10
1秒前
Xpen完成签到,获得积分10
1秒前
2秒前
2秒前
秋风的应助被孤独的根号三采纳,获得10
2秒前
wang发布了新的文献求助10
3秒前
3秒前
刘天煜发布了新的文献求助30
3秒前
顽石发布了新的文献求助10
3秒前
Owen的应助被善良水壶采纳,获得10
4秒前
4秒前
小二郎的应助被别偷我增肌粉采纳,获得30
4秒前
桐桐的应助被鑫妍妍采纳,获得10
5秒前
5秒前
一笑没的应助被yqy采纳,获得10
5秒前
风吹麦浪的应助被sumire采纳,获得10
5秒前
一笑没的应助被yqy采纳,获得10
5秒前
6秒前
6秒前
jkxbb完成签到 ,获得积分10
6秒前
一心一意完成签到,获得积分10
6秒前
Sky36001发布了新的文献求助20
6秒前
6秒前
香蕉觅云的应助被不安分的心采纳,获得10
7秒前
111发布了新的文献求助10
7秒前
7mi完成签到 ,获得积分10
7秒前
7秒前
CengcEng发布了新的文献求助10
8秒前
10秒前
Pearson完成签到,获得积分10
10秒前
逆光发布了新的文献求助10
10秒前
10秒前
高分求助中
(应助此贴封号)【重要!!请各用户(尤其是新用户)详细阅读】【科研通的精品贴汇总】 10000
拉伸高分子熔体中缠结行为的模拟和小角中子散射研究 1700
奈特基础组织学:配套组织病理学(第4版)(Netter's Essential Histology With Correlated Histopathology) 800
John McDowells Bildungstheorie 800
八旗制度の研究 600
plantTFDB 508
高分子基功能界面水蒸发材料与应用研究 500
热门求助领域 (近24小时)
化学 材料科学 医学 生物 纳米技术 计算机科学 工程类 有机化学 化学工程 生物化学 物理 复合材料 内科学 催化作用 光电子学 人工智能 细胞生物学 无机化学 物理化学 数学
热门帖子
关注 科研通微信公众号,转发送积分 8176481
求助须知:如何正确求助?哪些是违规求助? 9567855
关于积分的说明 21795109
捐赠科研通 7771163
什么是DOI,文献DOI怎么找? 3432027
关于科研通互助平台的介绍 2556365
邀请新用户注册赠送积分活动 2477695