关键词: 重新排序, 工件拒绝, 工件延误, 动态规划, 近似方案

Abstract:

In this paper, we investigate a rescheduling problem with rejection on a single machine due to the disruption of job delay. In this problem, we are given a set of jobs that are available at time zero in the planning horizon to be processed on a single machine. Each job has its processing time and weight. Before the formal processing begins, an original schedule according to the shortest weighted processing time first order is given with the goal to minimize the total weighted completion time. Based on the original schedule, the promised due date for each job is also given. However, when the formal processing starts, some jobs are delayed, which creates a disruption to the original schedule. Thus, it is necessary to adjust the original schedule, i.e., rescheduling. To achieve a reasonable service level, we are allowed to reject some delayed jobs by paying the corresponding rejection costs. In the adjusted schedule, the overall objective function is to minimize the sum of the total weighted completion time of the accepted jobs, the total rejection cost of the rejected jobs, and the weighted penalty for the maximum tardiness of the accepted jobs, while keeping the maximum tardiness no more than the given upper bound. For this problem, we design a dynamic programming exact algorithm running in pseudo-polynomial time. Furthermore, we derive a fully polynomial time approximation scheme by using the sparse technique.

Key words: rescheduling, job rejection, job delay, dynamic programming, approximation scheme