Seminar on Discrete Mathematics: Online early work scheduling on parallel machines

：蒋义伟（浙江工商大学）
：2023-07-07 09:00
：海韵园数理大楼686会议室

报告人：蒋义伟（浙江工商大学）

时  间：2023年7月7日9:00

地  点：海韵园数理大楼686会议室

内容摘要:

We consider non-preemptive online parallel-machine scheduling with a common due date to maximize the total early work of all the jobs, i.e., the total processing time of the jobs (or parts) completed before the common due date. For the general case of m machines, we provide a lower bound on m, which is the positive real root of an m-degree equation. For the online algorithm, we first show that the tight competitive ratio of the classical list scheduling (LS) algorithm is 4/3. We then re-prove that the competitive ratio of the previous algorithm EFFm is at most 1.2956 and present a formula to compute the competitive ratio of the algorithm for any given m. For the case of three machines, we improve the lower bound to 1.1878 and propose an improved online algorithm with a competitive ratio of 1.2483.

个人简介：

蒋义伟，浙江大学本硕博，浙江工商大学“西湖学者”特聘教授。美国The University of Texas at Dallas计算机系、香港大学计算机系、香港理工大学物流与航运系访问学者，美国《Mathematical Reviews》特约评论员，中国运筹学会排序专业委员会常务理事。入选浙江省“151”人才工程和浙江省高校优秀青年教师资助计划。主要研究领域有：调度理论、离散优化、算法设计与分析、物流与供应链管理等。主持国家自然科学基金2项，浙江省自然科学基金3项。获浙江省高校科研成果二等奖1项（排名第一）。在运筹、管理与理论计算机科学等领域国内外主流期刊EJOR, FGCS, INS, JORS, CAIE, TCS, JOCO等发表学术论文70余篇。

 

联系人：刘龙城