Система моделювання для дослідження ефективності пдс-алгоритму задачі мінімізації сумарного запізнення виконання завдань

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

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


Завантажити (pdf)