Preview

Вестник Донского государственного технического университета

Расширенный поиск

Алгоритм повышения быстродействия минимаксной оптимизации решений распределительных задач в однородных системах

https://doi.org/10.12737/5710

Полный текст:

Аннотация

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

 

Об авторах

Рудольф Анатольевич Нейдорф
Донской государственный технический университет, Россия
Россия


Артём Александрович Жикулин
Донской государственный технический университет, Россия
Россия


Список литературы

1. Jackson, J.-R. Scheduling a production line to minimize maximum tardiness / J.-R. Jackson // Research Report. Los Angeles University of California Management Sciences Research Project. — 1955. — № 43. — 72 p.

2. Bellman, R. Mathematical aspects of scheduling theory / R. Bellman // Journal of the Society for Industrial and Applied Mathematics. — 1956. — Vol. 4. — Pp. 168–205.

3. Коффман, Э. Г. Теория расписания и вычислительные машины / Э. Г. Коффман. — Москва : Наука, 1984. — 334 с.

4. Танаев, В. С. Теория расписаний. Одностадийные системы / В. С. Танаев, В. С. Гордон, Я. М. Шафранский. — Москва : Наука, 1984. — 384 с.

5. Танаев, В. С. Теория расписаний. Многостадийные системы / В. С. Танаев, Ю. Н. Сотсков, В. А. Струсевич. — Москва : Наука, 1989. — 328 с.

6. Scheduling Computer and Manufacturing Processes / J. Blazewicz [et al.]. — New York : Springer, 2001. — 485 p.

7. Лазарев, А. А. Теория расписаний. Задачи и алгоритмы / А. А. Лазарев, Е. Р. Гафаров. — Москва : Моск. гос. ун-т им. М. В. Ломоносова, 2011. — 222 с.

8. Романовский, И. В. Алгоритмы решения экстремальных задач / И. В. Романовский. — Москва : Наука, 1977. — 352 с.

9. Нейдорф, Р. А. Повышение ресурсной эффективности алгоритма точного решения одно-родной распределительной задачи / Р. А. Нейдорф, А. А. Жикулин // Математические методы в тех-нике и технологиях — ММТТ-27 : сб. тр. XXVII Междунар. науч. конф. — Тамбов : Тамб. гос. техн. ун-т , 2014. — Т. 3. — С. 42–46.

10. Бочаров, П. П. Теория вероятностей. Математическая статистика / П. П. Бочаров, А. В. Печинкин. — Москва : ФИЗМАТЛИТ, 2005. — 296 с.

11. Адлер, Ю. П. Планирование эксперимента при поиске оптимальных условий / Ю. П. Адлер, Е. В. Маркова, Ю. В. Гранковский. — Москва : Наука, 1976. — 278 с.


Для цитирования:


Нейдорф Р.А., Жикулин А.А. Алгоритм повышения быстродействия минимаксной оптимизации решений распределительных задач в однородных системах. Вестник Донского государственного технического университета. 2014;14(3):64-76. https://doi.org/10.12737/5710

For citation:


Neydorf R.A., Zhikulin A.A. SPEEDING ALGORITHM FOR MINIMAX OPTIMIZATION OF ALLOCATION PROBLEM SOLUTIONS IN HOMOGENEOUS SYSTEMS. Vestnik of Don State Technical University. 2014;14(3):64-76. (In Russ.) https://doi.org/10.12737/5710

Просмотров: 65


Creative Commons License
Контент доступен под лицензией Creative Commons Attribution 4.0 License.


ISSN 1992-5980 (Print)
ISSN 1992-6006 (Online)