Abstract
A classical single machine minmax common due-date assignment (CON) problem is studied. The problem is extended (independently) to the following settings: (1) general position-dependent job processing times are assumed, and an efficient O(n4) solution procedure is introduced; (2) the option of job rejection is allowed, and this case is shown to be solved in O(n5); (3) a deterioration effect is considered, and an O(n2) solution algorithm is proposed; (4) parallel uniform machines are considered; and (5) the machine setting is that of a permutation flowshop. The last two settings are known to be NP hard, and efficient heuristic procedures are introduced and shown numerically to produce very small optimality gaps.
Disclosure statement
No potential conflict of interest was reported by the authors.