Добрый день!

Продумываю структуры и логику для организации работы с многоуровневым BOM (bill of materials). По факту, это граф с одной вершиной в нашем случае. Но при этом с циклами. Т.е. один материал может входить в несколько узлов, причем разного уровня. Тогда у нас могут проявляться линейные алгебраические уравнения с несколькими коэффициентами (а если уровней много, то и не очень линейные).
Так же возможны ситуации, когда можно оперировать только целыми единицами или целыми+дробными. В общем, чем дальше - тем веселее.
Интересуют есть ли исследования по алгоритмам, рассмотрение введение ограничений для упрощения учета и прочее. Идей много, надо разложить оп полкам. Буду рад любой помощи.

ViPRos,

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

Вот произвольный пример в приложении.

Кот МатроскинDrac013Тогда у нас могут проявляться линейные алгебраические уравнения с несколькими коэффициентами (а если уровней много, то и не очень линейные).

Целые + дробные я бы решал выбором соответствующей единицы измерения - подозреваю что "точность" дробной части везде четко ограничена.

Есть такой соблазн. Если требуются дробные части, то вводить новые базовые единицы. Но это потребует много движений в уже существующем функционале. Поэтому стоит попробовать сначала реализовать логику целые+дробные в зависимости, например, от номенклатуры. Т.е. жесткие диски мы не можем потрать 1,5 или 2,2, а вот 0,1 пачки винтов вполне можно.

Кот Матроскин,

Переход к виртуальным единицам в рамках алгоритма - интересное решение. Попробую опереться на него.

Осталось разобраться с математикой. Понятно, что нам необходимо найти максимум для уравнения:

1*(2*(3*K+1*G)+3*G)+2*(3*3*G +4*(G+2*J+3*I)).

Но нас волнуют не только остатки материалов G,K,I и J, но и узлов B,D,C,E,F,H. Было бы легко разложить остатки узлов на материалы, но в общем случае это невозможно (если ПК на составляющие можно разобрать, то тесто на муку, дрожжи и прочее уже сложнее :) ).

ViPRos,

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

Например, собираем ПК. По умолчанию, в нем один диск. Но конкретный заказ подразумевает 2 диска. Тогда в документе к материалам по умолчанию добавляем еще один HDD и пересчитываем возможности сборки.

Пока вот изучаю литературу по теме.

Ы,

Давайте без винтов. Ткань приходуется и учитывается метрами, а списываться на пошив (да, и продажу тоже) может и по 0,5 и по 0,15. Переводить учет на сантиметры мало кому придет в голову, да и не особо рационально.

Кот Матроскин,

виртуально рассыпать :) Это вполне удобно. Точность ограничена. Поэтому мы всегда сможем перейти к целым виртуальным единицам и вернуться от них обратно на выходе.

ViPRos,

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

[quot Кот Матроскин]Drac013ViPRos,
Если же схема строго одна - то чего там оптимизировать?
самый тупой и простой в реализации способ - в цикле рассчитывать производство каждой единицы готвоой продукции, пока не обнаружится недостача в одном из "элементарных" материалов.

Не, задача "можем ли мы произвести n единиц товара?" - очень легкая. У меня обратная задача: "Какое количество материала мы можем произвести?". Т.е. необходимо рассчитать максимально возможное n.

Причем для подчиненных узлов это придется рассчитывать еще с учетом весового коэффициента. Например, продукт P состоит из одного узла N1 и одного N2, N1 и N2 требуют по одной единице материала M1, которого на складе m штук. Казалось бы, мы можем произвести m штук N1 и m штук N2, но т.к. нам нужны оба узла для производства P, то фактически мы можем произвести m/2 штук каждого из них.

Кот Матроскин,

кажется, понял, что вы имеете ввиду. А если таких циклов будет 1000? 10000? 0_о Да уровней штук 5 хотя бы. Мне это и в интерфейсе пересчитывать придется иногда (меняем в документе состав для текущей сборки).

Хм, мы можем быстро посчитать границу сверху (разложив все на элементарные материалы), проверить ее. И пойти медианным методом. Тогда более менее прилично выходит.

kva6513, почитаю, спс.

Кот Матроскин,
обход дерева - это сам по себе цикл. Т.е. каждая итерация - это именно что новый цикл обхода по дереву. Вот что смущает. Понятно, что настоль прямолинейно действовать нельзя. Прикину еще варианты. Если аналитически решение будет не найти (в чем я почти уверен), то будем решать подобным образом.

Собственно так и сделал в итоге. Получаю верхнюю границу остатков из материалов с учетом разложения узлов до простых материалов. И дальше последовательными приближениями с начальными точками в 1 и в ВерхнейГранице ищу количество, которое можно собрать. Думаю, что-то оптимальнее сложно найти.

Что ж, оказалось, что задача подсчета еще цветочки.

Теперь надо получить количество материалов и сборок, которые необходимы для N единиц продукта. При двух стратегиях: 1 - используем готовые узлы в первую очередь, 2 - используем сначала материалы.

При этом, мы уже знаем, что требуемое количество N мы можем произвести. Задача в первом варианте решается элементарно. А вот во втором... Попробовал уже пару алгоритмов реализовать, но они дают не оптимальный результат. Единственный гарантированный вариант - это методом итераций определить количество возможных сборок для каждого узла. Думаю, "эффективность" такого метода очевидна. Пытаюсь придумать что получше. Есть ли какие-нибудь идеи?

Вот пример дерева BOM, которое сломало пару моих алгоритмов.

