Titre : Contraintes d’ordre pour ordonnancement à une machine avec coût polynomial Exposant : Christoph Dürr Résumé : Typically in a scheduling problem we are given jobs of different lengths $p_j$ and different priority weights $w_j$, and need to schedule them on a single machine in order to minimize a specific cost function. In this paper we consider the non-linear objectif function $\sum w_j C_j^\beta$, where $C_j$ is the completion time of job $j$ and $\beta>0$ is some arbitrary real constant. Except for $\beta=1$ the complexity status of this problem is open. Past research mainly focused on the quadratic case ($\beta=2$) and proposed different techniques to speed up exact algorithms. This paper proposes new pruning rules and generalizations of existing rules to non-integral $\beta$. An experimental study evaluates the impact of the proposed rules on the exact algorithm A*.