Search

The problem of scheduling optimally a given set of jobs on a single machine is studied. The lower and upper bounds on the admissible duration of each job are known. The optimality criterion of the schedule is the minimum total completion time of a given set of jobs. Some properties of the optimality region for a job permutation are investigated. Polynomial algorithms for constructing the optimality region for a job permutation and also for calculating the volume of this region are developed. The existence conditions of an empty optimality region for a job permutation are determined. A criterion for the existence of a job permutation with the maximum possible volume of the optimality region is established.

A set of jobs has to be processed on a single machine without preemptions of a job. The exact value of the job processing time (duration) is unknown until the completion of the job. Lower and upper bounds on the job duration are known before scheduling. The problem is to minimize total completion time of the given jobs. We apply a stability approach to this scheduling problem and introduce an optimality region for a job permutation as an optimality measure of the schedule. We investigate properties of the optimality region and derive O(n) algorithms for calculating the relative perimeter of the optimality region (the sum of the relative optimality sets of the n jobs) for a fixed job permutation. We present computational results for a comparison of the relative perimeters of the optimality regions for the mid-point permutations, the lower-bound permutations, the upper-bound permutations and the permutations having the largest optimality box.

An uncertain single-machine scheduling problem is considered, where the processing time of a job can take any real value from a given segment. The criterion is to minimise the total weighted completion time of the n jobs, a weight being associated with each given job. We use the optimality box as a stability measure of the optimal schedule and derive an O(n)-algorithm for calculating the optimality box for a fixed permutation of the given jobs. We investigate properties of the optimality box using blocks of the jobs. If each job belongs to a single block, then the largest optimality box may be constructed in time. For the general case, we apply dynamic programming for constructing a job permutation with the largest optimality box. The computational results for finding a permutation with the largest optimality box show that such a permutation is close to an optimal one, which can be determined after completing the jobs when their processing times became known.

We consider a single machine scheduling problem with uncertain durations of the given jobs. The objective function is minimizing the sum of the job completion times. We apply the stability approach to the considered uncertain scheduling problem using a relative perimeter of the optimality box as a stability measure of the optimal job permutation. We investigated properties of the optimality box and developed algorithms for constructing job permutations that have the largest relative perimeters of the optimality box. Computational results for constructing such permutations showed that they provided the average error less than 0 . 74 % for the solved uncertain problems.

We study a single-machine scheduling problem to minimize the total completion time of the given set of jobs, which have to be processed without job preemptions. The lower and upper bounds on the job duration is the only information that is available before scheduling. Exact values of the job durations remain unknown until the completion of the jobs. We use the optimality region for the job permutation as an optimality measure of the optimal schedule. We investigate properties of the optimality region and derive O ( n ) -algorithm for calculating a quasi-perimeter of the optimality set (i.e., the sum of lengths of the optimality segments for n given jobs). We develop a fast algorithm for finding a job permutation having the largest quasi-perimeter of the optimality set. The computational results in constructing such permutations show that they are close to the optimal ones, which can be constructed for the factual durations of all given jobs.

The paper deals with scheduling under uncertainty of the job processing times. The actual value of the processing time of a job becomes known only when the schedule is executed and may be equal to any value from the given interval. We propose an approach which consists of calculating measures of problem uncertainty to choose an appropriate method for solving an uncertain scheduling problem. These measures are based on the concept of a minimal dominant set containing at least one optimal schedule for each realization of the job processing times. For minimizing the sum of weighted completion times of the $$n$$ jobs to be processed on a single machine, it is shown that a minimal dominant set may be uniquely determined. We demonstrate how to use an uncertainty measure for selecting a method for finding an effective heuristic solution of the uncertain scheduling problem. The efficiency of the heuristic $$O(n\log n)$$ -algorithms is demonstrated on a set of randomly generated instances with $$100 \le n \le 5{,}000.$$ A similar uncertainty measure may be applied to many other scheduling problems with interval processing times.

The flow-shop minimum-length scheduling problem with n jobs processed on two machines is addressed where processing times are uncertain: only lower and upper bounds of the random processing times are given before scheduling, but their probability distributions are unknown. For such a problem, there may not exist a dominant schedule that remains optimal for all possible realizations of the processing times and so we look for a minimal set of schedules that are dominant. We obtain necessary and sufficient conditions for the case when it is possible to fix the order of two jobs in a minimal set of dominant schedules. The necessary and sufficient conditions are proven for the case when one schedule dominates all the others. We characterize also the case where there does not exist non-trivial schedule domination. All the conditions proven may be tested in polynomial time of n.

