The single machine serial batch scheduling problem with rejection to minimize total completion time and total rejection cost

• We study a single machine serial batch scheduling problem with rejection.
• The objectives are to minimize total completion time and total rejection cost.
• We study four different variants of the problem.
• We prove that one variant is efficiently solvable while all other are NPNP-hard.
• We provide an ε  -approximation algorithm for one of the NPNP-hard variants.

We study a scheduling problem with rejection on a single serial batching machine, where the objectives are to minimize the total completion time and the total rejection cost. We consider four different problem variations. The first is to minimize the sum of the two objectives. The second and the third are to minimize one objective, given an upper bound on the value of the other objective and the last is to find a Pareto-optimal solution for each Pareto-optimal point. We provide a polynomial time procedure to solve the first variation and show that the three other variations are NPNP-hard. For solving the three NPNP-hard problems, we construct a pseudo-polynomial time algorithm. Finally, for one of the NPNP-hard variants of the problem we propose an FPTAS, provided some conditions hold.