Institute of Information Theories and Applications FOI ITHEA
Abstract:
We consider an uncertain version of the scheduling problem to sequence set of jobs J on a single
machine with minimizing the weighted total flow time, provided that processing time of a job can take on any real
value from the given closed interval. It is assumed that job processing time is unknown random variable before
the actual occurrence of this time, where probability distribution of such a variable between the given lower and
upper bounds is unknown before scheduling. We develop the dominance relations on a set of jobs J. The
necessary and sufficient conditions for a job domination may be tested in polynomial time of the number n = |J|
of jobs. If there is no a domination within some subset of set J, heuristic procedure to minimize the weighted total
flow time is used for sequencing the jobs from such a subset. The computational experiments for randomly
generated single-machine scheduling problems with n ≤ 700 show that the developed dominance relations are
quite helpful in minimizing the weighted total flow time of n jobs with uncertain processing times.