报告题目：Approximation scheme for rejection-allowed single-machine rescheduling

主 讲 人：罗文昌  教授（宁波大学）

报告时间：5月27日 14:00-15:00

报告地点：腾讯会议ID：446-182-620

主办单位：002cc白菜资讯

报告摘要：We study a novel rescheduling problem in which a set of jobs has been assigned an original schedule to minimize the total weighted completion time on a single machine, with the assumption but not with 100% certainty that all of them will be available when the planned processing begins. The need for rescheduling arises due to some jobs could not arrive in time; the decision-maker has to adjust the original schedule to account for the delayed jobs without causing excessive time disruption to the original schedule and to minimize their operational cost. While the decisionmaker can choose to reject any of the delayed or non-delayed jobs, the total rejection cost and the tardiness of each accepted job in the adjusted schedule are strictly upper bounded by given thresholds, respectively. The total operational cost includes three components: the total weighted completion time of the accepted jobs, the total rejection cost of the rejected jobs, and the penalty on the maximum tardiness for the accepted jobs. We study this novel rescheduling problem from approximation algorithm perspective, as it generalizes several classic NP-hard scheduling problems; we design a pseudo-polynomial time dynamic programming exact algorithm and, when the total rejection cost is unbounded, we develop the exact algorithm into a fully polynomial time approximation scheme.

主讲人简介： 罗文昌，男，宁波大学数学与统计学院教授，博士生导师。2011年6月获浙江大学数学博士学位，曾访问加拿大阿尔伯塔大学。主要研究领域为数学/运筹学/组合优化，研究方向为近似算法设计与分析及运筹优化建模。现主持国家自然科学基金面上项目1项，完成浙江省自然科学基金及教育部一般项目各1项。已在Algorithmica, JOS, EJOR, OMEGA，IPL，CIE，JOCO等国际主流期刊和ISSAC，COCOON等国际主流会议发表SCI/EI/SSCI检索论文30余篇。