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*.