Two-machine job shop scheduling with optional job rejection

We investigate a two-machine job shop scheduling problem with optional job rejection. The target is to look for a feasible schedule for the set of accepted jobs so that the sum of the makespan of the accepted jobs and the total penalty of the rejected jobs is minimized. We propose an exact pseudo-polynomial dynamic programming algorithm, a greedy root 5+1/2 approximation algorithm, an LP-based e/e-1-approximation algorithm, and a fully polynomial time approximation scheme to solve it. We demonstrate that the proportionate case is NP-hard and provide an O(n(2))-time algorithm for the agreeable case.