Some new efficient methods to solve the n/1/ri/κàTi scheduling problem

In this paper, the authors prove a sufficient condition for local optimality to solve the n/1/ri/ΣTi scheduling problem which is known to be NP-hard. They then define a new dominant subset of schedules on the basis of this condition and propose several new approximate algorithms to construct schedules belonging to this subset. Numerical experiments enable the authors to compare them with classical approximate algorithms.