Рассмотрен метод минимизации суммарного запаздывания работ на одиночном устройстве, сведенный к решению задачи нахождения кратчайшего гамильтонового пути в произвольном полносвязном графе на основе рангового подхода и правил доминирования. Рассмотрены свойства оптимальности метода на основе введенных определений локально-оптимального решения, локально-оптимального расписания на ранге и оптимальности получаемого итогового расписания. Сформулированы определения и предложения, определяющие оптимальность получаемых расписаний выполнения работ на основе доминирующих и строго доминирующих расписаний для взвешенного и невзвешенного случаев. Предложены метрики оценки улучшения результатов работы алгоритма при использовании правила доминирования. Приведены результаты вычислительного эксперимента по оцениванию улучшения работы алгоритма, подтверждающие целесообразность использования правил доминирования.

  Повний текст PDF - 460.16 Kb    Зміст випуску     Цитування публікації

  Якщо, ви не знайшли інформацію про автора(ів) публікації, маєте бажання виправити або відобразити більш докладну інформацію про науковців України запрошуємо заповнити "Анкету науковця"