Так, вот картинка:

iscrafm,

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

В подсчете количества и расхода по первой стратегии проблем нет совсем.

Кот МатроскинDrac013,

Это несложный кейс, и с ним разберется относительно простой алгоритм "посчитать стоимость в элементарных материалах, если элементарного материала не хватает - пытаться заменить его узлами, в которые он входит, снизу вверх, т.е. сначала взять сколько есть узлов G, уменьшив потребность в элементарном материала D на "стоимость" взятых G, потом узлов E, потом узлов С".

Примерно такой алгоритм и ломается на этом дереве. У нас есть довольно сильное утверждение, что требуемое N мы можем собрать. Я пытался сделать так: иду от корня дерева к его ветвям. Если текущий узел дерева - это сборка, то я пробую собрать его полностью, т.е. иду ниже. Как только я натыкаюсь на материал, то уже проверяю, достаточно ли его в наличии. Если да, то списываю из таблицы остатков. Если нет, то ищу другие узлы по уровню ниже текущего, где могу "позаимствовать" этот материал. Как только нашел такой узел, то иду от этого узла в сторону корня, заменяя родительские сборки на количество из остатков (если они есть, если нет, то иду еще выше). Но этот алгоритм не дает оптимального значения в конце.

[quot Кот Матроскин]Drac013пропущено...
Ээ, а что такое "оптимальное значение"? Вам важен только минимум остатка элементарных материалов, какого уровня узлы потрачены - не важно?

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

[quot iscrafm]у одного и того же изделия не может быть различного времени сборки или скорости сборки. [quot]

У одного изделия быть не может. А у разных узлов этого изделия может быть. Один узел, где используется материал М, собирается 4 недели, другой - 4 дня. Поэтому, если у нас поджимают сроки, то мы предпочтем взять готовый первый узел. А если заказ не срочный, то лучше этот узел собрать, чтобы запас на срочные заказы конечного продукта остался.

kva6513,

мы сейчас отвлеклись на то, что отбросили :)

Критерий один: максимально использовать простые материалы при производстве заданного количества продукта.

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

kva6513Drac013максимально использовать простые материалы при производстве заданного количества продукта.
Т.е. критерием становится выбор по максимизации добавленной стоимости ?
Нет. Критерий - максимальное количество простых материалов :) Т.е. сначала тратим их, а когда их не хватает, то начинаем использовать уже узлы. Стратегии упрощены, ибо усложнения могут даже не понадобиться.

iscrafmУ вас проблема другого рода. BOM здесь совершенно не при чем. Просто сдвигаете процесс изготовления, последовательность, очередность.... Вопрос просто неправильно озвучен изначально.

Вопрос озвучен корректно и довольно правильно. Надо либо тратить сперва готовые узлы (ускоряем производства и отгрузку). Либо надо стараться по максимуму использовать материалы, чтобы не уменьшать запасы узлов. Все просто. Другое дело, что в таком виде задача сводится к многомерному рюкзаку, как правильно заметил Кот Матроскин. И при увеличении узлов BOM будет непомерно расти потребность в ресурсах. Думаю, задачу будем слегка изменять.

iscrafm Ну так определите критерий - что такое "простой материал". Шевеления пальцами в воздухе в алгоритм не превратить никак. :) Я думал, уже все поняли, что простой материал - это тот, который не сборный. Если вы все еще не поняли сути задачи, то хотя бы не ехидничайте попусту.

Прошу прощения, вторая цитаты не того пользователя. Она предназначалась kva6513.

iscrafmвопрос поставлен совершенно некорректно. BOM здесь совершенно не при чем. Почитайте что такое Push и Pull стили производства. Потребность в ресурсах будет расти, если будете бесполезно "на склад" работать.
В качестве резюме: нужно отладить производственный процесс, прежде всего. Вы ставите вопросы, которые совершенно не решаются BOM и судя по всему менять тактику подхода не собираетесь. Т.е. отдайте решение задачи производственному специалисту, по программерски у вас совершенно невпопад получается. "Многомерный рюкзак", увеличение узлов BOM..

p.s. и не приписывайте мне чужие цитаты. Аккуратнее при цитировании.

Задача решается в рамках требований. Вы действительно думаете, что реализация полноценного MRP или JIT в рамках, скажем, пиццерии, магазинчика ПК, фирмы по установке кондиционеров и прочего мелкого "производства" имеет рациональное зерно? :)
А вот реализация поставленных стратегий именно в таком упрощенном и утрированном виде имеет смысл. У меня даже BOM может отличаться от описанного по умолчанию на этапе сборки (захотел покупатель 10 пицц "Маргарита" с двойной порцией сыра и фрикадельками). В рамках полноценного производства из кучи цехов и отделов такая задача не имеет смысла, а в описанных масштабах более чем. Не придумывайте задачу за меня :)

P.S.: по цитированию я отписался следующим постом.

[quot kva6513 ]
Ну если у вас в программе можно написать
IF Материал не сборочный THEN


то нет вопросов, чивоужтам. [quot]

0_о для вас проверить наличие дочерних узлов у текущего узла дерева - это что-то невероятное? Хм.

iscrafm Если строка не готова, то помечаете ее как "в производство" и т.п. с соответствующими временными допусками. Все достаточно просто и банально. Не забивайте мозг различными рюкзакам.
Поймите, вы пытаетесь дать решение другой задачи! Не той, что стоит передо мной. Она не правильная или неправильная, она другая.