informИнформатикаInformatics1816-03012617-6963UIIP NASBinform-273Research ArticleСТАТЬИ ПО МАТЕРИАЛАМ КОНФЕРЕНЦИЙARTICLES ON THE MATERIALS CONFERENCEАЛГОРИТМ ДЛЯ ВЕРСИЙ ЗАДАЧИ Pm||Cmax С НЕПОЛНОЙ ИНФОРМАЦИЕЙКотовВ. М.КеллерерХ.БраунерН.ФинкеГ.Белорусский государственный университетBelarusУниверситет Граца, Университетштрассе 15AustriaУниверситет ГренобляFrance20122302201804(36)8186Copyright © Котов В.М., Келлерер Х., Браунер Н., Финке Г., 20182018Котов В.М., Келлерер Х., Браунер Н., Финке Г.Котов В.М., Келлерер Х., Браунер Н., Финке Г.Данная работа распространяется под лицензией Creative Commons Attribution 4.0.This work is licensed under a Creative Commons Attribution 4.0 License.https://inf.grid.by/jour/article/view/273

Исследуются две модели с неполной информацией для задач теории расписаний с идентичны-ми процессорами. Предлагается общая параметрическая схема построения решений для таких задач. Достигаются рекордные гарантированные оценки точности для алгоритмов при соответствующих параметрах, которые доказывают принципиальное различие моделей.

ReferencesGraham, R.L. Bounds for certain multi-processing anomalies / R.L. Graham // Bell SystemGraham, R.L. Bounds for certain multi-processing anomalies / R.L. Graham // Bell SystemTechnical J. – 1966. – Vol. 45. – P. 1563–1581.Technical J. – 1966. – Vol. 45. – P. 1563–1581.Galambos, G. An on-line scheduling heuristic with better worst case ratio than Graham’s listGalambos, G. An on-line scheduling heuristic with better worst case ratio than Graham’s listscheduling / G. Galambos, G. Woeginger // SIAM J. on Computing. – 1993. – Vol. 22. – P. 349–355.scheduling / G. Galambos, G. Woeginger // SIAM J. on Computing. – 1993. – Vol. 22. – P. 349–355.Fleischer, R. Online scheduling revisited / R. Fleischer, M. Wahl // J. of Scheduling. –Fleischer, R. Online scheduling revisited / R. Fleischer, M. Wahl // J. of Scheduling. –– Vol. 3. – P. 343–353.– Vol. 3. – P. 343–353.Faigle, U. On the performance of on-line algorithms for partition problems / U. Faigle,Faigle, U. On the performance of on-line algorithms for partition problems / U. Faigle,W. Kern, G. Turan // Acta Cybernetica. – 1989. – Vol. 9. – P. 107–119.W. Kern, G. Turan // Acta Cybernetica. – 1989. – Vol. 9. – P. 107–119.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.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.Semi on-line algorithms for the partition problem / H. Kellerer [et al.] // Operations ResearchSemi on-line algorithms for the partition problem / H. Kellerer [et al.] // Operations ResearchLetters. – 1997. – Vol. 21. – P. 235–242.Letters. – 1997. – Vol. 21. – P. 235–242.Azar, Y. On-line bin-stretching / Y. Azar, O. Regev // Theoretical Computer Sci. – 2001. –Azar, Y. On-line bin-stretching / Y. Azar, O. Regev // Theoretical Computer Sci. – 2001. –Vol. 268. – P. 17–41.Vol. 268. – P. 17–41.Cheng, T.C.E. Semi-on-line multiprocessor scheduling with given total processing time /Cheng, T.C.E. Semi-on-line multiprocessor scheduling with given total processing time /T.C.E. Cheng, H. Kellerer, V. Kotov // Theoretical Computer Sci. – 2005. – Vol. 337. – P. 134–146.T.C.E. Cheng, H. Kellerer, V. Kotov // Theoretical Computer Sci. – 2005. – Vol. 337. – P. 134–146.Аlbers, S. Semi-Online Scheduling Revisited / S. Albers, M. Hellwig // Theoretical ComputerАlbers, S. Semi-Online Scheduling Revisited / S. Albers, M. Hellwig // Theoretical ComputerSci. – 2012. – Vol. 443. – P. 1–9.Sci. – 2012. – Vol. 443. – P. 1–9.

The authors declare that there are no conflicts of interest present.