报告题目：On Batching Task Scheduling: Theoretical Foundation and Algorithm Design

报 告 人：陈林教授，中山大学

报告时间：2023年12月7日（周四）上午10：00-11：00

报告地点：龙洞校区行政楼610

主 持 人：何伟骅

报告摘要：This talk is focused on the following batching task scheduling problem. There is a set of tasks to be executed on a number of machines. Some can be executed simultaneously on a single machine, while others require exclusive use of an entire machine. We seek an optimal scheduling policy to maximize the overall system utility. This problem is a significant generalization of the broadcast and lock scheduling problems, and arises in a variety of engineering fields where communication, computing, and storage resources are potential bottlenecks and thus need to be carefully scheduled.

In the talk I will start by introducing the motivation and theoretical background of the problem. I will then present the algorithmic framework we have developed for batching task scheduling in its most generic form, which is the first approximation algorithm with deterministic performance guarantee. I will focus on the core technicality in our design, a novel LP relaxation mechanism and a rounding and coloring approach that turns the solution of the LP relaxation to a feasible scheduling policy. I will conclude the talk by discussing a number of variants and extensions and our on-going work along this line of research.

The core technical part of this talk is joint work with Dr. Hehuan SHI, my former Ph.D. student. Part of our results were published in INFOCOM, RTSS, ICPP, and ToN.

专家简介：陈林, 教授, 博士生导师,2002年本科毕业于东南大学强化班（现吴健雄学院），信息工程专业，2005 年和 2008 年在法国高等电信学院（Télécom ParisTech）取得工程师和博士学位。2009年至2019年任巴黎南大学计算机系副教授、博士生导师（Habilitation à Diriger des Recherches），2019年起担任中山大学数据科学与计算机学院教授、博士生导师。主要研究领域为网络分布式学习及算法设计，信息安全和隐私保护等，在物联网、移动计算、绿色通信等领域具有多年的研究积累。