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