报 告 内 容 简 介 |
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.
|
浙公网安备 33100202001351号
