Метод минимизации суммарного запаздывания работ на одиночном устройстве на основе рангового подхода и правил доминирования
Рассмотрен метод минимизации суммарного запаздывания работ на одиночном устройстве на основе определения кратчайшего гамильтонового пути в произвольном полносвязном графе с использованием рангового подхода и правил доминирования. Предложены метрики оценивания улучшения результатов работы алгоритма п...
Saved in:
| Published in: | Электронное моделирование |
|---|---|
| Date: | 2014 |
| Main Authors: | , |
| Format: | Article |
| Language: | Russian |
| Published: |
Інститут проблем моделювання в енергетиці ім. Г.Є. Пухова НАН України
2014
|
| Subjects: | |
| Online Access: | https://nasplib.isofts.kiev.ua/handle/123456789/100993 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| Journal Title: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Cite this: | Метод минимизации суммарного запаздывания работ на одиночном устройстве на основе рангового подхода и правил доминирования / С.В. Минухин, Д.С. Ленько // Электронное моделирование. — 2014 — Т. 36, № 2. — С. 57-79. — Бібліогр.: 35 назв. — рос. |
Institution
Digital Library of Periodicals of National Academy of Sciences of Ukraine| _version_ | 1862716566922067968 |
|---|---|
| author | Минухин, С.В. Ленько, Д.С. |
| author_facet | Минухин, С.В. Ленько, Д.С. |
| citation_txt | Метод минимизации суммарного запаздывания работ на одиночном устройстве на основе рангового подхода и правил доминирования / С.В. Минухин, Д.С. Ленько // Электронное моделирование. — 2014 — Т. 36, № 2. — С. 57-79. — Бібліогр.: 35 назв. — рос. |
| collection | DSpace DC |
| container_title | Электронное моделирование |
| description | Рассмотрен метод минимизации суммарного запаздывания работ на одиночном устройстве на основе определения кратчайшего гамильтонового пути в произвольном полносвязном графе с использованием рангового подхода и правил доминирования. Предложены метрики оценивания улучшения результатов работы алгоритма при использовании правил доминирования—относительного уменьшения суммарного запаздывания и числа получаемых локально-оптимальных решений. Приведены результаты вычислительных экспериментов для взвешенного и невзвешенного случаев запаздывания работ с произвольными директивными сроками. Найдены условия, при которых используемый алгоритм позволяет улучшить расписания работ и определить наиболее эффективные правила доминирования.
Розглянуто метод мінімізації сумарного запізнювання робіт на одиночному пристрої на основі визначення найкоротшого гамільтонового шляху в довільному повнозв’язному графі з використанням рангового підходу і правил домінування. Запропоновано метрики оцінювання поліпшення результатів роботи алгоритму при використанні правил домінування — відносного зменшення сумарного запізнювання і кількості одержуваних локально-оптимальних рішень. Наведено результати обчислювальних експериментів для зваженого і незваженого запізнювання робіт з довільними директивними термінами. Визначено умови, при яких досліджуваний алгоритм дозволяє покращити розклад робіт, і знайдено найбільш ефективні правила домінування.
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.
|
| first_indexed | 2025-12-07T18:06:08Z |
| format | Article |
| fulltext | |
| id | nasplib_isofts_kiev_ua-123456789-100993 |
| institution | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| issn | 0204-3572 |
| language | Russian |
| last_indexed | 2025-12-07T18:06:08Z |
| publishDate | 2014 |
| publisher | Інститут проблем моделювання в енергетиці ім. Г.Є. Пухова НАН України |
| record_format | dspace |
| spelling | Минухин, С.В. Ленько, Д.С. 2016-05-28T18:10:08Z 2016-05-28T18:10:08Z 2014 Метод минимизации суммарного запаздывания работ на одиночном устройстве на основе рангового подхода и правил доминирования / С.В. Минухин, Д.С. Ленько // Электронное моделирование. — 2014 — Т. 36, № 2. — С. 57-79. — Бібліогр.: 35 назв. — рос. 0204-3572 https://nasplib.isofts.kiev.ua/handle/123456789/100993 621.398 Рассмотрен метод минимизации суммарного запаздывания работ на одиночном устройстве на основе определения кратчайшего гамильтонового пути в произвольном полносвязном графе с использованием рангового подхода и правил доминирования. Предложены метрики оценивания улучшения результатов работы алгоритма при использовании правил доминирования—относительного уменьшения суммарного запаздывания и числа получаемых локально-оптимальных решений. Приведены результаты вычислительных экспериментов для взвешенного и невзвешенного случаев запаздывания работ с произвольными директивными сроками. Найдены условия, при которых используемый алгоритм позволяет улучшить расписания работ и определить наиболее эффективные правила доминирования. Розглянуто метод мінімізації сумарного запізнювання робіт на одиночному пристрої на основі визначення найкоротшого гамільтонового шляху в довільному повнозв’язному графі з використанням рангового підходу і правил домінування. Запропоновано метрики оцінювання поліпшення результатів роботи алгоритму при використанні правил домінування — відносного зменшення сумарного запізнювання і кількості одержуваних локально-оптимальних рішень. Наведено результати обчислювальних експериментів для зваженого і незваженого запізнювання робіт з довільними директивними термінами. Визначено умови, при яких досліджуваний алгоритм дозволяє покращити розклад робіт, і знайдено найбільш ефективні правила домінування. 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. ru Інститут проблем моделювання в енергетиці ім. Г.Є. Пухова НАН України Электронное моделирование Вычислительные процессы и системы Метод минимизации суммарного запаздывания работ на одиночном устройстве на основе рангового подхода и правил доминирования Article published earlier |
| spellingShingle | Метод минимизации суммарного запаздывания работ на одиночном устройстве на основе рангового подхода и правил доминирования Минухин, С.В. Ленько, Д.С. Вычислительные процессы и системы |
| title | Метод минимизации суммарного запаздывания работ на одиночном устройстве на основе рангового подхода и правил доминирования |
| title_full | Метод минимизации суммарного запаздывания работ на одиночном устройстве на основе рангового подхода и правил доминирования |
| title_fullStr | Метод минимизации суммарного запаздывания работ на одиночном устройстве на основе рангового подхода и правил доминирования |
| title_full_unstemmed | Метод минимизации суммарного запаздывания работ на одиночном устройстве на основе рангового подхода и правил доминирования |
| title_short | Метод минимизации суммарного запаздывания работ на одиночном устройстве на основе рангового подхода и правил доминирования |
| title_sort | метод минимизации суммарного запаздывания работ на одиночном устройстве на основе рангового подхода и правил доминирования |
| topic | Вычислительные процессы и системы |
| topic_facet | Вычислительные процессы и системы |
| url | https://nasplib.isofts.kiev.ua/handle/123456789/100993 |
| work_keys_str_mv | AT minuhinsv metodminimizaciisummarnogozapazdyvaniârabotnaodinočnomustroistvenaosnoverangovogopodhodaipravildominirovaniâ AT lenʹkods metodminimizaciisummarnogozapazdyvaniârabotnaodinočnomustroistvenaosnoverangovogopodhodaipravildominirovaniâ |