Worst case performance evaluation of flexible solutions in single machine scheduling

Colloque avec actes et comité de lecture. nationale.National audienceIn this paper, we consider the problem of evaluating the worst case performance of flexible solutions in single machine scheduling. A flexible solution is a set of schedules following a structure defined by a partial order of jobs and a type of schedules. here, we consider active and non-delay schedules. The proposed structure allows the decision maker to dispose of some flexibility (a set of schedules instead of one schedule) that can be used on-line to absorb the impact of data disturbances related to, for example, job arrival, tool availability or machine breakdowns. The performance is a function of (i) the best case performance providing the decision maker a lower bound of the performance, (ii) the worst case performance giving him a guarantee about how poorly the solution may perform, in both cases when following the considered structure. The worst cases correspond to new scheduling problems, in which a regular criterion must be maximized. We present new algorithms and/or new computational complexity results, in presence of: one machine, different release dates, precedence constraints and various criteria to be maximized. || Nous nous intéressons dans ce papier à l'évaluation de performance dans le pire des cas pour des solutions d'ordonnancement flexibles pour des problèmes d'ordonnancement à une machine. Une solution flexible est définie par un ordre partiel et par un typ