ИСТИНА

Рассматриваются методы оценки сложности алгоритма решения NP-трудной в сильном смысле задачи теории расписаний для одного прибора с различными моментами поступления требований, продолжительностями обслуживания и директивными сроками . В качестве целевой функции выбрана минимизация максимального временного смещения. Для решения задачи предлагается использовать алгоритм, который с помощью оценок, получаемых при решении двойственной задачи, реализует метод ветвей и границ для получения точного решения исходной задачи [1]. Оценкой сложности примеров (различных наборов значений , ) будет количество точек ветвления в построеном дереве. Нетрудно оценить максимальное количество точек ветвления Алгоритм решения двойственной задачи имеет полиномиальную трудоёмкость. Для оценки эффективности предложенного алгоритма его необходимо протестировать на различных примерах. Самый простой способ генерации примеров – случайный. Все параметры требований задаются случайными величинами. Такой способ плох тем, что нет никакой гарантии, что будут рассмотрены различные типы примеров (в силу большого количества переменных), и примеры не будут повторяться. Также необходимо протестировать алгоритм на сложных примерах, а случайным методом гарантированно их получить невозможно. Если представить пример как точку в -мерном пространстве ( требований с тремя параметрами), то при равномерном распределении невозможно получить точки, достаточно удаленные от начала координат. Чтобы при случайной генерации примеров была возможность получить точки во всем пространстве, в [2] было предложено использовать нормальное распределение, благодаря чему существует вероятность достаточно сильного отклонения от нормы, что позволяет создавать более “удаленные” друг от друга примеры. Используя сгенерированные примеры, с помощью алгоритма и вариации параметров каждого требования в примере создавался новый пример, требующий больших вычислительных мощностей для нахождения оптимального решения. Также были предложены методы генерации L-примеров в шаре, P-примеров в параллелепипеде, G-примеров на кубе для оценки эффективности алгоритма решения задачи одного прибора, основанной численном количестве точек ветвления в построенном дереве решения.