Single-Machine Rescheduling with Rejection and an Operator No-Availability Period

In this paper, we investigate a rescheduling problem with rejection and an operator non-availability period on a single machine. An optimal original schedule with the objective of minimizing the total weighted completion time has been made in a deterministic production scheduling system without an unavailable interval. However, prior to the start of formal job processing, a time interval becomes unavailable due to the operator. No jobs can start or complete in the interval; nonetheless, a job that begins prior to this interval and finishes afterward is possible (if there is such a job, we call it a crossover job). In order to deal with the operator non-availability period, job rejection is allowed. Each job is either accepted for processing or rejected by paying a rejection cost. The planned original schedule is required to be rescheduled. The objective is to minimize the total weighted completion time of the accepted jobs plus the total penalty of the rejected jobs plus the weighted maximum tardiness penalty between the original schedule and the new reschedule. We present a pseudo-polynomial time dynamic programming exact algorithm and subsequently develop it into a fully polynomial time approximation scheme.