关键词: 重新排序, 不可用区间, 拒绝, 最大延误, 近似方案

Abstract: In this paper, we consider the single machine rescheduling problem with an unavailable interval and job rejection. In this problem, given a set of jobs to be processed on a single machine, each job has its processing time and its weight and a planned schedule with the goal to minimize the total weighted completion time has been made. The promised deliver time for each job is determined based on its completion time in the planned schedule. However, before the formal job processing begins, a given interval that is originally used to process jobs in the planned schedule becomes unavailable due to the temporary occupation for maintaining the machine. The planned schedule becomes unfeasible and is required to reschedule. To assure that the tardiness penalty for jobs is not too much in the adjusted schedule, the decision-maker has the option to reject some jobs by paying the corresponding reject costs. The task is to determine the accepted set of jobs and the rejected set of jobs and reschedule the accepted jobs subject to a given unavailable interval on the machine to minimize the sum of the total weighted completion time for the accepted jobs, the total reject cost for the rejected jobs and the weighted maximum tardiness penalty. This problem is NP-hard. We propose a pseudo-polynomial time dynamic programming exact algorithm and a fully polynomial time approximation scheme by using the sparse technique.

Key words: rescheduling, unavailable interval, rejection, maximum tardiness, approximation scheme