报告题目：带运输时间的调度问题的近似算法的研究

报 告 人：韩  鑫

报告时间：4月24日上午8:50-9:50

报告地点（Venue）： 腾讯会议：会议号：493485227，会议密码：106675.

报告人简介： 韩鑫，大连理工大学教授，博士生导师，主要研究方向理论计算机科学中算法设计和分析，具体研究调度，装箱等相关问题。近10年，主持国家自然科学基金面上项目2项、青年项目1项。在国内外期刊和会议发表学术论文40 余篇。

摘 要: 主要介绍三种模型，针对每种模型，我们给出目前最好的近似算法，其中也会介绍一下近似算法设计的一些思想。

报告题目：  Rescheduling for new orders on a single machine with rejection

报 告 人：罗文昌（宁波大学）

报告时间： 4月24日上午10:00-11:00

报告地点： 腾讯会议：会议号：493485227，会议密码：106675.

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

摘 要：We consider a single machine rescheduling problem where a set of original jobs has been scheduled to minimize the total weighted completion time. However, before formal processing begins, a new set of jobs arrives and creates a disruption. To reduce the negative impact of new jobs and keep an acceptable service level for the original jobs, the decision maker can reject a subset of the new jobs by paying certain rejection penalties, and reschedule the original and the remaining new jobs without excessively disrupting the original schedule, which is measured by the maximum completion time deviation for any original jobs between the original and adjusted schedules. We examine a general model where the maximum completion time disruption appears both as a constraint and as a part of the cost objective. The overall cost objective is to minimize the sum of total weighted completion time of the original jobs and the accepted new jobs in the adjusted schedule, the weighted maximum completion time deviation and the total rejection cost. We first provide a dynamic programming-based exact algorithm running in pseudo-polynomial time, and then propose a fully polynomial time approximation scheme. Given the NP-hardness for the studied problem, our result is the best possible.