JOB SELECTION IN A HEAVILY LOADED SHOP

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