SPEEDING ALGORITHM FOR MINIMAX OPTIMIZATION OF ALLOCATION PROBLEM SOLUTIONS IN HOMOGENEOUS SYSTEMS
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...
| Main Authors: | , |
|---|---|
| Format: | Article |
| Language: | Russian |
| Published: |
Don State Technical University
2014-09-01
|
| Series: | Advanced Engineering Research |
| Subjects: | |
| Online Access: | https://www.vestnik-donstu.ru/jour/article/view/332 |
| _version_ | 1797881344638844928 |
|---|---|
| author | Rudolf Anatolyevich Neydorf Artem Alexandrovich Zhikulin |
| author_facet | Rudolf Anatolyevich Neydorf Artem Alexandrovich Zhikulin |
| author_sort | Rudolf Anatolyevich Neydorf |
| collection | DOAJ |
| description | 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. |
| first_indexed | 2024-04-10T03:18:42Z |
| format | Article |
| id | doaj.art-27a63599a25244a78e5f0bd656bc8aca |
| institution | Directory Open Access Journal |
| issn | 2687-1653 |
| language | Russian |
| last_indexed | 2024-04-10T03:18:42Z |
| publishDate | 2014-09-01 |
| publisher | Don State Technical University |
| record_format | Article |
| series | Advanced Engineering Research |
| spelling | doaj.art-27a63599a25244a78e5f0bd656bc8aca2023-03-13T07:31:25ZrusDon State Technical UniversityAdvanced Engineering Research2687-16532014-09-01143647610.12737/5710325SPEEDING ALGORITHM FOR MINIMAX OPTIMIZATION OF ALLOCATION PROBLEM SOLUTIONS IN HOMOGENEOUS SYSTEMSRudolf Anatolyevich Neydorf0Artem Alexandrovich Zhikulin1Донской государственный технический университет, РоссияДонской государственный технический университет, Россия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.https://www.vestnik-donstu.ru/jour/article/view/332теория расписанийраспределительная задачаалгоритм романовскогодерево решенийперебор комбинацийразмер заданиясочетанияперестановки. |
| spellingShingle | Rudolf Anatolyevich Neydorf Artem Alexandrovich Zhikulin SPEEDING ALGORITHM FOR MINIMAX OPTIMIZATION OF ALLOCATION PROBLEM SOLUTIONS IN HOMOGENEOUS SYSTEMS Advanced Engineering Research теория расписаний распределительная задача алгоритм романовского дерево решений перебор комбинаций размер задания сочетания перестановки. |
| title | SPEEDING ALGORITHM FOR MINIMAX OPTIMIZATION OF ALLOCATION PROBLEM SOLUTIONS IN HOMOGENEOUS SYSTEMS |
| title_full | SPEEDING ALGORITHM FOR MINIMAX OPTIMIZATION OF ALLOCATION PROBLEM SOLUTIONS IN HOMOGENEOUS SYSTEMS |
| title_fullStr | SPEEDING ALGORITHM FOR MINIMAX OPTIMIZATION OF ALLOCATION PROBLEM SOLUTIONS IN HOMOGENEOUS SYSTEMS |
| title_full_unstemmed | SPEEDING ALGORITHM FOR MINIMAX OPTIMIZATION OF ALLOCATION PROBLEM SOLUTIONS IN HOMOGENEOUS SYSTEMS |
| title_short | SPEEDING ALGORITHM FOR MINIMAX OPTIMIZATION OF ALLOCATION PROBLEM SOLUTIONS IN HOMOGENEOUS SYSTEMS |
| title_sort | speeding algorithm for minimax optimization of allocation problem solutions in homogeneous systems |
| topic | теория расписаний распределительная задача алгоритм романовского дерево решений перебор комбинаций размер задания сочетания перестановки. |
| url | https://www.vestnik-donstu.ru/jour/article/view/332 |
| work_keys_str_mv | AT rudolfanatolyevichneydorf speedingalgorithmforminimaxoptimizationofallocationproblemsolutionsinhomogeneoussystems AT artemalexandrovichzhikulin speedingalgorithmforminimaxoptimizationofallocationproblemsolutionsinhomogeneoussystems |