Алгоритмы сетевых методов, применяемые для планирования производства в базе данных «ЮНА-АСУП»

Ю.И. Долгова,

индивид. предприним., juna@telecomdubna.ru,

г. Дубна, Московской обл.

В предлагаемой базе данных изложены сетевые алгоритмы, необходимые для плановых расчетов. С их помощью решены следующие задачи:

· расчёт полного количества всех предметов на изделие;

· расчёт опережения всех предметов по отношению к выпуску изделия;

· выбор из общего состава в БД любого конкретного изделия или узла и ряд других.

The proposed network database described algorithms required for routine calculations. With their help accomplish the following tasks:

· calculate the total amount of all items on the product;

· calculation of the timing of all items in relation to the production of the product;

· selection of the overall composition of the database for any particular product or site, and several others.

1. Некоторые общие обозначения при использовании сетевых методов

Любую сеть, состоящую из множества каких-то взаимосвязанных работ, можно кратко обозначить так:

S( i , j ), где«i» и «j» - произвольные события (вершины) сети, причем

I – начальное событие работы (старшее), левое = старшее,

j – конечное событие работы (младшее), правое = младшее.

Таким образом, здесь уже определена ориентация сети от «i» к «j».

Запись ( i, j ) представляет собой отдельную работу, которая связывает два события (вершины): «i» и «j».

Будем считать равноценными определения «предмет», «событие» и «вершина» в сети. Так же будем считать равноценными понятия «работа», «связка» (связь) или пара предметов «старший» – «младший».

Каждая работа имеет определенное время для своего выполнения (продолжительность работы), а каждый младший предмет входит в свой старший обязательно с каким-то количеством, как минимум равным единице. Обозначим:

k_ij – количество, с которым младший предмет входит непосредственно в старший;

t_ij – продолжительность работы, т. е. время ее выполнения.

Тогда более полное представление любой записи в сети можно обозначить так:

( i , j , k_ij , t_ij) - это работа, направленная от события i к событию j с количеством k_ij и временем выполнения t_ij.

Итак, более полное обозначение сети в целом можно представить, как указано ниже:

S( i , j , k_{i j} , t_{i j} )или,немногоупрощенно, S( i , j , k, t ).

2. Применение сетевых методов для плановых расчётов

В данном проекте исходная для расчетов сеть уже построена – это состав SOS, который объективно представляет ориентированную иерархическую сеть, связывающую между собой все работы по изготовлению изделия.

Построена также таблица номенклатуры всех предметов, входящих в изделие – таблица NOM. Номенклатура предметов таблицыNOM соответствует таблице всех событий абстрактной сети S, где каждое событие представлено один раз. Обозначим таблицу событий абстрактной сети S как ТС. Тогда смысл и назначение таблиц NOM и ТС тоже будут равноценны между собой.

При создании таблицы SOS в каждой записи уже присутствуют пары двух предметов: старший – это ССЕ, т.е. старшая сборочная единица, и младший с именем ВХОД, т.е. входящий предмет, причем младший входит в старший обязательно со своим ненулевым количеством.

В таблице SOS пара предметов «старший – младший» кроме текстовых имен получает цифровые коды, взятые из таблицы NOM.

Итак, сеть S( i , j , k, t)построена. Вместе с ней построена также таблица событий ТС.

Сейчас можно сделать очень важное замечание – как только построена сеть S( i , j , k, t) с числовыми кодами событий, становится совершенно безразличным, какие материальные предметы (чертежи, кирпичи или еще что-то) были физически положены в основу при ее создании. В результате получена абстрактная цифровая сеть, к которой можно применять все доступные сетевые методы и расчеты. В этом смысле математические расчеты по отношению к сети, организованной на основе изделий машиностроительной продукции, носят универсальный характер и одинаково применимы к любому из ее объектов – от самых простых сетей до самых сложных.

3. Реализация алгоритма «спуска по сети»

Спуском по сети назовем передачу некоторого признака (обычно числового) от заданного старшего события к подчиненным ему младшим событиям, т. е. связанным с ним какими либо путями в сети. Алгоритм спуска является итерационным.

Здесь возникает ряд вопросов: «что спускать», «откуда и куда спускать», «как спускать» и зачем этот «спуск» необходим:

