Zurück zu den Preprints des Jahres 1998


Mean Flow Time Minimization with Unit Processing Times

by Lai, Tsung-Chyan, Sotskov, Yuri N., Sotskova, Nadezhda Y., Werner, Frank.

Series: 1998-15, Preprints

90B35 Scheduling theory, deterministic
90C31 Sensitivity, stability, parametric optimization

A job shop scheduling problem with the objective of minimizing the
sum of completion times under uncertain numerical data is modelled in terms of a
mixed graph. It is assumed that only the structural input data are fixed while for the
operation processing times only their lower and upper bounds are known before scheduling.
We develop an approach for dealing with such `strict uncertainty' based on a stability analysis of
an optimal schedule. Two variants of a branch and bound method are developed. Along with implicit
enumerations based on a branch and bound method, we realize
an explicit enumeration of all feasible schedules, and all algorithms have
been estimated on randomly generated job shop problems.

Scheduling, Job shop, Mean flow time, Uncertainty

This paper was published in:
European Journal of Operat