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

Про властивості оптимальності методу мінімізації сумарного запізнювання на одиночному пристрої на основі рангового підходу і правил домінування

С.В. Мінухін
Анотації на мовах:

Розглянуто метод мінімізації сумарного запізнювання робіт на одиночному пристрої, зведений до вирішення задачі знаходження найкоротшого гамільтонового шляху в довільному повнозв’язному графі на основі рангового підходу і правил домінування. Розглянуто властивості оптимальності методу на основі введених визначень локальнооптимального рішення, локально-оптимального розкладу на ранзі і оптимальності одержуваного підсумкового розкладу. Сформульовано визначення та пропозиції, що визначають оптимальність одержуваних розкладів виконання робіт на основі домінуючих і строго домінуючих розкладів для зваженого і незваженого випадків. Запропоновано метрики оцінки поліпшення результатів роботи алгоритму при використанні правила домінування. Наведено результати обчислювального експерименту з оцінювання поліпшення роботи алгоритму, які підтверджують доцільність використання правил домінування.
Ключові слова: розклад, робота, ранговий підхід, правило домінування, послідовність, метрика, граф