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.
The job shop problem under consideration can be described as follows. Each job Ji∈J={J1,J2,…,Jn} has to be processed on each machine Mj∈M={M1,M2,…,Mm} exactly once. Technological routes (machine orders) are fixed for all jobs, but may vary from job to job. A job Ji∈J consists of a chain of m uninterrupted operations (Oii1,Oii2,…,Oiim), where Oiik denotes the operation of job Ji on machine Mik∈M and (i1,i2,…,im) is a permutation of the indices {1,2,…,m}. At the scheduling stage, the processing time pij of operation Oij (Ji∈J, Mj∈M) is not fixed: pij may take any real value between a given lower bound aij⩾0 and a given upper bound bij⩾aij. The probability distribution of the random processing times is unknown. The criterion is mean flow time minimization. By adopting the three-field notation [10], we denote this problem by J|aij⩽pij⩽bij|Φ, where Φ is the objective function depending on the job completion times Ci, Ji∈J, with Φ(C1,C2,…,Cn)=∑ni=1Ci=∑Ci.
Problem J|aij⩽pij⩽bij|Φ aims to complement but not to replace other models of uncertain scheduling environments, e.g. a stochastic model [13] and a fuzzy model [14]. A former model is useful when we have enough prior information to characterize the probability distributions of random processing times and there is a large number of realizations of similar processes, but it may have a limited significance for a small number of realizations. In [6], uncertainty of the processing times was modeled by means of fuzzy numbers for mean flow time minimization and for other criteria. The known results and current trends in the field of scheduling under fuzziness have been presented in [14]. To model scheduling in an uncertain environment, a two-person non-zero sum game was introduced in [5], where the decision maker was considered as player 1 and `nature' as player 2.
In Section 4 we have developed branch-and-bound algorithms for the general case of a job shop problem. Instead of Algorithm B&B1, one can use any known branch-and-bound method developed for the problem J∥∑Ci after a simple modification with the aim to construct the k best schedules. However, the question which still remains open, is how to choose k to have a guarantee that the k best schedules contain an exact solution to problem J|aij⩽pij⩽bij|∑Ci. To answer this question, we have available Lemma 2 and experimental results given in [15] for calculating the stability radius of an optimal schedule for randomly generated job shop problems. In particular, in all experiments presented in Table 1, we used View the MathML source which was sufficient to obtain an exact solution for all instances considered. For the computational results presented in Table 2, we used View the MathML source, View the MathML source and View the MathML source depending on the problem size and on the uncertainty of the processing times. As follows from Table 2, for some instances these values of View the MathML source were not sufficient in the sense that the cardinality of the set of schedules which may be optimal for some input vectors p∈T was larger than the value of k used.
Algorithm B&B2 constructs a set of all `potentially optimal schedules' for problem J|aij⩽pij⩽bij|∑Ci and guarantees an exact solution after a complete realization. Moreover, its running time was less than that of Algorithm B&B1. The `heuristic' Algorithm B&B2∗ was better than Algorithm B&B1∗ both in the running time as well as in the number of instances for which a better solution was obtained.