1. Наука
  2. Видання
  3. Системи обробки інформації
  4. 1(117)'2014
  5. О свойствах оптимальности метода минимизации суммарного запаздывания на одиночном устройстве на основе рангового подхода и правил доминирования

О свойствах оптимальности метода минимизации суммарного запаздывания на одиночном устройстве на основе рангового подхода и правил доминирования

С. В. Минухин
Системи обробки інформації. — 2014. — № 1(117). — С. 122-128.
УДК 519.853
Мова статті: російська
Анотації на мовах:

Рассмотрен метод минимизации суммарного запаздывания работ на одиночном устройстве, сведенный к решению задачи нахождения кратчайшего гамильтонового пути в произвольном полносвязном графе на основе рангового подхода и правил доминирования. Рассмотрены свойства оптимальности метода на основе введенных определений локально-оптимального решения, локально-оптимального расписания на ранге и оптимальности получаемого итогового расписания. Сформулированы определения и предложения, определяющие оптимальность получаемых расписаний выполнения работ на основе доминирующих и строго доминирующих расписаний для взвешенного и невзвешенного случаев. Предложены метрики оценки улучшения результатов работы алгоритма при использовании правила доминирования. Приведены результаты вычислительного эксперимента по оцениванию улучшения работы алгоритма, подтверждающие целесообразность использования правил доминирования.
Ключові слова: расписание, работа, ранговый подход, правило доминирования, последовательность, метрика, граф
Інформація про авторів публікації:
Бібліографічний опис для цитування:
Минухин С. В. О свойствах оптимальности метода минимизации суммарного запаздывания на одиночном устройстве на основе рангового подхода и правил доминирования / С. В. Минухин  // Системи обробки інформації. — 2014. — № 1. — С. 122-128.