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