An efficient best response heuristic for a non-preemptive strictly periodic scheduling problem

International audienceWe propose an enhanced version of a original heuristic first proposed in Al Sheikh (2011) to solve a NP-hard strictly periodic scheduling prob- lem. Inspired by game theory, the heuristic reaches an equilibrium by iteratively solving best response problems. Our contribution is to greatly improve its efficiency, taking advantage of the two-dimensionality of the best response problem. The results show that the new heuristic compares favorably with MILP solutions