donstuAdvanced Engineering Research (Rostov-on-Don)Advanced Engineering Research (Rostov-on-Don)2687-1653Don State Technical Universitydonstu-775Research ArticleTECHNICAL SCIENCESТЕХНИЧЕСКИЕ НАУКИEXCHANGE ALGORITHM OF BIEXTREMAL SOLUTION TO HOMOGENEOUS ALLOCATION PROBLEMПерестановочный алгоритм биэкстремального решения однородной распределительной задачиНейдорфРудольф АнатольевичNeydorfRudolph A.neyruan@yandex.ruФилипповАнтон ВладимировичFilippovAnton V.emilen2003@mail.ruЯгубовЗафар Хангусейн оглыYagubovZafar Khangusein-oglyzyagubov@yandex.ruДонской государственный технический университетРоссияDon State Technical UniversityRussian FederationУхтинский государственный технический университетРоссияUkhta State Technical UniversityRussian Federation201130122011115655666Copyright © Neydorf R.A., Filippov A.V., Yagubov Z.K., 20112011Нейдорф Р.А., Филиппов А.В., Ягубов З.Х.Neydorf R.A., Filippov A.V., Yagubov Z.K.This work is licensed under a Creative Commons Attribution 4.0 License.https://www.vestnik-donstu.ru/jour/article/view/775

An effective algorithm of constructing optimal solutions to homogeneous allocation problems is developed. It is called a biextremal solution algorithm because it permits to find the distribution carrying an extremum to two popular distribution evaluations simultaneously: uniformity of distribution criterion and minimax criterion. The principle of its operation consists in formalizing structure transformation of the core-image matrix derived by Romanovsky’s algorithm with further formalized rearrangement of tasks between their executors. An example of incremental solution to the particular problem is provided.

Разработан эффективный алгоритм построения оптимальных решений однородных распределительных задач, который назван алгоритмом биэкстремального решения, поскольку позволяет находить распределение, доставляющее экстремум одновременно двум популярным оценкам качества распределения: критерию равномерности распределения и минимаксному критерию. Изложена сущность его работы, заключающаяся в формализующей перестройке структуры загрузочной матрицы, полученной алгоритмом Романовского, с дальнейшей формализованной перестановкой заданий между их исполнителями. Приведен пример пошагового решения конкретной задачи.

алгоритмтеория расписанийраспределительная задачаоднородная системакритерий оптимизациибиэкстремальное решениеперестановочное правило.algorithmtheory of schedulingallocation problemhomogeneous systemoptimization criterionbiextremal solutionpermutable rule.ReferencesКонвей Р.В. Теория расписаний / Р.В. Конвей, В.Л. Максвелл, Л.В. Миллер. – М.: Наука, 1975. – 360 с.Konvej R.V. Teoriya raspisanij / R.V. Konvej, V.L. Maksvell, L.V. Miller. – M.: Nauka, 1975. – 360 s. – In Russian.Коффман Э.Г. Теория расписания и вычислительные машины / Э.Г. Коффман. – М.: Наука, 1987. – 334 с.Koffman E`.G. Teoriya raspisaniya i vy`chislitel`ny`e mashiny` / E`.G. Koffman. – M.: Nauka, 1987. – 334 s. – In Russian.Романовский И.В. Алгоритмы решения экстремальных задач / И.В. Романовский. – М.: Наука, 1977. – 352 с.Romanovskij I.V. Algoritmy` resheniya e`kstremal`ny`x zadach / I.V. Romanovskij. – M.: Nauka, 1977. – 352 s. – In Russian.Будиловский Д.М. Оптимизация решения задач теории расписаний на основе эволюционно-генетической модели распределения заданий: дис. … канд. техн. наук. – Ростов н/Д, 2007.Budilovskij D.M. Optimizaciya resheniya zadach teorii raspisanij na osnove e`volyucionno-geneticheskoj modeli raspredeleniya zadanij: dis. … kand. texn. nauk. – Rostov n/D, 2007. – In Russian.Филиппов А.В. Эквивалентно-селективный метод повышения эффективности работы распределительных алгоритмов / А.В. Филиппов, З.Х. Ягубов, Р.А. Нейдорф // «Инновация, экология и ресурсосберегающие технологии на предприятиях машиностроения, авиастроения, транспорта и сельского хозяйства»: Тр. IX междунар. науч.-техн. конф. – Ростов н/Д: Издательский центр ДГТУ, 2010. – С.366-373.Filippov A.V. E`kvivalentno-selektivny`j metod povy`sheniya e`ffektivnosti raboty` raspredelitel`ny`x algoritmov / A.V. Filippov, Z.X. Yagubov, R.A. Nejdorf // «Innovaciya, e`kologiya i resursosberegayushhie texnologii na predpriyatiyax mashinostroeniya, aviastroeniya, transporta i sel`skogo xozyajstva»: Tr. IX mezhdunar. nauch.-texn. konf. – Rostov n/D: Izdatel`skij centr DGTU, 2010. – S.366-373. – In Russian.Филиппов А.В. Ресурсно-точностной анализ алгоритма критического пути / А.В. Филиппов // Тр. 1-го Междунар. семинара студентов, аспирантов и ученых «Системный анализ, управление и обработка информации» / под общ. ред. Р.А. Нейдорфа. – Ростов н/Д: Издательский центр ДГТУ, 2010. – С.98-106.Filippov A.V. Resursno-tochnostnoj analiz algoritma kriticheskogo puti / A.V. Filippov // Tr. 1-go мezhdunar. seminara studentov, aspirantov i uchyony`x «Sistemny`j analiz, upravlenie i obrabotka informacii» / pod obshh. red. R.A. Nejdorfa. – Rostov n/D: Izdatel`skij centr DGTU, 2010. – S.98-106. – In Russian.Нейдорф Р.А. Селективно-минимизирующий метод повышения эффективности работы приближенных распределительных алгоритмов / Р.А. Нейдорф, А.В. Филиппов, З.Х. Ягубов // Тр. 1-го междунар. семинара студентов, аспирантов и ученых «Системный анализ, управление и обработка информации» / под общ. ред. Р.А. Нейдорфа. – Ростов н/Д: Издательский центр ДГТУ, 2010. – С.106-115.Nejdorf R.A. Selektivno-minimiziruyushhij metod povy`sheniya e`ffektivnosti raboty` priblizhyonny`x raspredelitel`ny`x algoritmov / R.A. Nejdorf, A.V. Filippov, Z.X. Yagubov // Tr. 1-go mezhdunar. seminara studentov, aspirantov i uchyony`x «Sistemny`j analiz, upravlenie i obrabotka informacii» / pod obshh. red. R.A. Nejdorfa. – Rostov n/D: Izdatel`skij centr DGTU, 2010. – S.106-115. – In Russian.Нейдорф Р.А. Методологические проблемы теории расписаний/ Р.А. Нейдорф, В.Г. Кобак // Системный анализ, управление и обработка информации: 1-й межвуз. сб. науч. ст. / ДГТУ; ТТИ ЮФУ. – Ростов н/Д, 2007. – С.101-108.Nejdorf R.A. Metodologicheskie problemy` teorii raspisanij / R.A. Nejdorf, V.G. Kobak // Sistemny`j analiz, upravlenie i obrabotka informacii: 1-j mezhvuz. sb. nauch. st. / DGTU; TTI YUFU. – Rostov n/D, 2007. – S.101-108. – In Russian.

The authors declare that there are no conflicts of interest present.