Preview

Информатика

Расширенный поиск

АЛГОРИТМ ДЛЯ ВЕРСИЙ ЗАДАЧИ 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.

Просмотров: 170


Creative Commons License
Контент доступен под лицензией Creative Commons Attribution 4.0 License.


ISSN 1816-0301 (Print)
ISSN 2617-6963 (Online)