Вісник № 01. Системний аналіз, управління та інформаційні технології

Постійне посилання колекціїhttps://repository.kpi.kharkov.ua/handle/KhPI-Press/42344

Переглянути

Результати пошуку

Зараз показуємо 1 - 10 з 12

Total weighted tardiness minimization for tasks with a common due date on parallel machines in case of agreeable weights and processing times
(НТУ "ХПІ", 2019) Pavlov, Alexander Anatolievich; Misura, Elena Borisovna; Melnikov, Oleg Valentinovich
We consider n tasks scheduling problem on m identical parallel machines by the criterion of minimizing the total weighted tardiness of tasks. All tasks arrive for processing at the same time. Weights and processing times are agreeable, that is, a greater weight of a task corre sponds to a shorter processing time. In addition, we have arbitrary start times of machines for tasks processing. The times may be less or greater than the due date or to coincide with it. The problem in this formulation is addressed for the first time. It can be used to provide planning and decision making in systems with a network representation of technological processes and limited resources. We give efficient PSC-algorithm with 𝑂(𝑚𝑛 log 𝑛) complexity that includes the polynomial component and the approximation algorithm based on permutations of tasks. The polynomial component contains sufficient signs of optimality of the obtained solutions and allows to obtain an exact solution by polynomial subalgorithm. In the case when the sufficient signs of optimality do not fulfill, we obtain approximate solution with an estimate of deviation from the optimum for each individual problem instance of any practical dimension. We show that a schedule obtained as a result of the problem solving can be split into two schedules: the schedule on machines which start time is less than or equal to the due date, and the schedule on machines which start after the due date. Optimization is only done in the first schedule. The second schedule is optimal by construction. Statistical studies of the PSC-algorithm showed its high efficiency. We solved problems with dimensions up to 40,000 tasks and up to 30 machines. The average time to solve the problem by the algorithm using the most efficient types of permutations was 27.3 ms for this dimension. The average frequency of an optimal solution obtaining amounted to 90.3 %. The average deviation from an optimum was no more than 0.000251.
Synthesis of local area network structure in uncertain conditions of initial information
(НТУ "ХПІ", 2019) Mishchenko, Oryna Oleksiivna; Volovshchykov, Valeriy Yuriyovich; Shapo, Vladlen Felixovitch; Grinchenko, Marina Anatoliyvna
The problem of taking into account the uncertainty of the initial information is identified in the tasks of the structure synthesis of local area networks. The analysis of the factors generating uncertainty is carried out, the sources of uncertainty are singled out and the approac hes to formalization and research of uncertainty are systematized. Probabilistic-statistical, interval, fuzzy and deterministic approaches were reviewed, as well as statistical, subjective, logical interpretations of probability and stochastic description, concept of interval-probabilistic approach, continuously determined and discretely determined models. The formulation of the problem was formed and it was proposed to apply the theory of fuzzy sets to formalize and study an uncertainty in synthesizing the structure of the local computing network, the main elements of which are user points, the centers of processing of the information, switching devices and communication channels. The implementation of information and computing works which sources are subs criber points, is assigned to the centers of information processing. It is assumed the popularity of volumes of information and computing works and geographical coordinates of the location of network elements. A model for a research problem based on a cost criterion has been developed. Cost parameters are divided into well-defined and having an uncertain nature. Fuzzyparameters are proposed to describe the membership functions of the form "approximately equal" or "is approximately in the interval". Restrictions on technical capabilities of information processing centers, switching devices, traffic in communication channels are singled out. The technology of model research based on the idea of solving the problems of linear programming in fuzzy statement is proposed. The technology provides the decision maker with information about the network structure, its cost and the level of ownership of the solution. The results of the work can be used in the analysis of approaches to solving problems of structural-topological synthesis of local area networks, design, development and implementation of appropriate software solutions.
Поліпшений метод дослідження стійкості розв'язування систем лінійних алгебраїчних рівнянь
(НТУ "ХПІ", 2019) Марченко, Наталя Андріївна; Руденко, Роман Олександрович
Проведений огляд існуючих методів дослідження стійкості розв’язків систем лінійних алгебраїчних рівнянь (СЛАР), що залежать від вхідних даних, тобто варіацій параметрів. Розглянуто методи оцінки стійкості розв'язування систем лінійних алгебраїчних рівнянь, такі як числа зумовленості, модульні визначники та побудова таблиці знаків за оригінальним та поліпшеним методом побудови. Реалізоване програмне забезпечення для оцінки стійкості систем лінійних алгебраїчних рівнянь за допомогою чисел обумовленості, модульних визначників та побудови таблиці знаків для знаходження точних оцінок варіацій розв'язків залежних від варіацій параметрів СЛАР. В роботі показано, що дослідження стійкості за числами обумовленості дають дуже грубу оцінку можливих похибок розв'язків, але вони є простими в реалізації, та для СЛАР можуть одразу показати, що деякі системи є погано зумовленими, що значно економить час дослідження, особливо якщо СЛАР мають дуже велику розмірність. Дослідження стійкості за модульними визначниками потребують великих розрахунків, але дають досить надійну оцінку зверху щодо можливих варіацій окремих компонент розв'язків систем лінійних алгебраїчних рівнянь. Це є дуже важливою особливістю метода тому, що окремі компоненти розв'язку можуть зазнавати значних варіацій, що не враховуються при дослідженні за числами обумовленості. Дослідження стійкості побудовою таблиці знаків надають можливість знайти максимальні варіації окремих компонент розв'язків системи лінійних алгебраїчних рівнянь, що насправді можуть бути значно меншими, ніж верхня оцінка можливих варіацій за методом модульних визначників. В роботі запропоновано поліпшений метод побудови таблиці знаків, що знаходить більш точний діапазон можливих варіацій розв'язків системи лінійних алгебраїчних рівнянь. Був проведений порівняльний аналіз між традиційним методом побудови таблиці знаків за окремими визначниками та поліпшеним методом побудови таблиці знаків за похідними від ділення визначників за формулою Крамера. Згідно аналізу, поліпшений метод у 30% випадків знаходить варіації, що в 1.3 рази більші ніж варіації, що знаходить попередній метод, та у 5% випадків ці варіації перевищують попередні у 2 або більше разів. Це говорить про те, що традиційний метод у деяких випадках недооцінював можливі відхилення розв'язків, що залежать від варіацій вхідних даних
Problems of elicitation and analysis of requirements to the program module of monitoring on the basis of the conditions of cognitive analysis
(НТУ "ХПІ", 2019) Kozulia, Tatyana Vladimirovna; Sviridova, Alyona Sergeevna; Kozulia, Maria Mikhailovna
There are risks of obtaining result that does not answer a work purpose statement when developing the software product for new subject area. It is necessary to pay attention on requirements to the software for elimination of such risks. This article is considering questions about collection and analysis requirements to a program module of sea water areas environmental monitoring. Program system "НДС Эколог" for ensuring continuous observation of sea water areas condition is noted by complex structure, high labor intensity of processing, storage and manipulations of data due to their significant amount. The software of this system makes a large-scale program complex for monitoring researches automation. However, according to the preliminary analysis of functionality "НДС Эколог" on quality control of dolphins living environment is not sufficient and need additional module development. Thus, the further development of this monitoring system is associated with the problem of elicitation and analyzing the requirements for the program module for calculating the coastal zones water resources quality. Elicitation requirements to additional program module is carried out on the basis of the standard documentation analysis, business processes of monitoring researches according to program engineering provisions. Identified Requirements are need check on integrity and lack of contradictions in their pithiness for further documenting according to the internatio nal recommendations standard about development of requirements specifications to the software IEEE STD 830 1993. To solve the problems of information support and software for integrated monitoring, a matrix of requirements was formed and cognitive modeling was applied. The requirements dependency matrix represents a simple and effective method of contradictions and overlappings identification, in case of simple systems consideration. Cognitive modeling promotes better understanding a problem situation, identification of contradictions and qualitative system analysis. The purpose of modeling consists in formation and specification of a studied object functioning hypothesis which consists of separate subsystems and elements. In this case, the system of requirements should reflect the causal relationships of object elements under study.
Застосування методів згладжування для прогнозування обсягу виробництва
(НТУ "ХПІ", 2019) Хом'як, Тетяна Валеріївна; Малієнко, Андрій Вікторович; Симонець, Галина Василівна
Об'єктом дослідження є підприємство ТОВ ТПК "Терра" – провідний вітчизняний виробник високоякісних захисних покриттів промислового призначення для антикорозійного захисту металоконструкцій і залізобетонних конструкцій. Наразі на підприємстві відкриті питання планування майбутніх замовлень, доцільного використання потужностей і розширення виробничих можливостей. В роботі проведено системний аналіз цього підприємства шляхом розробки функціональної моделі процесів та її декомпозиції з розкладанням до другого рівня деталізації. В результаті отримано задачу з прогнозування обсягу випуску антикорозійних покриттів, які запобігають руйнації металевих конструкції та механізмів. Ця задача є актуальною як для самого підприємства, так і для задоволення попиту на ринку збуту. Найбільш ефективними математичними моделями, за допомогою яких можна прогнозувати розвиток процесів виробництва – це моделі на основі часових рядів. Одними з найпоширеніших методів прогнозування показників таких рядів є методи згладжування, які використовуються для зменшення впливу випадкових коливань. Поставлену задачу вирішено методами експоненціального та адаптивного згладжування. Для перевірки адекватності отриманих моделей застосовано критерій серій (визначення випадковості відхилень від тренду), критерій піків (перевірка рівності нулю математичного сподівання), R/S-критерій (визначення відповідності розподілу залишкової компоненти нормальному закону), критерій Дарбіна-Уотсона (визначення незалежності значень залишкової компоненти). Проведено аналіз кожної отриманої моделі прогнозування, а також оцінено якість прогнозів. Зроблено висновки щодо подальшого виготовлення продукції на основі прогнозованих значень. Запропонована модель має практичну спрямованість і може використовуватися у задачах, пов'язаних з прогнозуванням в умовах виробничих підприємств.
An information technology for the support for solving the analysis problem of the customers’ value within the enterprise CRM-strategy implementation
(НТУ "ХПІ", 2019) Orlovskyi, D. L.; Kopp, A. M.; Pyvovarova, A. A.
This study considers a CRM-approach and methods for analyzing customer base. Mathematical and algorithmic support was developed for the analysis of customer value in a trading enterprise. Algorithmic support is presented using the IDEF0 notation. A software solution was developed to assess customer value in a commercial enterprise. A fragment of the data model for the software solution was developed using the IDEF1x notation. The parameters for estimating the value of customers in a commercial enterprise were calculated using the processed data obtained by applying the developed software solution. The developed software solution allows to segment the customer base according to different criteria and provide marketing recommendations to each groups of customers. Therefore, customers were divided into groups according to the calculated parameters. As a result of the analysis, each group of clients receives a marketing recommendations. After the application of recommendations an increase in the purchasing power of clients, belonging to the group to which the marketing recommendation has been provided, is expected. Another used method for analyzing the customer base in the developed software solution is the sales funnel, which displays the effectiveness of the marketing unit at each of the sales stages, thereby allowing to identify weak points in the sales department. Thus, unlike existing software solutions, the developed software allows not only to segment customers by their costs, but also to provide marketing recommendations in order to increase the enterprise’s profit. The generation of recommendations is based on the developed mathematical support. By using this mathematical support, the calculations are carried out. Customers are allocated into certain groups, each of which is provided with the relevant marketing recommendations, by using the results of the performed calculations. In addition, the developed software solution allows not only to design sales funnels, but also to analyze sales funnels.
Исследование методов разработки программного обеспечения компьютерной инженерии на основе типовых программных элементов
(НТУ "ХПИ", 2019) Павленко, Евгений Петрович; Бутенко, Владимир Михайлович; Губин, Вадим Александрович
В работе рассматриваются проблемы повышения эффективности разработки ИС, и, в частности, вопросы уменьшения сроков разработки программного комплекса ИС. Проведен анализ технологий разработки программного комплекса в жизненном цикле ИС. Структурный подход к программированию предлагал осуществлять декомпозицию программ методом пошаговой детализации. Разработка структур программы выполняется при помощи построения структур входных и выходных данных, идентификации связей обработки между этими данными, формирования структуры программы на основании структур данных и обнаруженных соответствий. Преодолеть фактор сложности можно, если отойти от прямолинейного подхода к решению поставленной задачи, состоящего в последовательном и линейном наращивании исходного текста программы оператор за оператором, в результате чего получается одна длинная и аморфная программа. Оказывается действенным принцип модульности: исходная задача разбивается на относительно независимые части; они реализуются отдельными программными модулями, которые затем связываются в единое целое на этапе компоновки. Выделены особенности технологии автоматизированного синтеза программ, а именно, технологии сборки программ из типовых программных элементов. Определены основные понятия указанной выше технологии, проведено исследование конструирования программ из блоков и выявлена проблемная область. Исходными данными для постановки и решения задач синтеза системы программных модулей являются множество информационных массивов системы, для которых определены: входные, выходные и промежуточные данные; множество альтернативных процедур обработки данных; последовательности выполнения процедур в процессе обработки; способы обмена с внешней памятью. Рассмотрен подход для выделения типовых программных элементов, удовлетворяющих определенным критериям. На основании рассмотренного подхода, а также с учетом его недостатков, был предложен усовершенствованный метод классификации типовых программных элементов и способ проектирования ПО на их основе с учетом минимизации времени и стоимости проекта.
Combinatorial optimization under uncertainty and formal models of expert estimation
(НТУ "ХПІ", 2019) Pavlov, Alexander Anatolievich
Previously, the author formalized the concepts of uncertainty, compromise solution, compromise criteria and conditions for a quite general class of combinatorial optimization problems. The functional of the class’ problems contains linear convolution of weights and arbitrary numerical characteristics of a feasible solution. It was shown that the efficiency of the presented algorithms for the uncertainty resolution is largely determined by the efficiency of solving the combinatorial optimization problem in a deterministic formulation. A part of the formulated compromise criteri a and conditions uses expert weights. Previously, the author and his disciples also formulated combinatorial optimization models, optimality criteria, criteria for decisions’ consistency. The models allow to evaluate and justify the degree of stability and reliability of the estimated values of empirical coefficients using a formally ill-conditioned empirical pairwise comparison matrix of arbitrary dimension. The matrix may contain zero elements. The theoretical research and statistical experiments allowed to choose the most efficient of these optimization models. In this article, on the base of earlier results by the author and his disciples, we formalize and substantiate the efficiency of the proposed sequential procedure for expert estimation of weights that determine compromise criteria and conditions. The procedure is an integral part of the algorithm introduced by the author to solve combinatorial optimization problems under uncertainty of the mentioned class. We give unified algorithm for efficient uncertainty resolution that includes original and efficient formal procedure for expert coefficients’ estimation using empirical matrices of pairwise comparisons.
Нормативно-правове забезпечення діяльності у сфері транспорту
(НТУ "ХПІ", 2019) Смачило, Валентина Володимирівна
Економічна категорія "підприємство транспорту" є загальновживаним в економічному науковому та практичному обігу. Але, в той же час, її розуміння в правовому полі, яке визначає основи господарської діяльності в сфері транспорту, не є досить чітким. Вказане породжує проблему ідентифікації та віднесення до тієї чи іншої категорії суб'єктів господарювання транспортної галузі. Нормативно -правове забезпечення діяльності транспорту України базується на сукупності загальних законів та кодексів, які регулюють господарську діяльність будь-яких сфер національної економіки країни, а також на спеціальних нормативно-правових актах, які враховують специфіку транспортної сфери. Незважаючи на широке правове поле забезпечення діяльності транспорту, сучасні трансформації та виклики, що стоять перед галуззю, вимагають вирішення певних неузгодженостей задля коректного сприйняття понятійно-категоріального апарату, що формується в правовому полі, та його розвитку у відповідності з потребами часу. Метою дослідження є ідентифікація суб'єктів в сфері транспорту на основ і законодавчо-правового підходу. Рекомендовано ввести в нормативно-правове поле визначення транспортного підприємства (підприємства транспорту), яке б корелювало з його дефініцією в Господарському Кодексі України. Пропонуємо розкрити термін "транспортне підприємство" як самостійний суб'єкт господарювання, створений компетентним органом державної влади або органом місцевого самоврядування, або іншими суб'єктами для задоволення суспільних та особистих потреб шляхом систематичного здійснення господарської діяльності в сфері транспорту, відповідно до Закону України "Про транспорт", в порядку, передбаченому Господарським Кодексом та іншими законами України. Чітке окреслення понятійно-категоріального апарату відносно сутності підприємств транспорту в законодавчому полі та його поєднання із класифікацією видів економічної діяльності дозволить в майбутньому коректно формувати сукупність для аналітичної вибірки та здійснювати подальшу класифікацію.
Using graph embeddings for Wikipedia link prediction
(НТУ "ХПІ", 2019) Shaptala, Roman Vitaliyovych; Kyselev, Gennadiy Dmytrovych
Link prediction is an important area of study in network analysis and graph theory which tries to answer the question of whether two nodes in the graph might have an association in the future. Nowadays, graphs are ubiquitously present in our lives (social networks, circuits, roads etc.), which is why the problem is crucial to the development of intelligent applications. In the past, there have been proposed methods of solving link prediction problem through algebraic formulations and heuristics, however, their expressive power and transferability fell short. Recently, graph embedding methods have risen to popularity because of their effectiveness and the ability to transfer knowledge between tasks. Inspired by the famous in machine learning and natural language processing research Word2Vec approach, these methods try to learn a distributed vector representation, called an embedding, of graph nodes. After that a binary classifier given a pair of embeddings predicts the probability of the existence of a link between the encoded nodes. In this paper, we review several graph embedding approaches for the problem of Wikipedia link prediction, namely Wikipedia2vec, Role2vec, AttentionWalk and Walkets. Wikipedia link prediction tries to find pages that should be interlinked due to some semantic relation. We evaluate prediction accuracy on a hold-out set of links and show which one proves to be better at mining associations between Wikipedia concepts. The results include qualitative (principal component analysis dimensionality reduction and visualization) and quantitative (accuracy) differences between the proposed methods. As a part of the conclusion, further research questions are provided, including new embedding architectures and the creation of a graph embedding algorithms benchmark.