报告题目：Scheduling with Calibrations for Multi-Interval Jobs

报告时间：9月24日10:00-11:00

报告地点：数学科学学院 10号楼415 会议室

报告人：Vincent Chau教授（东南大学）

报告摘要：

This paper studies a scheduling problem with machine calibrations for multi-interval jobs. More exactly, there are n (possibly weighted) jobs of unit-size that must be scheduled on a single, initially uncalibrated machine. The machine can process jobs only when calibrated, and such a calibration lasts for T time slots. The standard model by Bender et al. [SPAA'13] assumes that each job has a release time and deadline between which it must be processed. We study a generalization in which each job must be processed during one of possibly many job-dependent time intervals. We consider two objectives: In the minimization version, our goal is to minimize the number of calibrations while scheduling all jobs. In the maximization version, our goal is to maximize the total weight of scheduled jobs while using at most B calibrations.

For the minimization version, we present a logarithmic approximation algorithm.We also prove that the problem is set-cover hard, implying that our algorithm is optimal up to a constant factor unless P=NP. The special case when each job may be scheduled in at most two time slots is shown to be vertex-cover hard, implying that there is no $(2-\epsilon)$-approximation algorithm based on the unique game conjecture.

For the maximization version, we give an algorithm with approximation ratio (1 - 1/e). This improves upon the previously best-known algorithm, which has an approximation ratio of 1/3 [WADS 2019].

Moreover, we also prove that our bound on the approximation ratio is tight.

While all hardness results mentioned above hold for any T \geq 3, we provide optimal polynomial-time algorithms for $T = 2$ in both the minimization and the maximization versions.

Finally, we show that our methods can be extended into $m$ identical machines case by losing some running time while all algorithmic results remain the same in both versions.

报告人简介：

Vincent Chau，东南大学计算机科学与工程学院副教授、博士生导师。2014年获巴黎萨克雷大学博士学位，随后于香港城市大学、香港浸会大学及中国科学院深圳先进技术研究院从事博士后研究。入选中国科学院国际人才计划（国际博士后、外国青年学者、访问学者）。主要研究方向为算法设计与分析、能源调度优化及校准调度等。在 INFORMS Journal on Computing、Theoretical Computer Science、Journal of Scheduling等算法理论权威期刊，以及 STACS、ISAAC、SPAA、AAAI 等计算机理论与人工智能顶会发表学术论文50余篇。