Rescheduling for new orders on a single machine with rejection

We consider a single machine rescheduling problem where a set of original jobs have been scheduled to minimize the total weighted completion time. However, before formal processing begins, a new set of jobs arrives and creates a disruption. 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. The 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 from the approximation algorithm perspective. In addition, we conduct extensive computational experiments to evaluate the performance of our proposed methods, and provide some managerial insights on their applicability under different situations.