报告时间：2023年05月18日 14:30开始
报 告 人：龚铭炀（加拿大阿尔伯塔大学 博士）
报告地点：包玉书9号楼401
报告题目 Randomized algorithms for fully online multiprocessor scheduling with testing.
报告摘要：Multiprocessor scheduling is one of the famous combinatorial optimization problems that receives numerous studies. Recently, its testing variant is investigated by several research groups, in which each job J_j arrives with an upper bound u_j on the exact processing time p_j and a testing operation with length t_j. An algorithm chooses to execute J_j for u_j time or to test J_j for t_j time to obtain the exact processing time p_j followed by immediately executing the job for p_j time. Our target problem is the fully online multiprocessor scheduling with testing, in which the jobs arrive in sequence so that the testing decision needs to be made at the job arrival as well as the designated machine. We first design a randomized algorithm with 3.1490-competitive as a non-uniformly probability distribution over arbitrary many deterministic algorithms. When the number of machines is two, we show our randomized algorithm is already 2.1839-competitive based on only two deterministic algorithms while we prove the competitive ratio is at least 2.2117 for any deterministic algorithm. So, our randomized algorithm beats all deterministic algorithms on two machines.
报告人简介：Mingyang Gong is pursuing the Ph.D. in Department of Computing Science at University of Alberta. He received his Bachelor of Natural Sciences in Mathematics and Applied Mathematics in 2018 and Master in School of Mathematical Sciences in 2021 at Zhejiang University.
