Skip navigation
Please use this identifier to cite or link to this item:
Title: Minimizing total weighted completion time with uncertain data: a stability approach
Authors: Egorova, N. G.
Sotskov, Y. N.
Werner, Frank
Keywords: публикации ученых;одностадийное обслуживания требований;неопределенность длительностей обслуживания требований;single-machine scheduling;uncertain processing times
Issue Date: 2010
Publisher: MAIK Nauka
Citation: 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.
Abstract: 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:Публикации в зарубежных изданиях

Files in This Item:
File Description SizeFormat 
031024.pdf704.67 kBAdobe PDFView/Open
Show full item record Google Scholar

Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.