Stability of a schedule minimising the makespan for processing jobs on identical machines
研究了相同机器上最小化最大完工时间的最优调度方案，在部分作业加工时间可能偏离初始估计值时的稳定性，给出了不稳定性的充要条件、稳定性半径的上下界及计算公式。
A set of jobs has to be processed on identical machines. Every job may be processed on any available machine without preemptions. The criterion is to minimise the makespan (i.e. the completion time of the last job in a schedule). During the realisation of a schedule, durations of some jobs may deviate from the initial values estimated before scheduling. Other jobs have fixed durations that are known before scheduling. We conduct a stability analysis of the optimal semi-active schedule. First, we derive necessary and sufficient conditions for an optimal schedule to be unstable with respect to infinitely small variations of the non-fixed durations (the stability radius of an unstable schedule is equal to zero). Second, we show that the stability radius of an optimal schedule could be infinitely large. Furthermore, several lower and upper bounds on the stability radius have been established. Third, we derive a formula and develop an algorithm for calculating stability radii.