98-15
Mean Flow Time Minimization with Unit Processing Times
by Lai, Tsung-Chyan; Sotskov, Yuri N.; Sotskova, Nadezhda Y.; Werner, Frank
Preprint series: 98-15, Preprints
The paper is published: European Journal of Operational Research, Vol. 159, No.3, 2004, 558 - 573.
- MSC:
- 90B35 Scheduling theory, See also {68M20}
- 90C31 Sensitivity, stability, parametric optimization
Abstract: 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.
Keywords: Scheduling, Job shop, Mean flow time, Uncertainty
The author(s) agree, that this abstract may be stored asfull text and distributed as such by abstracting services.