Алгоритм поиска времени завершения сложного проекта

Abstract

RU: Постановка проблемы. Рассматривается задача минимизации времени построения сложной системы, которая состоит из множества подсистем. Такие задачи возникают на производстве, в строительстве, управлении, информатике и других областях. Построение системы предполагает последовательное построение ее подсистем, состоящих из множества элементов. Эти элементы в заданные моменты времени поступают на вход системы построения. Известный технологический маршрут каждого элемента и каждой подсистемы, включающей заданное множество элементов, а также время обработки каждого элемента и подсистемы. Построение сложной системы представляется в виде сетевого графика, который определяет последовательность ее построения. Этот сетевой график в данном случае представляет дерево дуг, основой которого является завершение построения сложной системы. При заданных временах поступления элементов системы и их соединения в подсистемы минимальное время построения системы равно критическому пути данного сетевого графика. Для его нахождения, необходимо определить время завершения каждой подсистемы. Это время зависит от времени готовности всех элементов подсистемы для ее сборки. Время критического пути может быть уменьшено посредством устранения ожиданий на участках сборки подсистем. Минимизация ожиданий позволяет получить критический путь минимальной длины. Существуют такие моменты времени поступления элементов сложной системы на входе сетевого графика, для которых суммарное ожидание элементов и их подсистем на каждом пункте сборки будет минимальным. Определение таких моментов поступления на вход системы необходимо начинать с конца сетевого графика. Уменьшение времени завершения cборки системы влечет за собой уменьшение времени поступления составляющих ее элементов. Это уменьшение влечет за собой уменьшение времени поступления элементов подсистемы на предшествующий пункт сборки. Такое прохождение сетевого графика от конца к началу с изменением времен поступления элементов подсистем позволяет минимизировать ожидания начала сборки подсистем на каждом участке. Это достигается посредством определения оптимальных времен поступления элементов на входе сетевого графика. После проделанных изменений критический путь необходимо пересчитать и только в том случае, если его значение не будет изменено, будет найдено минимальное время построения сложной системы. Для реализации данного алгоритма вычисления минимального времени построения сложной системы разработана компьютерная программа и проведены численные эксперименты, которые подтверждают эффективность данного алгоритма.

UK: Постановка проблеми. Розглядається задача мінімізації часу побудови складної системи, яка складається з множини підсистем. Такі задачі виникають на виробництві, в будівництві, управлінні, інформатиці та інших прикладних галузях. Побудова системи передбачає послідовну побудову її підсистем, що складаються з безлічі елементів. Ці елементи в задані моменти часу надходять на вхід системи. Відомий технологічний маршрут кожного елемента і кожної підсистеми, що включає задану кількість елементів, а також час обробки кожного елемента і підсистеми. Побудова складної системи подається у вигляді мережевого графіка, який визначає послідовність її побудови. Цей мережевий графік у даному випадку являє собою дерево дуг, основою якого є час завершення побудови складної системи. При заданих моментах надходження елементів системи та їх складання в підсистеми, мінімальний час побудови системи дорівнює критичному шляху даного мережевого графіка. Для його знаходження необхідно визначити час завершення кожної підсистеми. Цей час залежить від часу готовності всіх елементів підсистеми для її складання. Час критичного шляху може бути зменшений за допомогою усунення очікувань на ділянках складання підсистем. Мінімізація очікувань дозволяє отримати критичний шлях мінімальної довжини. Існують такі моменти часу надходження елементів складної системи на вході мережевого графіка, для яких сумарне очікування елементів та їх підсистем на кожному пункті складання буде мінімальним. Визначення таких моментів надходження на вхід системи необхідно починати з кінця мережевого графіка. Зменшення часу завершення складання системи тягне за собою зменшення часу надходження складових її елементів. Це зменшення тягне за собою зменшення часу надходження елементів підсистеми на попередній пункт складання. Таке проходження мережевого графіка від кінця до початку зі зміною часів надходження елементів підсистем дозволяє мінімізувати очікування початку складання підсистем на кожній ділянці. Це досягається за допомогою визначення оптимальних часів надходження елементів на вході мережевого графіка. Після виконаних змін критичний шлях необхідно перерахувати і тільки в тому випадку, якщо його значення не буде змінено, буде знайдене мінімальний час побудови складної системи. Для реалізації даного алгоритму обчислення мінімального часу побудови складної системи розроблено комп'ютерну програму та проведено числові експерименти, які підтверджують ефективність даного алгоритму.

EN: Problem statement. The article discusses the problem of minimizing the construction time of a complex system, which consists of the set of subsystems. Such problems arise in manufacturing, construction, management, computer science and other fields. Building a system requires consistent construction of its subsystems, which include numerous elements. These elements are supplied to the system’s entrance at specific moments of time. The technological route of each element and each subsystem consisting of a given number of elements, as well as the processing time of each element and subsystem are known. Construction of a complex system is represented as a network graph, which determines its construction sequence. The network graph in this case is a tree of arcs, the root of which is the completion of a complex system’s construction. With a given times of system elements supply and of their compounding into subsystem, the minimum time of system’s construction is equal to the critical path of network graph. To find the critical path it is necessary to determine the completion time of each subsystem. This time depends on availability time of all elements of subsystems required for its assembly. Time critical path can be reduced by removing the idling in the areas of subsystems assembly. Minimization of idling periods provides a critical path of minimum length. There are such timings of complex system element’s arrival at the entrance of network graph for which the total idle periods of elements and subsystems at each point of the assembly will be minimal. Determining such moments of arriving at system’s entrance requires starting from the end of the network graph. Reducing the completion time of system’s assembly entails a reduction in the time of its elements arrival. This reduction leads to a decrease in the arrival time of the subsystem’s elements on the previous point of assembly. Such passage from end to beginning of the network graph, changing times of subsystems’ elements arrival allows minimizing idle periods before the assembly of sub- systems at each region. This is achieved by determining the optimum arrive timings of elements at the entrance of network graph. After the performed changes the critical path must be recalculated and only if its value is not changed, the minimum construction time of complex system will be found. To implement the computing algorithm of minimization of a complex system’s construction time, a computer program is developed and the numerical experiments that confirm the effectiveness of the algorithm are performed.