АЛГОРИТМ ДЛЯ ВЕРСИЙ ЗАДАЧИ Pm||Cmax С НЕПОЛНОЙ ИНФОРМАЦИЕЙ
Abstract
Исследуются две модели с неполной информацией для задач теории расписаний с идентичны-
ми процессорами. Предлагается общая параметрическая схема построения решений для таких задач. Достигаются рекордные гарантированные оценки точности для алгоритмов при соответст
вующих параметрах, которые доказывают принципиальное различие моделей.
About the Authors
В. Котов
Белорусский государственный университет
Belarus
Belarus
Х. Келлерер
Университет Граца, Университетштрассе 15
Austria
Austria
Н. Браунер
Университет Гренобля
France
France
Г. Финке
Russian Federation
References
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.
Review
For citations:
, , , . Informatics. 2012;(4(36)):81-86. (In Russ.)
Views: 603
Email this article 