中国科学院机构知识库网格
Chinese Academy of Sciences Institutional Repositories Grid
首页 机构 成果 学者
  
  1. CAS IR Grid
  2. 计算技术研究所
  3. 中国科学院计算技术研究所
  4. 中国科学院计算技术研究所期刊论文
  5. 英文
Online scheduling of time-critical tasks to minimize the number of calibrations

文献类型：期刊论文

作者Chen, Zuzhi1,2; Zhang, Jialin1,2
刊名THEORETICAL COMPUTER SCIENCE
出版日期2022-05-07
卷号914页码:1-13
关键词Online scheduling Calibration Time-critical
ISSN号0304-3975
DOI10.1016/j.tcs.2022.01.040
英文摘要We study the online scheduling problem where the machines need to be calibrated before processing any jobs. To calibrate a machine, it will take lambda time steps as the activation time, and then the machine will remain calibrated status for T time steps. The job can only be processed by the machine that is in calibrated status. Given a set of jobs arriving online, each of the jobs is characterized by a release time, a processing time, and a deadline. We assume that there is an infinite number of machines for usage. The objective is to minimize the total number of calibrations while feasibly scheduling all jobs. For the case that all jobs have unit processing times, we propose an O(lambda)-competitive algorithm, which is asymptotically optimal. When lambda = 0, the problem is degraded to rent minimization, where our algorithm achieves a competitive ratio of 3e + 7(asymptotic to & nbsp;15.16) which improves upon the previous results for such problems. (C)& nbsp;2022 Elsevier B.V. All rights reserved.
资助项目National Natural Science Foundation of China[61832003] ; National Natural Science Foundation of China[61872334] ; Strategic Priority Research Program of Chinese Academy of Sciences[XDA27000000]
WOS研究方向Computer Science
语种英语
WOS记录号WOS:000793346000001
出版者ELSEVIER
源URL[http://119.78.100.204/handle/2XEOYT63/19544]  
专题中国科学院计算技术研究所期刊论文_英文
通讯作者Zhang, Jialin
作者单位1.Univ Chinese Acad Sci, Beijing, Peoples R China
2.Chinese Acad Sci, Inst Comp Technol, Beijing, Peoples R China
推荐引用方式
GB/T 7714		 Chen, Zuzhi,Zhang, Jialin. Online scheduling of time-critical tasks to minimize the number of calibrations[J]. THEORETICAL COMPUTER SCIENCE,2022,914:1-13.
APA Chen, Zuzhi,&Zhang, Jialin.(2022).Online scheduling of time-critical tasks to minimize the number of calibrations.THEORETICAL COMPUTER SCIENCE,914,1-13.
MLA Chen, Zuzhi,et al."Online scheduling of time-critical tasks to minimize the number of calibrations".THEORETICAL COMPUTER SCIENCE 914(2022):1-13.

入库方式： OAI收割

来源：计算技术研究所

浏览0
下载0
收藏0
其他版本

除非特别说明，本系统中所有内容都受版权保护，并保留所有权利。