On finding stable PERT schedules with uncertain job durations

Session : SS13-1 / SS13 : Méthodes d'optimisation pour l'ordonnancement et la planification
Jeudi 11 février 15:00 - 16:40 Salle : CI2-05
Philippe Chrétienne, Pierre Fouilhoux, Alain Quilliot et Pascale Bendotti

We consider in this paper three stability problems that occur in PERT scheduling when the real durations of the jobs are larger than their planned durations. The similarity between a schedule of the real instance and a schedule of planned instance is dened as the number of jobs that are started at the same time in both schedules and the stability of a planned schedule is its similarity with the closest (i.e: most similar) schedule of the real instance. We rst assume that a planned schedule is known for the planned instance and provide a polynomial algorithm to nd the closest schedule of the real instance. We then add a common deadline to the planned instance and again provide a polynomial algorithm to nd a planned schedule whose stability is maximum. If a time-window constraint is added to the planned instance and to the real instance, we show that the problem of nding a planned schedule whose stability is maximum is NP-hard and provide some polynomial special cases.

Mots clés : PERT scheduling problem, stability, complexity