Зацикливание при расчёте себестоимости продукции

[Swetlana]

Описание задачи, техзадание

ОБНАРУЖЕНИЕ ЦИКЛОВ В ПРОИЗВОДСТВЕННЫХ ЗАДАНИЯХ МОДУЛЯ “УПРАВЛЕНИЕ НЕПРЕРЫВНЫМ ПРОИЗВОДСТВОМ”

Решения Oracle E-Business Suite для управления непрерывным производством позволяют оптимизировать всю производственную цепочку предприятия, начиная от закупок сырья и заканчивая выпуском готовой продукции, независимо от типа производства. Актуальными задачами являются планирование и прогнозирование затрат на производство продукции. Управление затратами на производство включает калькуляцию плановой и фактической себестоимости. В схемах по производственным заданиям отражается количество израсходованных ингредиентов, полученных продуктов, с указанием конкретных складских мест.

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

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

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

[Swetlana]

Разговор с заказчиком

Разговор с заказчиком был очень смешным. Собственно, после этого разговора заказчиков я уже не видела, а необходимую информацию получала от коллег по хоздоговору.
Появляется заказчик, в дорогом костюме, с ароматом французского парфюма (парфюм, к слову, был хороший), начальник какого-то отдела.
- Вот это наш математик-постановщик, Светлана Ильдаровна, закончила мехмат МГУ...
На автопилоте подумала. что шеф попутал, кого кому нужно представлять, но сказала "очень приятно", в ответ получила "маленький английский кивок". Так что заказчик остаётся анонимом
Когда дошло до дела, попыталась сделать 2 вещи.
1. Объяснить заказчику, что нельзя формулировать задачу как обнаружение ВСЕХ орциклов в графе производственных заданий. Потому что задача класса E, циклов может оказаться экспоненциальное количество от размерности графа (граф состоял из 62000 дуг), т.е. мы запрашиваем большую информацию. чем можем использовать. А на самом деле мы просто хотим разомкнуть все орциклы путём удаления некоторого множества дуг за линейное время. Это сделать не удалось, поэтому в названии хоздоговора так и осталось "обнаружение циклов".
2. В связи с незнанием Оракла выяснить, что является дугами, из которых этот граф строится. Заказчик сказал, что он не готов ответить на мой вопрос - приходите, когда будете готовы.

Через день заказчик подготовил и распечатал целую презентацию, оказалось, что дугами являются производственные задания типа Позиция1/Склад1 -> Позиция2/Склад2, и входными данными для моего "пробника" будет список таких дуг.

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

[СергейП]

Может оно и интересно с точки зрения математики, а практически выглядит сомнительно.
В нормально спроектированной системе замкнутых циклов, ИМХО, не должно быть.
Насколько непрерывным не было бы планирование, в системе всё равно есть дискретные события - поступление сырья, выход из строя оборудования и т.п.
Произведённый брак - такое же дискретное событие. Условно говоря оператор жамкает кнопочку и вместо готовой продукции появляется сырьё спец. вида, планировать надо заново.

[Swetlana]

Это недостаток Оракла, разумеется, что процедура расчёта себестоимости предполагала, что граф заданий является ациклическим. Вроде бы в более новых версиях он устранён.
Вероятно, эта задача возникает ещё где-то. В интернете часто задают вопрос "Как найти фундаментальные ориентированные циклы".
ЗЫ. Я просто выполняю просьбу модератора

Математическая постановка задачи

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

Математическая постановка задачи

Производственные задания вида (Позиция_1|Склад_1) (Позиция_2|Склад_2),
участвующие в расчете себестоимости, образуют множество E дуг (или ориентированных ребер) ориентированного графа G = <V, E>. Множество вершин V состоит из пар вида (Позиция|Склад).
Для машинного представления G ориентированного графа используются списки инцидентности следующих вершин, которые в алгоритме будут обозначаться L.
Дано. Ориентированный граф G, заданный списками инцидентности L.
Вопрос. Напечатать множество обратных дуг, для каждой дуги один замыкаемый ею цикл.
Алгоритм. Поиск в глубину.
Вычислительная сложность. O(nm).

Описание поиска в глубину находится здесь
[url=http://magazine.sources.ru/2010/03/algoritm_graf/]http://magazine.sources.ru/2010/03/algoritm_graf/[/url]

Демонстрационная программа в прикреплённом файле





[img]/modules/file/icons/application-octet-stream.png[/img] ______Oracle.rar

[zykov]

Source of the post
Зацикливание расчета себестоимости происходит, например, в ситуации, когда позиция, представленная как произведенный продукт, на следующем шаге используется как ингредиент в предыдущем производственном задании (например, бракованную листопрокатную продукцию отправили в металлолом).

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

[Swetlana]

Их процедура (расчёта себестоимости) в случае зацикливании действительно запускалась несколько раз. В хоздоговоре был текст "не более 10 минут на один проход", т.е. они не ожидали, что всё можно сделать за один проход.

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

[av.polyakov.new]

Source of the post Для устранения такой ситуации необходимо разработать процедуру обнаружения циклов в производственных заданиях.

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