Stability of a schedule minimizing mean flow time

This paper is devoted to the calculation of the stability radius of an optimal schedule for a general shop scheduling problem, where the objective is to minimize mean flow time. The stability radius denotes the largest quantity of independent variations of the processing times of the operations such that an optimal schedule of the problem remains optimal. We derive formulas for calculating the stability radius, and necessary and sufficient conditions when it is equal to zero. Moreover, computational results on the calculation of the stability radius for randomly generated job shop scheduling problems are discussed.