Job selection in a heavily loaded shop

Recently, Slotnick and Morton address a job selection problem in a heavily loaded shop, where a tradeoff is sought between the reward obtained when a job is accepted for processing and the lateness penalty incurred when such a job is actually delivered. They provide a branch and bound algorithm and a couple of heuristics for the problem’s solution. They do not, however, resolve the issue of problem complexity. In this note, the paper first establishes that the problem is NP-hard. It then goes on to provide two pseudo-polynomial time algorithms, which also show that the problem is solvable in polynomial time if either the job processing times or the job weights for the lateness penalty are equal. The paper provide a fully polynomial time approximation scheme which always generates a solution within a specified percentage of the optima.