A unified approach for the scheduling problem with rejection

This paper is devoted to the scheduling problem with rejection. This problem is to determine which jobs should be accepted or rejected, and then to schedule the accepted jobs on machines so that total rejection cost plus schedule cost is minimized, or total revenue minus schedule cost is maximized. The latter equivalent maximization problem is called the order acceptance and scheduling problem. The main result of this paper is very simple. The scheduling problem with rejection in which the schedule cost is the sum of job completion costs can be converted into the ordinary scheduling problem with slightly modified job completion costs. This enables us to apply algorithms developed for ordinary scheduling problems to the corresponding scheduling problems with rejection. The effectiveness of the proposed conversion method will be demonstrated by numerical experiment: Several types of single-machine scheduling problems with rejection are solved by our exact algorithms for ordinary single-machine scheduling problems. As a result, the proposed method is shown to outperform the best branch-and-bound algorithm so far.