Метод минимизации суммарного запаздывания работ на одиночном устройстве на основе рангового подхода и правил доминирования
Рассмотрен метод минимизации суммарного запаздывания работ на одиночном устройстве на основе определения кратчайшего гамильтонового пути в произвольном полносвязном графе с использованием рангового подхода и правил доминирования. Предложены метрики оценивания улучшения результатов работы алгоритма п...
Збережено в:
| Дата: | 2014 |
|---|---|
| Автори: | , |
| Формат: | Стаття |
| Мова: | Russian |
| Опубліковано: |
Інститут проблем моделювання в енергетиці ім. Г.Є. Пухова НАН України
2014
|
| Назва видання: | Электронное моделирование |
| Теми: | |
| Онлайн доступ: | http://dspace.nbuv.gov.ua/handle/123456789/100993 |
| Теги: |
Додати тег
Немає тегів, Будьте першим, хто поставить тег для цього запису!
|
| Назва журналу: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Цитувати: | Метод минимизации суммарного запаздывания работ на одиночном устройстве на основе рангового подхода и правил доминирования / С.В. Минухин, Д.С. Ленько // Электронное моделирование. — 2014 — Т. 36, № 2. — С. 57-79. — Бібліогр.: 35 назв. — рос. |
Репозитарії
Digital Library of Periodicals of National Academy of Sciences of Ukraine| id |
irk-123456789-100993 |
|---|---|
| record_format |
dspace |
| spelling |
irk-123456789-1009932016-05-29T03:03:27Z Метод минимизации суммарного запаздывания работ на одиночном устройстве на основе рангового подхода и правил доминирования Минухин, С.В. Ленько, Д.С. Вычислительные процессы и системы Рассмотрен метод минимизации суммарного запаздывания работ на одиночном устройстве на основе определения кратчайшего гамильтонового пути в произвольном полносвязном графе с использованием рангового подхода и правил доминирования. Предложены метрики оценивания улучшения результатов работы алгоритма при использовании правил доминирования—относительного уменьшения суммарного запаздывания и числа получаемых локально-оптимальных решений. Приведены результаты вычислительных экспериментов для взвешенного и невзвешенного случаев запаздывания работ с произвольными директивными сроками. Найдены условия, при которых используемый алгоритм позволяет улучшить расписания работ и определить наиболее эффективные правила доминирования. Розглянуто метод мінімізації сумарного запізнювання робіт на одиночному пристрої на основі визначення найкоротшого гамільтонового шляху в довільному повнозв’язному графі з використанням рангового підходу і правил домінування. Запропоновано метрики оцінювання поліпшення результатів роботи алгоритму при використанні правил домінування — відносного зменшення сумарного запізнювання і кількості одержуваних локально-оптимальних рішень. Наведено результати обчислювальних експериментів для зваженого і незваженого запізнювання робіт з довільними директивними термінами. Визначено умови, при яких досліджуваний алгоритм дозволяє покращити розклад робіт, і знайдено найбільш ефективні правила домінування. 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. 2014 Article Метод минимизации суммарного запаздывания работ на одиночном устройстве на основе рангового подхода и правил доминирования / С.В. Минухин, Д.С. Ленько // Электронное моделирование. — 2014 — Т. 36, № 2. — С. 57-79. — Бібліогр.: 35 назв. — рос. 0204-3572 http://dspace.nbuv.gov.ua/handle/123456789/100993 621.398 ru Электронное моделирование Інститут проблем моделювання в енергетиці ім. Г.Є. Пухова НАН України |
| institution |
Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| collection |
DSpace DC |
| language |
Russian |
| topic |
Вычислительные процессы и системы Вычислительные процессы и системы |
| spellingShingle |
Вычислительные процессы и системы Вычислительные процессы и системы Минухин, С.В. Ленько, Д.С. Метод минимизации суммарного запаздывания работ на одиночном устройстве на основе рангового подхода и правил доминирования Электронное моделирование |
| description |
Рассмотрен метод минимизации суммарного запаздывания работ на одиночном устройстве на основе определения кратчайшего гамильтонового пути в произвольном полносвязном графе с использованием рангового подхода и правил доминирования. Предложены метрики оценивания улучшения результатов работы алгоритма при использовании правил доминирования—относительного уменьшения суммарного запаздывания и числа получаемых локально-оптимальных решений. Приведены результаты вычислительных экспериментов для взвешенного и невзвешенного случаев запаздывания работ с произвольными директивными сроками. Найдены условия, при которых используемый алгоритм позволяет улучшить расписания работ и определить наиболее эффективные правила доминирования. |
| format |
Article |
| author |
Минухин, С.В. Ленько, Д.С. |
| author_facet |
Минухин, С.В. Ленько, Д.С. |
| author_sort |
Минухин, С.В. |
| title |
Метод минимизации суммарного запаздывания работ на одиночном устройстве на основе рангового подхода и правил доминирования |
| title_short |
Метод минимизации суммарного запаздывания работ на одиночном устройстве на основе рангового подхода и правил доминирования |
| title_full |
Метод минимизации суммарного запаздывания работ на одиночном устройстве на основе рангового подхода и правил доминирования |
| title_fullStr |
Метод минимизации суммарного запаздывания работ на одиночном устройстве на основе рангового подхода и правил доминирования |
| title_full_unstemmed |
Метод минимизации суммарного запаздывания работ на одиночном устройстве на основе рангового подхода и правил доминирования |
| title_sort |
метод минимизации суммарного запаздывания работ на одиночном устройстве на основе рангового подхода и правил доминирования |
| publisher |
Інститут проблем моделювання в енергетиці ім. Г.Є. Пухова НАН України |
| publishDate |
2014 |
| topic_facet |
Вычислительные процессы и системы |
| url |
http://dspace.nbuv.gov.ua/handle/123456789/100993 |
| citation_txt |
Метод минимизации суммарного запаздывания работ на одиночном устройстве на основе рангового подхода и правил доминирования / С.В. Минухин, Д.С. Ленько // Электронное моделирование. — 2014 — Т. 36, № 2. — С. 57-79. — Бібліогр.: 35 назв. — рос. |
| series |
Электронное моделирование |
| work_keys_str_mv |
AT minuhinsv metodminimizaciisummarnogozapazdyvaniârabotnaodinočnomustrojstvenaosnoverangovogopodhodaipravildominirovaniâ AT lenʹkods metodminimizaciisummarnogozapazdyvaniârabotnaodinočnomustrojstvenaosnoverangovogopodhodaipravildominirovaniâ |
| first_indexed |
2024-03-30T08:52:31Z |
| last_indexed |
2024-03-30T08:52:31Z |
| _version_ |
1796148726575661056 |