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