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

Abstract

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

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

The paper deals with the algorithms of minimizing the total lag of works on a single device on the basis of determining the shortest Hamilton path in the arbitrary graph using the rank approach and the dominance rules. The performance metrics of applying the dominance rules based on the evaluation of locally optimal solutions, obtained on different ranks and the values of relative reduction of total lag in relation to the basic algorithm are proposed. The results of computational experiments for the weighted and unweighted cases for the works with different duration and the types of due dates defined in the research are given. The conditions, under which, the proposed algorithms allow improving the schedule of works are defined and the most effective dominance rules are determined.