Древовидная структура
Материал из Supply Chain Management Encyclopedia
Zyatchin (обсуждение | вклад) |
Zyatchin (обсуждение | вклад) |
||
(4 промежуточные версии не показаны) | |||
Строка 1: | Строка 1: | ||
- | Обозначения и методы решения, применяемые для | + | '''English: [http://scm.gsom.spbu.ru/Tree_systems Tree systems]''' |
+ | |||
+ | Обозначения и методы решения, применяемые для линейных систем (см. раздел [[линейная структура]]), применимы и к системам с древовидной структурой<ref> Zipkin P. (2000) Foundations of inventory management; The McGraw-Hill Companies, Inc.</ref> (подробнее о структурах логистических и производственных процессов см. раздел [[Структура многопродуктовых систем с несколькими складами]]). Более того, эти подходы применимы и для систем общего вида при введении ограничений на время доставки материалов между узлами. | ||
Формализация системы древовидного типа и построение сети проводится на основании основных свойств системы. Система древовидного типа является ориентированным графом, который определяется парой множеств <math>\,(N,A)</math>, где <math>\,N</math> -- множество узлов, <math>\,J=|N|</math> -- количество узлов. Множество ребер <math>\,A</math> описывает отношения типа спрос-снабжение или вход-выход в производственном процессе. Ребро из узла <math>\,i</math> в узел <math>\,j</math> обозначается <math>\,(i,j)\in A</math> и означает, что часть продукта типа <math>\,i</math> используется для производства продукта <math>\,j</math> (если существует несколько узлов <math>\,i</math> таких, что <math>\,(i,j)\in A</math>, это означает, что все они используются для производства <math>\,j</math>). | Формализация системы древовидного типа и построение сети проводится на основании основных свойств системы. Система древовидного типа является ориентированным графом, который определяется парой множеств <math>\,(N,A)</math>, где <math>\,N</math> -- множество узлов, <math>\,J=|N|</math> -- количество узлов. Множество ребер <math>\,A</math> описывает отношения типа спрос-снабжение или вход-выход в производственном процессе. Ребро из узла <math>\,i</math> в узел <math>\,j</math> обозначается <math>\,(i,j)\in A</math> и означает, что часть продукта типа <math>\,i</math> используется для производства продукта <math>\,j</math> (если существует несколько узлов <math>\,i</math> таких, что <math>\,(i,j)\in A</math>, это означает, что все они используются для производства <math>\,j</math>). |
Текущая версия на 15:29, 17 сентября 2012
English: Tree systems
Обозначения и методы решения, применяемые для линейных систем (см. раздел линейная структура), применимы и к системам с древовидной структурой[1] (подробнее о структурах логистических и производственных процессов см. раздел Структура многопродуктовых систем с несколькими складами). Более того, эти подходы применимы и для систем общего вида при введении ограничений на время доставки материалов между узлами.
Формализация системы древовидного типа и построение сети проводится на основании основных свойств системы. Система древовидного типа является ориентированным графом, который определяется парой множеств , где -- множество узлов, -- количество узлов. Множество ребер описывает отношения типа спрос-снабжение или вход-выход в производственном процессе. Ребро из узла в узел обозначается и означает, что часть продукта типа используется для производства продукта (если существует несколько узлов таких, что , это означает, что все они используются для производства ).
Граф системы древовидного типа является связным и не содержит циклов: не существует такой группы продуктов, которая производилась бы отдельно от остальных продуктов, и ни один не используется явно или неявно для производства самого себя. Узлы нумеруются таким образом, что , если . Если , то является (непосредственным) предшественником для , а является наследником для . Введем следующие обозначения:
-- множество предшественников для
-- множество наследников элемента
Эти множества содержат информацию о входах и выходах для каждого узла. Начальный узел в сети единственный из всех узлов не имеет предшественника. Окончательный узел единственный из всех узлов не имеет наследников. Только начальный узел снабжается извне -- в случае производственного процесса это соответствует получению исходных материалов для производства.
В такой терминологии система сборочного типа имеет только один окончательный узел и каждый узел имеет единственного наследника. Здесь узел может иметь несколько предшественников (в отличие от систем последовательного типа). Системы распределительного типа, напротив, имеют единственную начальную вершину 1 и каждый узел имеет единственного предшественника. Один узел может иметь несколько наследников. Формальное определение системы древовидного типа требует дополнительных предположений и может рассматриваться (не принимая во внимание направление ребер), как неориентированный граф без циклов. При таком условии каждый объект может иметь несколько предшественников и наследников. Во всех случаях количество ребер равно .
Стоимостные параметры , и функция имеют те же значения, что и в системе последовательного типа. Введем новое обозначение для интенсивности спроса узла :
Только окончательная вершина может иметь положительную интенсивность спроса .
Содержание |
Время доставки
Каждое ребро имеет соответствующее время поставки . Пусть время поставки от внешнего источника до начальной вершины обозначается . Все эти величины являются неотрицательными. Соответствующая система с нулевым временем поставки имеет такие же параметры, что и система древовидного типа, за исключением и , которые принимают нулевые значения.
Рассмотрим узел с несколькими предшественниками. Время поставки может включать время на поставку, а также время, необходимое на сборку. Таким образом, в общем случае зависит от . Для производства партии в узле к моменту соответствующая поставка для узла должна быть подготовлена к моменту . Следовательно, момент размещения заказа в такой системе зависит от предшественников узла и для каждого из них определяется отдельно. При этом существенными показателями также становятся время отправки и время прибытия материалов: зависит от всех поставок в узел и поставок из узла .
Эшелоны
Эшелон состоит из узла , наследников узла и всех последующих наследников. Таким образом, эшелон содержит и все последующие узлы, которые напрямую или косвенно используют продукт, произведенный в узле .
Запас в эшелоне определяется как сумма запасов в каждом узле эшелона, интенсивность спроса в эшелоне определяется как сумма всех локальных показателей интенсивности во всех узлах эшелона. Эти величины могут быть вычислены рекурсивно, начиная с последнего узла:
Затраты на хранение в эшелоне имеют вид:
В системах сборочного типа, например, эшелон состоит из вершин, находящихся в пути от вершины до . При этом для всех имеет место равенство: и, если является единственным элементом множества , то
Как и в системе с линейной структурой, суммарные затраты на хранение в эшелоне в момент времени имеют вид:
Задача нахождения оптимального размера запасов
В отличие от структур линейного типа, в системах с древовидной структурой политика, построенная на основе стационарных интервалов, не обязательно является доминирующей. При этом такой подход по-прежнему является удобным для анализа и дает решение, достаточно близкое к оптимальному.
Вложенная политика управления запасами -- это такая политика, в которой оформление заказа в узле влечет за собой оформление заказа всеми наследниками этого узла, а, следовательно, -- в каждом узле эшелона. В системах с линейной и сборочной структурой вложенная политика оказывается доминирующей. В системах с древовидной структурой это свойство выполняется не всегда. В качестве примера рассмотрим систему со структурой, представленной на рисунке 1. Здесь узел 1 соответствует складу, который снабжает узлы 2 и 3. Предположим, что интенсивность спроса узлов 2 и 3 одинаковая, , все равны, , , . Последние два неравенства приводят к тому, что заказы на узлах 2 и 3 буду проходить чаще, чем на узле 3, следовательно, политика управления запасами не является вложенной. Несмотря на это, в некоторых случаях применяется вложенная политика, поскольку ее применение значительно проще.
Рассмотрим политику управления запасами, учитывая предположение о стационарности интервалов между заказами и вложенности. Рассмотрим величину
Тогда средние затраты в зависимости от продолжительности интервалов принимают вид:
Задача поиска оптимальной политики управления запасами является задачей целочисленного линейного программирования следующего вида:
, -- целое,
References
- ↑ Zipkin P. (2000) Foundations of inventory management; The McGraw-Hill Companies, Inc.