Optimal algorithms for single‐machine scheduling with rejection to minimize the makespan

In this paper we consider the single‐machine scheduling problem with rejection. Each job has an arrival time, a processing time and a rejection penalty. The objective is to minimize the sum of the makespan of the accepted jobs and the total rejection penalty of the rejected jobs. First, we present a polynomial‐time algorithm for the off‐line problem when split is allowed. Second, for the on‐line problem with arbitrary arrival times, we provide a determined on‐line algorithm with the best‐possible competitive ratio 2. Finally, for the on‐line problem with at most two distinct arrival times, we provide a determined on‐line algorithm with the best‐possible competitive ratio $(\sqrt{5}+1)/2\approx 1.618$.