Sensitivity analysis in the single-machine scheduling problem with max–min criterion

In this paper, the single-machine scheduling problem 1|prec|fmax is considered. It is one of the most general scheduling problems for which an efficient, polynomial algorithm has been developed. It is always possible to calculate quickly one optimal solution (a sequence of jobs) in that problem. However, the set of all optimal solutions may contain a lot of other sequences, so it is important to give a full characterization of that set. This paper consists of two parts. In the first part, some sufficient and necessary conditions of optimality of a given solution to the problem 1|prec|fmax are proved. In the second part, an application of these conditions to the sensitivity analysis is presented.