Sotskov, Jurij NazarovičLai, Tsung-ChyanEgorova, Natalia G.Werner, FrankOtto-von-Guericke-Universität Magdeburg2025-05-292017https://epflicht.bibliothek.uni-halle.de/handle/123456789/4623887738605urn:nbn:de:gbv:3:2-725612552036FbTIBAn uncertain single-machine scheduling problem is considered, where the processing time of a job can take any real value from a given segment. The criterion is to minimize the total weighted completion time of the n jobs, a weight being associated with each given job. We use the optimality box as a stability measure of the optimal schedule and derive an O(n)-algorithm for calculating the optimality box for a fixed permutation of the given jobs. We investigate properties of the optimality box using blocks of the jobs. If each job belongs to a single block, then the largest optimality box may be constructed in O(n log n) time. For the general case, we apply dynamic programming for constructing a job permutation with the largest optimality box. The computational results for finding a permutation with the largest optimality box show that such a permutation is close to an optimal one, which can be determined after completing the jobs when their processing times became known.1 Online-Ressource (23 Seiten = 0,3 MB) : Diagrammeenghttp://rightsstatements.org/vocab/InC/1.0/510Book