· Целью реализации алгоритма «спуска по сети» является выбор конкретного подмножества сети, подчиненного заданной вершине (событию). Можно сказать, что нужно выбрать подмножество, связанное в сети с заданной вершиной.

· «Что спускать» – нужно передавать некоторый числовой признак, например, во многих случаях допустимо «спускать» единицу «1». Иногда возможны и другие числа – в зависимости от поставленной расчетной задачи.

· «Откуда и куда спускать» –передавать выбранный числовой признак от старшего события в связке ( i , j ) к ее младшему событию – в полном соответствии с ориентацией сети S.

· «Как спускать» – описание этого алгоритма изложено ниже.

Алгоритм «спуска по сети» для выбора подмножества сети, определенного заданным начальным событием, и упорядочения этой сети по уровням иерархии изложен ниже. На практике такая задача называется «разузлованием сети». Одновременно решается также задача расчета полного количества

предметов на изделие и опережениедля всех событий в сети.

Исходными данными для реализации алгоритма спуска являются:

1) сеть S( i , j , k, t );

2) рабочая таблица S1, которая по структуре совпадает с таблицей S, но в которой пока нет записей. В нее будут помещены те записи, которые составят отобранное подмножество из сети S .

3) таблица событий ТС, в которой перечислены коды всех событий, составляющих исходную сеть S. Также в таблице определены шесть числовых рабочих столбцов, где каждое число – длинное целое. Описание ее можно считать таким:

· КС – код события, натуральное число (формирует система Access).

· VIX_K – столбец, куда будут помещаться числа для расчета количеств К и относящиеся к старшему событию « i », из которого «выходит» связка ( i , j);

· VX_K – столбец, куда будут помещаться числа для расчета количеств К и относящиеся к младшему событию « j », в которое «входит» связка ( i , j);

· VIX_O – столбец, куда будут помещаться числа для расчета опережений О и относящиеся к старшему событию « i », из которого «выходит» связка ( i , j);

· VX_O – столбец, куда будут помещаться числа для расчета опережений О и относящиеся к младшему событию « j », в которое «входит» связка ( i , j);

· K_R– рабочий столбец для хранения промежуточных данных по итерациям для расчета количеств;

· O_R– рабочий столбец для хранения промежуточных данных по итерациям для расчета опережений.

Или более наглядно:

Таблица событий ТС

Код события	VIX_K	VX_K	VIX_O	VX_O	K_R	O_R
1
2
N
i
…
j
…

1) Задана начальная вершина N, от которой нужно вести спуск.

Спуск начинается от заданного события с номером NтаблицыТС.

1. Поместить «1» в поля VIX_K, VX_K и K_R строки с номером NтаблицыТС) –

Этим самым заданы начальные значения для расчета.

2. Рассмотреть первую (текущую) записьS( i , j , k_ij , t_ij).

3. Вычислить количество по формуле:

если в поле VIX_K количество К ( i ) <>0, то вычислить

количество в событии ( j) по формуле:

К ( j ) = К ( j ) + К ( i ) * K_ij (в столбце VX_K).

4. Вычислить опережение О по формуле:

если сумма О ( i , j ) = О ( i ) + t_ij> О ( j ), то заменить

в строке ( j ) число О ( j ) числом О ( i , j ) (в столбце VX_O).

5. Поместить текущую запись сети S( i , j , k_ij , t_ij)в рабочую таблицу S1.

6. Проверка на окончание одного цикла итераций и на окончание всего алгоритма расчета в целом:

6.1. Если числовые значения в каждом из столбцов VIX_K и VIX_O равна нулю, то обработка исходной сети S окончена. При этом все выбранные записи из сети S перешли в сеть S1, а количества и опережения всех событий сети S рассчитаны и находятся в таблице событий в столбцах VX_K и VX_O.

Количество итераций заранее неизвестно, однако наблюдается закономерность, что с каждой выполненной итерацией в таблице событий обнуляются ячейки событий предыдущих, более высоких уровней иерархии (столбцы VIX_K и VIX_O), а на их место переходят события более низких уровней. Когда все уровни иерархии в сети S будут исчерпаны, в указанных столбцах (VIX_K и VIX_O) будут одни нули. Поэтому и сформулирован признак окончания всех итераций в сети как одновременное равенство нулю числовых значений в каждом из столбцов VIX_Kи VIX_O.

