We investigate the two-machine n-job flow-shop scheduling problem with
the objective of minimizing the makespan and given non-availability
intervals on each of the two machines. It was proven recently that this
problem is NP-hard even if there is only one non-availability interval
either on the first machine or on the second machine. If there are no
non-availability intervals on any machine, then the two-machine flow-shop
problem may be solved using Johnson's schedule constructed in O(n log n)
time. Our results demonstrate that the optimality of Johnson's schedule
is not violated if there exist only sufficiently small non-availability
intervals. The instrument we use is stability analysis which answers the
question how stable the property of a schedule to be optimal is if there
are independent changes in the processing times of the jobs.