АЛГОРИТМ ДЛЯ ВЕРСИЙ ЗАДАЧИ Pm||Cmax С НЕПОЛНОЙ ИНФОРМАЦИЕЙ
Аннотация
Исследуются две модели с неполной информацией для задач теории расписаний с идентичны-
ми процессорами. Предлагается общая параметрическая схема построения решений для таких задач. Достигаются рекордные гарантированные оценки точности для алгоритмов при соответст
вующих параметрах, которые доказывают принципиальное различие моделей.
Об авторах
В. М. Котов
Белорусский государственный университет
Беларусь
Беларусь
Х. Келлерер
Университет Граца, Университетштрассе 15
Австрия
Австрия
Н. Браунер
Университет Гренобля
Франция
Франция
Г. Финке
Россия
Список литературы
1. Graham, R.L. Bounds for certain multi-processing anomalies / R.L. Graham // Bell System
2. Technical J. – 1966. – Vol. 45. – P. 1563–1581.
3. Galambos, G. An on-line scheduling heuristic with better worst case ratio than Graham’s list
4. scheduling / G. Galambos, G. Woeginger // SIAM J. on Computing. – 1993. – Vol. 22. – P. 349–355.
5. Fleischer, R. Online scheduling revisited / R. Fleischer, M. Wahl // J. of Scheduling. –
6. – Vol. 3. – P. 343–353.
7. Faigle, U. On the performance of on-line algorithms for partition problems / U. Faigle,
8. W. Kern, G. Turan // Acta Cybernetica. – 1989. – Vol. 9. – P. 107–119.
9. Rudin III, J.F. Improved bounds for the online scheduling problem / J.F. Rudin III, R. Chandrasekaran // SIAM J. on Computing. – 2003. – Vol. 32. – P. 717–735.
10. Semi on-line algorithms for the partition problem / H. Kellerer [et al.] // Operations Research
11. Letters. – 1997. – Vol. 21. – P. 235–242.
12. Azar, Y. On-line bin-stretching / Y. Azar, O. Regev // Theoretical Computer Sci. – 2001. –
13. Vol. 268. – P. 17–41.
14. Cheng, T.C.E. Semi-on-line multiprocessor scheduling with given total processing time /
15. T.C.E. Cheng, H. Kellerer, V. Kotov // Theoretical Computer Sci. – 2005. – Vol. 337. – P. 134–146.
16. Аlbers, S. Semi-Online Scheduling Revisited / S. Albers, M. Hellwig // Theoretical Computer
17. Sci. – 2012. – Vol. 443. – P. 1–9.
Рецензия
Для цитирования:
Котов В.М., Келлерер Х., Браунер Н., Финке Г. АЛГОРИТМ ДЛЯ ВЕРСИЙ ЗАДАЧИ Pm||Cmax С НЕПОЛНОЙ ИНФОРМАЦИЕЙ. Информатика. 2012;(4(36)):81-86.
Просмотров: 604
Послать статью по эл. почте 