Online scheduling of time-critical tasks to minimize the number of calibrations

doi:10.1016/j.tcs.2022.01.040

	Online scheduling of time-critical tasks to minimize the number of calibrations
	Chen, Zuzhi 1,2; Zhang, Jialin 1,2
	2022-05-07
发表期刊	THEORETICAL COMPUTER SCIENCE
ISSN	0304-3975
卷号	914 页码:1-13
摘要	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.
关键词	Online scheduling Calibration Time-critical
DOI	10.1016/j.tcs.2022.01.040
收录类别	SCI
语种	英语
资助项目	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类目	Computer Science, Theory & Methods
WOS记录号	WOS:000793346000001
出版者	ELSEVIER
引用统计
文献类型	期刊论文
条目标识符	http://119.78.100.204/handle/2XEOYT63/19545
专题	中国科学院计算技术研究所期刊论文_英文
通讯作者	Zhang, Jialin
作者单位	1.Chinese Acad Sci, Inst Comp Technol, Beijing, Peoples R China 2.Univ Chinese Acad Sci, 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.