Recently Slotnick and Morton address a job selection problem in a heav
ily loaded shop, where a tradeoff is sought between the reward obtaine
d when a job is accepted for processing and the lateness penalty incur
red when such a job is actually delivered. They provide a branch and b
ound algorithm and a couple of heuristics for the problem's solution.
They do not, however, resolve the issue of problem complexity. In this
note, we first establish that the problem is NP-hard. We then go on t
o provide two pseudo-polynomial time algorithms which also show that t
he problem is solvable in polynomial time if either the job processing
times or the job weights for the lateness penalty are equal. We furth
er provide a fully polynomial time approximation scheme which always g
enerates a solution within a specified percentage of the optimal. Copy
right (C) 1997 Elsevier Science Ltd