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.
scheduling theory, allocation problem, Romanovsky’s algorithm, decision tree, combination search, job size, combinations, permutations.
Введение. Масштабы современного производства, задачи координации действий больших технических, экономических и социальных систем усложнили функции организационного управления. Оно требует жёсткого планирования работ, процессов, действий во всех сферах человеческой деятельности. Эффективность планирования определяет технико-экономические показатели многочисленных бизнес-процессов. Поэтому всё больше внимания уделяется теории расписаний, суть которой можно сформулировать как решение проблемы упорядочивания задач, решаемых последовательно параллельно во времени.
Квинтэссенцией проблемы упорядочивания является задача построения оптимального расписания процесса выполнения конечного множества заданий выделенной для этого совокупностью исполнителей. Возникает задача построения такого алгоритма распределения заданий между исполнителями, который обеспечивает оптимум критерия оценки результирующего расписания. Указанная задача относится к классу NP-полных, является сложной как для теоретического, так и для экспериментального исследования [1–7].
С этим свойством распределительной задачи (РЗ) связана необходимость использования значительного временного ресурса, что затрудняет нахождение оптимального решения даже в простейших случаях работы с однородными РЗ (ОРЗ). Наиболее известный и эффективный в настоящее время подход к решению ОРЗ демонстрирует алгоритм, предложенный И. В. Романовским [8]. Однако и он требует доработки. Если речь идёт о задачах с размерностью по количеству исполнителей более 2 и по количеству заданий более 15 с некоторыми структурными особенностями совокупности распределяемых заданий, то время решения РЗ алгоритмом Романовского (АР) может значительно превысить разумные или технологические пределы. Таким образом, актуальна задача повышения ресурсно-временной эффективности данного алгоритма за счёт модификации, которая позволит повысить быстродействие, но не нарушит основного свойства нахождения абсолютного оптимума. Иными словами, модификация метода Романовского должна сохранить свойство метода ветвей и границ.
1. Jackson, J.-R. Scheduling a production line to minimize maximum tardiness. Research Report. Los Angeles University of California Management Sciences Research Project, 1955, no. 43, 72 p.
2. Bellman, R. Mathematical aspects of scheduling theory. Journal of the Society for Industrial and Applied Mathematics, 1956, vol. 4, pp. 168–205.
3. Koffman, E. G. Teoriya raspisaniya i vychislitelnyye mashiny. [Sheduling theory and computers.] Moscow : Nauka, 1984, 334 p. (in Russian).
4. Tanayev, V. S., Gordon, V. S., Shafranskiy, Y. M. Teoriya raspisaniy. Odnostadiynyye sistemy. [Sheduling theory. Single-stage systems.] Moscow : Nauka, 1984, 384 p. (in Russian).
5. Tanayev, V. S., Sotskov, Y. N., Strusevich, V. A. Teoriya raspisaniy. Mnogostadiynyye sistemy. [Sheduling theory. Multistage systems.] Moscow : Nauka, 1989, 328 p. (in Russian).
6. Blazewicz, J., et al. Scheduling Computer and Manufacturing Processes. New York : Springer, 2001, 485 p.
7. Lazarev, А. А., Gafarov, E. R. Teoriya raspisaniy. Zadachi i algoritmy. [Sheduling theory. Problems and algorithms.] Moscow: Lomonosov Moscow State University, 2011, 222 p. (in Russian).
8. Romanovskiy, I. V. Algoritmy resheniya ekstremalnykh zadach. [Algorithms for solving extremum problems.] Moscow : Nauka, 1977, 352 p. (in Russian).
9. Neydorf, R. А., Zhikulin, A. A. Povysheniye resursnoy effektivnosti algoritma tochnogo resheniya odnorodnoy raspredelitelnoy zadachi. Matematicheskiye metody v tekhnike i tekhnologiyakh — MMTT-27: sb. tr. XXVII Mezhdunar. nauch. konf. [Resource efficiency increase of the algorithm for homogeneous allocation problem exact solution. Mathematical methods in Engineering and Technology — MMTT-27: Proc. XXVII Int. Sci. Conf.] Tambov : TGTU, 2014, vol. 3, pp. 42–46 (in Russian).
10. Bocharov, P. P., Pechinkin, A. V. Teoriya veroyatnostey. Matematicheskaya statistika. [Probability calculus. Mathematical statistics.] Moscow : FIZMATLIT, 2005, 296 p. (in Russian).
11. Adler, Y. P., Markova, E. V., Grankovskiy, Y. V. Planirovaniye eksperimenta pri poiske optimalnykh usloviy. Planning an experiment under search for optimal conditions.] Moscow : Nauka, 1976, 278 p. (in Russian).
