Series: 2013-09, Preprints
Abstract:
Optimal scheduling is considered as sequencing the given activities over time in order to meet some given objective. Activities (jobs, operations) represent processes which use resources (machines) to produce goods or to provide services.
This work presents a survey of scheduling and sequencing problems with interval or uncertain data which can be solved by a stability method. It
is assumed that the job processing times (and other numerical parameters) may take any values from
given closed intervals.
For different types of problems, we discuss mathematical models, known results, and developed algorithms,
which are based on a stability analysis of an optimal
solution with respect to possible variations of the input parameters.
The main attention is paid to multi-stage
processing systems with a fixed job route through the given
machines, but we also deal with single-stage scheduling problems.
The surveyed stability method combines a stability analysis, a multi-stage scheduling decision framework
(the off-line planning stage and the on-line scheduling stages), and the solution concept of a minimal
dominant set of schedules that optimally covers all scenarios in the sense
that for any scenario such a set contains at least one solution (an optimal sequence).
The results discussed in this survey have been obtained in the period from 1988 to 2013.
This work will provide the reader with a comprehensive
understanding of the stability method and the models
appropriate for scheduling and sequencing with interval data. This survey shows how one can use the stability of an optimal (or near optimal) sequence of the given activities to overcome the uncertainty of the numerical input data.
Keywords:
Uncertainty, General shop, Job shop, Flow shop, Single machine scheduling