The flow-shop minimum-length scheduling problem with n jobs processed on two machines is addressed where processing times are uncertain (only lower and upper bounds for the random processing time are given, while the probability distribution between these bounds is unknown). For such a problem, there often does not exist a dominant schedule that remains optimal for all possible realizations of the job processing times, and so we look for a minimal dominant set of schedules, which may be represented by a partial job order. We investigate properties of this partial job order and show how to construct this order in polynomial time. The approach based on a set of dominant schedules allows us to find special cases of the problem when it is possible to find an optimal schedule in spite of the uncertainty of the numerical data.

The flow-shop minimum-length scheduling problem with n jobs processed on two machines is addressed where processing times are uncertain: only lower and upper bounds of the random processing times are given before scheduling, but their probability distributions are unknown. For such a problem, there may not exist a dominant schedule that remains optimal for all possible realizations of the processing times and so we look for a minimal set of schedules that are dominant. We obtain necessary and sufficient conditions for the case when it is possible to fix the order of two jobs in a minimal set of dominant schedules. The necessary and sufficient conditions are proven for the case when one schedule dominates all the others. We characterize also the case where there does not exist non-trivial schedule domination. All the conditions proven may be tested in polynomial time of n.

We consider a job shop scheduling problem under uncertain processing times and fixed precedence and capacity constraints. Each of the random processing times can take any real value between given lower and upper bounds. The goal is to find a set of schedules which contains at least one optimal schedule (with mean flow time criterion) for any admissible realization of the random processing times. In order to compute such a set of schedules efficiently and keep it as small as possible, we develop several exact and heuristic algorithms and report computational experience based on randomly generated instances.

We address the two–machine flowshop scheduling problem to minimize makespan where jobs have random and bounded processing times. The probability distributions of job processing times are unknown and only the lower and upper bounds of processing times are given before scheduling. In such cases there may not exist a unique schedule that remains optimal for all possible realizations of processing times, and therefore, a set of schedules has to be considered which dominates all other schedules. In this paper, we find some sufficient conditions for the considered problem.

We consider a scheduling problem with the objective of minimising the makespan under uncertain numerical input data (for example, the processing time of an operation, the job release time and due date) and fixed structural input data (for example the precedence and capacity constraints). We assume that at (before) the scheduling stage the structural input data are known and fixed but all we know about the numerical input data are their upper and lower bounds, where the uncertain numerical data become realised at the control stage as the scheduled process evolves. After improving the mixed graph model, we present an approach for dealing with our scheduling problem under uncertain numerical data based on a stability analysis of an optimal makespan schedule. In particular, we investigate the candidate set of the critical paths in a circuit-free digraph, characterise a minimal set of the optimal schedules, and develop an optimal and a heuristic algorithm. We also report computational results for randomly generated as well as well-known test problems.

We consider an uncertain single-machine scheduling problem, in which the processing time of a job can take any real value from a given closed interval. The criterion is to minimize the sum of weighted completion times of the n jobs, a weight being associated with each job. For a job permutation, we study the stability box, which is a subset of the stability region. We derive an O(n logn) algorithm for constructing a job permutation with the largest dimension and volume of a stability box. The efficiency of such a permutation is demonstrated via a simulation on a set of randomly generated instances with 1000 ≤ n ≤ 2000. If several permutations have the largest dimension and volume of a stability box, the developed algorithm selects one of them due to a mid-point heuristic.

The usual assumption that the processing times of the operations are known in advance is the strictest one in deterministic scheduling theory and it essentially restricts its practical aspects. Indeed, this assumption is not valid for the most real-world processes. This survey is devoted to a stability analysis of an optimal schedule which may help to extend the significance of scheduling theory for some production scheduling problems. The terms ‘stability’, ‘sensitivity’ or ‘postoptimal analysis’ are generally used for the phase of an algorithm at which a solution (or solutions) of an optimization problem has already been found, and additional calculations are performed in order to investigate how this solution depends on the problem data. We survey some recent results in the calculation of the stability radius of an optimal schedule for a general shop scheduling problem which denotes the largest quantity of independent variations of the processing times of the operations such that this schedule remains optimal. We present formulas for the calculation of the stability radius, when the objective is to minimize mean or maximum flow time. The extreme values of the stability radius are of particular importance, and these cases are considered more in detail. Moreover, computational results on the calculation of the stability radius for randomly generated job shop scheduling problems are briefly discussed. We also show that the well-known test problem with 6 jobs and 6 machines has both stable and unstable optimal makespan schedules.