Scheduling is one of the common steps of decision-making which is important in manufacturing and in service industries. A scheduling problem deals with an optimal allocation of a limited number of given resources (e.g. machines) to given tasks (e.g. jobs) over time. Modern scheduling theory contains two main parts, based on deterministic and stochastic models. In spite of a huge number of papers and books published about scheduling, the utilization of numerous theoretical results of classical scheduling theory in most production environments is far away from the desired volume. One of the main reasons for this gap between scheduling theory and practice is connected with the usual theoretical assumptions that the processing times of the jobs are known exactly before scheduling (for deterministic models) or that they are random values with known probability distributions (for stochastic models).
In this dissertation, a model of more realistic scheduling scenarios is considered. It is assumed that in the practical realization of a schedule, the processing time of an operation may take any real value between lower and upper bounds, which are only given before applying a scheduling procedure, and there is no prior information about the probability distribution of a random processing time. For such an uncertain scheduling problem, there does usually not exist a unique schedule that remains optimal for all possible realizations of the processing times, and a set of schedules (we call it a solution) has to be considered which dominates all other schedules for the given criterion. To find such a schedule set with minimal cardinality (a minimal solution), we use a stability analysis of an optimal schedule with respect to the perturbations of the processing times, and introduce the notion of the relative stability radius of an optimal schedule. The relativity is considered with respect to the polytope of feasible vectors of processing times and with respect to a set B of semiactive schedules for which the superiority of a schedule s at hand has to be guaranteed.
We use the mixed (disjunctive) graph model which is suitable for the whole scheduling process from the initial mixed graph G=(Q, A, E) representing the input data until a final digraph Gs representing schedule s. The set of vertices Q of a mixed graph G represents the set of operations which have to be processed. The set of arcs A defines precedence constraints and the set of edges E defines capacity constraints. Most results in this dissertation, obtained for the maximum (makespan) and mean flow time criteria, are formulated in terms of paths in the digraph Gs. In particular, we establish necessary and sufficient conditions for the case of an infinitely large relative stability radius of an optimal schedule s (under such conditions schedule s remains optimal for any feasible perturbations of the processing times), and a zero relative stability radius (when the optimality of schedule s is not stable). Formulas for calculating the exact value of the relative stability radius are based on a comparison of an optimal schedule s with other schedules from the set B, and we show how it is possible to restrict the number of schedules from the set B with which a comparison has to be made for the calculation of the relative stability radius.
The above results are used in exact and heuristic algorithms for constructing a solution and a minimal solution of a scheduling problem with uncertain processing times. The algorithms have been estimated on randomly generated deterministic and uncertain job shop problems. The main issue from our experiments is that an optimal schedule is usually stable if the processing times of the operations are real numbers. On the basis of the computational experiments on randomly generated uncertain job shop problems, the cardinality of the minimal solution set usually composes a small part of the cardinality of the set of semiactive schedules. This observation means that, even for the very challenging uncertain scheduling problem, a decision-maker only needs to consider a small number of schedules (due to the theoretical results and the software), and may choose the best schedule from the minimal solution set if additional information on the numerical data will be available at the stage of the realization of a schedule.
We outline some topics for future research which follow from the results obtained in the dissertation.