Алгоритм окончен положительно.

6.2. Иначе подготовка следующего цикла итерации:

Обнулить в столбцах VIX_K и VIX_O те строки, которые были начальными значениями для текущей итерации. / Работа с рабочими столбцами K_R и O_R, см. п.1/

Поместить только что рассчитанные в данной итерации значения количеств и опережений из столбцов VX_K и VX_O в столбцы VIX_K и VIX_O соответственно. Также переместить эти же значения в столбцы K_R и O_R, обнулив там предыдущие.

Выполнить переход на начало следующей итерации п. 2. /Комментарии. Таким образом, те события, которые в предыдущем цикле были «младшими», теперь будут выступать в роли «старших», причем начальные значения предыдущей итерации обнулены. Если в первой итерации «спуск» шел от вершин первого уровня иерархии к вершинам 2-го уровня в сети, то теперь «спуск» будет идти от вершин 2-го уровня к вершинам 3-го уровня и т.д./

6.3.Однако все вышесказанное верно только тогда, когда в исходной сети нет

логических ошибок в виде так называемых циклов или замкнутых контуров. В случае появления замкнутых контуров в сети возникает момент, когда вместо «спуска по сети» происходит возврат на «верхний» уровень» и с этого момента получается повтор с выбором записей из исходной сети S. При реализации в базе данных в таком случае возникает ошибка при перемещении записей в рабочую таблицу S1, так как появляется дубликат записи, что противоречит описанию таблицы. Система дает следующее сообщение о нарушении уникальности ключа:

«Приложению «MicrosoftOfficeAccess» не удается добавить все записи в запросе на добавление»

В приложении «MicrosoftOfficeAccess» значение Null присвоено следующему числу полей - N1 – (ошибка преобразования типа), не добавлено в таблицу следующее число записей – N2 (нарушение уникальности ключа), записей - N3 (нарушение блокировки), записей – N4 (нарушение условий на значения) /Комментарии. На самом деле ситуация, когда начиная спуск от некоторого исходного события i, выполняется последовательный переход через какую-то цепочку работ (записей сети S), и получен возврат опять к тому же исходному событию i, является ошибкой в реальной конструкторско-технологической сети.

С точки зрения реальных производственных сетей такая ситуация не имеет смысла: ни одна последовательность работ не может замыкаться сама на себя, так как все работы должны вести к одной цели – выпуску готового изделия.

В данном случае присутствует чья-то содержательная или формальная ошибка (например, ошибка ввода). Подобные ситуации подлежат серьезному анализу разработчиков сети и требуют исправления ошибок/.

В таком случае нужен останов решения: алгоритм окончен отрицательно. Нужен содержательный анализ исходной сети и исправление допущенных ошибок.

Выводы.

В рассмотренном выше алгоритме спуска по сети решены следующие задачи:

· выбор подмножества сети, определенного заданным начальным событием;

· упорядочения сети по уровням ее иерархии;

· расчет полного количества всех предметов;

· расчет опережений всех предметов.

Как видно из рассмотренного алгоритма, в результате вычисляются опережения всех событий в сети. Тогда опережение любой работы S( i, j, k_ij, t_ij) вычислить просто:

Время начала (запуска) работы равно времени опережения ее младшего события ( j ).

Время окончания работы равно времени ее начала плюс время ее продолжительности t_ij.

1. Определение начальных и конечных вершин в сети

Указанная функция может быть полезна для дополнительного контроля структуры сети, что особенно важно в случае больших сетей. Реализация логического контроля сети в базе состоит в том, что каждый конструкторский предмет в таблицах состава и номенклатуры дополняется специальным полем под названием «тип предмета».

Начальным событием сети является такое событие, из которого выходят работы, но ни одна не входит в него.

Конечным событием сети является такое событие, в которое входят работы, но ни одна не выходит из него.

Начальным событием в конструкторской сети могут быть только сами основные изделия, которые известны заранее, они помечены в таблицах типом предмета «из».

Конечными вершинами в сети могут быть только неделимые предметы (детали, покупные), которые не имеют своего состава. Они также помечены специальным признаком «д». Промежуточные вершины (узлы) имеют другие «типы».

