报 告 人

罗文昌 宁波大学数学与统计学院教授，博导

报告时间

2021年5月10日下午14:00

报告地点

椒江校区 电信学院会议室（行政楼223）

报

告

内

容

简

介

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.

承办学院

电子与信息工程学院（大数据学院）

发布日期

2021.05.08

欢迎广大教师、学生参加！