Randomized algorithms for fully online multiprocessor scheduling with testing

报告题目：  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 Jj arrives with an  upper bound uj on the exact processing time pj and a testing operation with  length tj. An algorithm chooses to execute Jj for uj time or to test Jj for  tj time to obtain the exact processing time pj followed by immediately  executing the job for pj 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.

报告时间：2023年5月17日15:00

报告地点：海纳苑2幢101