Логический контроль сети может быть следующим: каждая начальная вершина должна иметь признак «из», иначе имеем ошибку – разрыв в сети /возможно, какой-то узел оказался никуда не привязан/. Точно так же и каждая конечная вершина должна иметь свой «тип предмета», который «разрешает» ей не иметь своих составляющих. Если у конечной вершины оказался другой тип предмета, то это ошибка: возможно, какой-то узел оказался без состава.

Расчёт начальных и конечных вершин в сети можно получить как следствие при реализации алгоритма спуска в п. 3, причем значительно упростив его.

Алгоритм определения начальных и конечных вершин в сети.

Исходные данные:

1) сеть S ( i , j , k, t );

2) таблица событий ТС, описание ее то же, что и в п. 3, но в данном случае можно использовать не все столбцы, а только два из них, например:

· VIX_O – столбец, где будет суммироваться количество работ (связок), выходящих из каждого события ( i ) ;

· VX_O – столбец, где будет суммироваться количество работ (связок), входящих в каждое событие (j ).

За один просмотр всей сети S можно получить в каждой строке VIX_O таблицы ТС сумму выходящих из этого события работ.

Так же за один просмотр сети S можно получить в каждой строке VX_O таблицы ТС сумму входящих в это событие работ.

В результате этих просмотров те события в столбце VIX_O, где значения счетчиковравны нулю, определяют конечные события – из них не выходит ни одна работа.

Точно так же те события в столбце VX_O, где значения счетчиков равны нулю, определяют начальные события – в них не входит ни одна работа.

Алгоритм окончен.

Очевидно, что события, где в одной строке одновременно значения VIX_Oи VX_Oтаблицы ТС равны нулю, рассматривать не нужно, так как эти события не входят в заданное изделие.

2. Корректировка по удалению или ограничению узла в информационной базе

Одной из важных функций при поддержании информационной базы в рабочем состоянии является операция корректировки по удалению или ограничению узла вбазе. Алгоритм спуска по сети хорошо работает для выполнения этой важной функции. Очень важно автоматизировать указную функцию с распространением этого свойства на весь состав узла. Человек указывает только номер чертежа конкретного узла, который нужно снять (удалить), а распространить это свойство на весь состав данного узла должна автоматизированная обработка.

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

3. Определение вышестоящих узлов, в состав которых входит заданная деталь (узел)

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

Здесь достаточно поменять ориентацию сети в противоположном направлении – от деталей к изделию. Тогда по связности сети можно отобрать все подмножество вышестоящих узлов, которым подчинены заданная деталь или узел.

Заключение

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

· выбор подмножества сети, определенного заданным начальным событием;

· упорядочения сети по уровням ее иерархии;

· расчёт полного количества всех предметов на изделие;

· расчёт опережений всех предметов по отношению к выпуску готового изделия;

· определение начальных и конечных вершин в сети;

· корректировка по удалению или ограничению узла в базе;

· определение вышестоящих узлов, в состав которых входит заданная деталь (узел).

Все перечисленные выше функции обработки информации, реализованные и используемые на практике, могли бы существенно помочь в автоматизации вопросов планирования производства на многих предприятиях нашей страны.

Литература

1. Проект системы сетевого планирования и управления работами по созданию новой техники КОМПАС-НТ-1. Раздел II, часть I. Алгоритмы обработки информации. Москва, НИАТ, 1965г.

2. Долгова Ю. И. «Автоматизированная система управления производством» // Журнал «Машиностроитель», № 9 стр. 40-43, 2005 г.

3. Долгова Ю. И. «Автоматизированная система управления производством» // Журнал «Машиностроитель», № 10 стр. 21-26, 2005 г.

4. Долгова Ю. И. «Автоматизированная система управления производством» // Журнал «Машиностроитель», № 11 стр. 2-7, 2005 г.

5. Долгова Ю. И. «Автоматизированная система управления производством» // Журнал «Машиностроитель» № 12 стр. 12-19, 2005 г.

6. Долгова Ю. И. «Автоматизированная система управления производством». // Журнал «Машиностроитель», № 1 стр. 41-45 2006 г.

7. Долгова Ю. И. «Автоматизированная система управления производством». // Журнал «Машиностроитель», № 2 стр. 28-34, 2006 г.

8. Свидетельство о государственной регистрации базы данных. «База данных «ЮНА-АСУП» - Планирование машиностроительного производства» № 2012621039 от 5 октября 2012 г.