SPEEDING ALGORITHM FOR MINIMAX OPTIMIZATION OF ALLOCATION PROBLEM SOLUTIONS IN HOMOGENEOUS SYSTEMS
Abstract
The optimization algorithm for solving homogeneous allocation problems of the scheduling theory is described and proved. It is a modification of Romanovsky’s algorithm known in this problem domain. Romanovsky’s algorithm is a classical version of the branch-and-bound method with one-way traversing a decision tree. A systematic study of this algorithm that allows revealing reasons for its operate time increment when traversing some decision tree branches is carried out. It allows proposing modification free of the revealed shortcoming. It is called a combinatorial-modified Romanovsky's algorithm. The essence of this modification is as follows. In the process of solving the allocation problem, those rules, stages, and steps that lead to the sorting on executors the sets of tasks deliberately duplicating the previous effects are selectively skipped. The essence of the new algorithm is illustrated by an example. The statistically presented studies are resulted. They demonstrate the algorithm capabilities on the high dimensional allocation problems. (Such problems cannot be solved by the classical algorithm due to the limited timing budgets.) The results of processing these solutions have shown that the new modification does not solve the problem of NP-complete allocation tasks, but it provides a resource-time gain associated with the significant reduction in the exponential model index of the average solution time.
Keywords
About the Authors
Rudolf Anatolyevich NeydorfRussian Federation
Artem Alexandrovich Zhikulin
Russian Federation
References
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 с.
Review
For citations:
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