• A
  • A
  • A
  • АБB
  • АБB
  • АБB
  • А
  • А
  • А
  • А
  • А
Обычная версия сайта

Статья

Лексикографический алгоритм для решения конвейерной задачи

Чусовлянкин А. А., Морозенко В. В.

Cоставление оптимальных расписаний, с одной стороны, является практической потребностью и диктуется необходимостью экономии ресурсов, например, времени выполнения комплекса заданий в многопроцессорных вычислительных системах. С другой стороны, многие из задач теории расписаний являются NP-трудными и не могут быть решены точно за полиномиальное время ни одним из известных алгоритмов. Конвейерная задача – это одна из известных задач, в которой несколько специализированных исполнителей должны в кратчайшие сроки выполнить набор многоэтапных заданий. Если все задания являются двухэтапными, то для решения конвейерной задачи существует точный алгоритм, имеющий полиномиальную сложность относительно числа заданий. Однако, для случаев, когда число этапов превосходит 2, аналогичного алгоритма пока не существует. На практике в этой ситуации используют либо тривиальный переборный алгоритм с экспоненциальной сложностью, когда число заданий не слишком велико, либо какой-либо из быстрых приближенных алгоритмов, например, фронтальный алгоритм. В данной работе предложен новый подход для быстрого приближенного решения конвейерной задачи с числом этапов, превосходящим 2, а именно, – лексикографический алгоритм. В рассматриваемом алгоритме используется двойная сортировка. Сначала для каждого задания сортируются этапы по убыванию их длительности, в результате чего каждому заданию сопоставляется символьная строка, а затем полученные символьные строки сортируются по убыванию в лексикографическом порядке. Двойная сортировка способствует снижению вероятности возникновения интервалов вынужденного бездействия исполнителей. Подобные простои объясняются невозможностью выполнения последующего этапа какого-либо задания до тех пор, пока не завершится выполнение всех предыдущих этапов этого задания. Иногда простои неизбежны даже в оптимальных расписаниях. В таких случаях стремятся сократить время простоев. На наборе специально подготовленных тестовых заданий была изучена зависимость сложности, относительной погрешности и времени работы предложенного лексикографического алгоритма от количества заданий и числа этапов. Проведенное тестирование показало превосходство лексикографического алгоритма над фронтальным с точки зрения точности, а именно, в большинстве случаев относительная погрешность лексикографического алгоритма оказалась ниже, чем у фронтального алгоритма, однако фронтальный алгоритм находил расписание быстрее.