Описывается и обосновывается алгоритм оптимизации решения однородных распределительных задач теории расписаний. Он представляет собой модификацию известного в этой предметной области алгоритма Романовского — классического варианта метода ветвей и границ с односторонним обходом дерева решений. Проведено системное исследование этого алгоритма, которое позволило выявить причины увеличения времени его работы при обходе некоторых ветвей дерева решений. Это даёт возможность предложить свободную от выявленного недостатка модификацию, названную комбинационно-модифицированным алгоритмом Романовского. Сущность данной модификации заключается в следующем. В процедуре решения распределительной задачи избирательно пропускаются те правила, этапы и шаги, которые приводят к перебору на исполнителях наборов заданий, заведомо повторяющих проверенный ранее результат. Сущность нового алгоритма поясняется примером. Приводятся результаты статистически представительных исследований. Они позволили продемонстрировать возможности алгоритма на распределительных задачах высокой размерности. (Решение таких задач классическим алгоритмом невозможно из-за ограниченных временных ресурсов.) Результаты обработки этих решений показали, что новая модификация не позволяет решить проблему NP-полноты распределительных задач, но обеспечивает ресурсно-временной выигрыш, связанный с существенным снижением показателя степени экспоненциальной модели роста среднего времени решения.
теория расписаний, распределительная задача, алгоритм Романовского, дерево решений, перебор комбинаций, размер задания, сочетания, перестановки.
Введение. Масштабы современного производства, задачи координации действий больших технических, экономических и социальных систем усложнили функции организационного управления. Оно требует жёсткого планирования работ, процессов, действий во всех сферах человеческой деятельности. Эффективность планирования определяет технико-экономические показатели многочисленных бизнес-процессов. Поэтому всё больше внимания уделяется теории расписаний, суть которой можно сформулировать как решение проблемы упорядочивания задач, решаемых последовательно параллельно во времени.
Квинтэссенцией проблемы упорядочивания является задача построения оптимального расписания процесса выполнения конечного множества заданий выделенной для этого совокупностью исполнителей. Возникает задача построения такого алгоритма распределения заданий между исполнителями, который обеспечивает оптимум критерия оценки результирующего расписания. Указанная задача относится к классу NP-полных, является сложной как для теоретического, так и для экспериментального исследования [1–7].
С этим свойством распределительной задачи (РЗ) связана необходимость использования значительного временного ресурса, что затрудняет нахождение оптимального решения даже в простейших случаях работы с однородными РЗ (ОРЗ). Наиболее известный и эффективный в настоящее время подход к решению ОРЗ демонстрирует алгоритм, предложенный И. В. Романовским [8]. Однако и он требует доработки. Если речь идёт о задачах с размерностью по количеству исполнителей более 2 и по количеству заданий более 15 с некоторыми структурными особенностями совокупности распределяемых заданий, то время решения РЗ алгоритмом Романовского (АР) может значительно превысить разумные или технологические пределы. Таким образом, актуальна задача повышения ресурсно-временной эффективности данного алгоритма за счёт модификации, которая позволит повысить быстродействие, но не нарушит основного свойства нахождения абсолютного оптимума. Иными словами, модификация метода Романовского должна сохранить свойство метода ветвей и границ.
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 с.
