On Wednesday, 2021-04-21, Associate Professor Dr. Vincent Chau of Southeast University [东南大学] gave his invited talk "Weighted Throughput Maximization with Calibrations." Scheduling is always an interesting and challenging field, where many important algorithms and novelties have emerged. Dr. Chao introduced algorithms with strong worst-case guarantees for the problem of scheduling both calibration and jobs to machines. This research applies to many scenarios, as many advanced production machinery needs to be calibrated regularly to ensure a high manufacturing quality. The talk was very well received by the audience and, for the third time today, a very nice discussion ensued. (Before this talk on the same day, we hosted two more invited talks by Prof. Min LI [李敏] of Nanjing University and by Prof. Weili XUE [薛巍立] of Southeast University).
报 告 人:
2021 年 04 月 21 日(星期三) 15:30-16:30
应用优化研究所会议室(合肥学院南艳湖校区 53 栋 920)
The scheduling problem with calibrations was introduced by Bender et al. (SPAA 2013). In sensitive applications, machines need to be periodically calibrated to ensure that they run correctly. Formally, we are given a set of n jobs with release times, deadlines and weights. Calibrating a machine requires a cost and remains calibrated for a period of T time units, after which it must be recalibrated before it can resume running jobs. Moreover, we are given a budget of K calibrations. The objective is to schedule a set of jobs such that the total weight is maximized on m identical machines with at most K calibrations. In this paper, we present a (1/3)-approximation polynomial time algorithm when jobs have unit processing time. For the arbitrary processing time case, we give a ((1−epsilon)/18)-approximation polynomial time algorithm.
Vincent Chau 于 2014 年获得法国埃夫里大学计算机系博士学位,之后分别在香港城市大学及香港浸会大学做博士后。2017 年在中国科学院深圳先进技术研究院做博士后, 2019 年起任助理研究员。2021 年起在东南大学计算机科学与工程学院任副教授。研究领域包括:算法设计与分析、能源调度优化、校准调度等。 近年来,累计以第一作者、通讯作 者身份在国际著名期刊 Theoretical Computer Science、Journal of Combinatorial Optimization、Journal of Scheduling 以及 SPAA、STACS、ISAAC 等计算理论知名国际学术会议上发表论文 二十余篇。