Система моделирования для исследования эффективности ПДС-алгоритма задачи минимизации суммарного запаздывания выполнения задач

Павлов О.А., Місюра О.Б., Халус О.А., Беньковський С.Б., Костик Д.Ю., Лисенький Т.М.

Разработана система моделирования для исследования эффективности ПДС-алгоритма (алгоритм с полиномиальной и экспоненциальной составляющими) задачи минимизации суммарного запаздывания выполнения задач, которая относится к NP-сложным; методика исследования задачи, а также генератор произвольных задач, охватывающих все подклассы задачи минимизации суммарного запаздывания (МСЗ). Построена такая схема исследования эффективности ПДС-алгоритма, позволяющая получить статистические характеристики решения задачи полиномиальной и экспоненциальной составляющими (оценки трудоемкости, процент задач решаемых полиномиально, оценка реального времени решения, процент решаемых задач реальным полным перебором).


Загрузить (pdf)