|Minimizing total weighted completion time with uncertain data: a stability approach
|Egorova, N. G.
Sotskov, Y. N.
|публикации ученых;одностадийное обслуживания требований;неопределенность длительностей обслуживания требований;single-machine scheduling;uncertain processing times
|Egorova, N. G. Minimizing total weighted completion time with uncertain data: a stability approach / N. G. Egorova, Y. N. Sotskov, Frank Werner // Automation and Remote Control. – 2010. – Vol. 71, № 10. – P. 2038–2057.
|A single-machine scheduling problem is investigated provided that the input data are uncertain: The processing time of a job can take any real value from the given segment. The criterion is to minimize the total weighted completion time for the n jobs. As a solution concept to such a scheduling problem with an uncertain input data, it is reasonable to consider a minimal dominant set of job permutations containing an optimal permutation for each possible realization of the job processing times. To find an optimal or approximate permutation to be realized, we look for a permutation with the largest stability box being a subset of the stability region. We develop a branch-and-bound algorithm to construct a permutation with the largest volume of a stability box. If several permutations have the same volume of a stability box, we select one of them due to one of two simple heuristics.
|Appears in Collections:
|Публикации в зарубежных изданиях
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.