Древовидная структура

Материал из Supply Chain Management Encyclopedia

(Различия между версиями)
Перейти к: навигация, поиск
 
(6 промежуточных версий не показаны.)
Строка 1: Строка 1:
-
Обозначения и методы решения, применяемые для последовательных систем, применимы и к системам с древовидной структурой<ref> Zipkin P. (2000) Foundations of inventory management; The McGraw-Hill Companies, Inc.</ref>. Более того, эти подходы применимы и для систем общего вида при введении ограничений на время доставки материалов между узлами.  
+
'''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] (подробнее о структурах логистических и производственных процессов см. раздел Структура многопродуктовых систем с несколькими складами). Более того, эти подходы применимы и для систем общего вида при введении ограничений на время доставки материалов между узлами.

Формализация системы древовидного типа и построение сети проводится на основании основных свойств системы. Система древовидного типа является ориентированным графом, который определяется парой множеств \,(N,A), где \,N -- множество узлов, \,J=|N| -- количество узлов. Множество ребер \,A описывает отношения типа спрос-снабжение или вход-выход в производственном процессе. Ребро из узла \,i в узел \,j обозначается \,(i,j)\in A и означает, что часть продукта типа \,i используется для производства продукта \,j (если существует несколько узлов \,i таких, что \,(i,j)\in A, это означает, что все они используются для производства \,j).

33Z1E.jpg

Граф системы древовидного типа является связным и не содержит циклов: не существует такой группы продуктов, которая производилась бы отдельно от остальных продуктов, и ни один не используется явно или неявно для производства самого себя. Узлы нумеруются таким образом, что \,i<j, если \,(i,j)\in A. Если \,(i,j)\in A, то \,i является (непосредственным) предшественником для \,j, а \,j является наследником для \,i. Введем следующие обозначения:

\,Pre(j) -- множество предшественников для \,j

\,Suc(i) -- множество наследников элемента \,i

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

В такой терминологии система сборочного типа имеет только один окончательный узел \,J и каждый узел \,i<j имеет единственного наследника. Здесь узел может иметь несколько предшественников (в отличие от систем последовательного типа). Системы распределительного типа, напротив, имеют единственную начальную вершину 1 и каждый узел \,j>1 имеет единственного предшественника. Один узел может иметь несколько наследников. Формальное определение системы древовидного типа требует дополнительных предположений и может рассматриваться (не принимая во внимание направление ребер), как неориентированный граф без циклов. При таком условии каждый объект может иметь несколько предшественников и наследников. Во всех случаях количество ребер равно \,|A|=|N|-1=J-1.

Стоимостные параметры \,k_{j} , \,h'_{j} и функция \,I'_{j} (t) имеют те же значения, что и в системе последовательного типа. Введем новое обозначение для интенсивности спроса узла \,j: \,\lambda '_{j} .

Только окончательная вершина может иметь положительную интенсивность спроса \,\lambda '_{j} >0.

Содержание

Время доставки

Каждое ребро \,(i,j) имеет соответствующее время поставки \,L'_{ij} . Пусть время поставки от внешнего источника до начальной вершины \,j обозначается \,L'_{j} . Все эти величины являются неотрицательными. Соответствующая система с нулевым временем поставки имеет такие же параметры, что и система древовидного типа, за исключением \,L'_{ij} и \,L'_{j} , которые принимают нулевые значения.

Рассмотрим узел \,j с несколькими предшественниками. Время поставки \,L'_{ij} может включать время на поставку, а также время, необходимое на сборку. Таким образом, в общем случае \,L'_{ij} зависит от \,i. Для производства партии в узле \,j к моменту \,t соответствующая поставка для узла \,i\in Pre(j) должна быть подготовлена к моменту \,t-L'_{ij} . Следовательно, момент размещения заказа в такой системе зависит от предшественников узла и для каждого из них определяется отдельно. При этом существенными показателями также становятся время отправки и время прибытия материалов: \,I'_{j} (t) зависит от всех поставок в узел \,j и поставок из узла \, j.

Эшелоны

Эшелон \,i состоит из узла \,i, наследников узла \,i и всех последующих наследников. Таким образом, эшелон \,i содержит \,i и все последующие узлы, которые напрямую или косвенно используют продукт, произведенный в узле \,i.

Запас в эшелоне \,i определяется как сумма запасов в каждом узле эшелона, интенсивность спроса в эшелоне \,i определяется как сумма всех локальных показателей интенсивности во всех узлах эшелона. Эти величины могут быть вычислены рекурсивно, начиная с последнего узла:

\,I_{i} (t)=I'_{i} (t)+\sum _{j\in Suc(i)}I_{j}  (t)

\,\lambda _{i} =\lambda _{i} ^{{'} } +\sum _{j\in Suc(i)}\lambda _{j}

Затраты на хранение в эшелоне имеют вид:

\,h_{j} =h_{j} ^{{'} } -\sum _{i\in Pre(j)}h_{i} ^{{'} }   .

В системах сборочного типа, например, эшелон \,i состоит из вершин, находящихся в пути от вершины \,i до \,J. При этом для всех \,j имеет место равенство: \,\lambda _{i} =\lambda _{J} =\lambda и, если \,j является единственным элементом множества \,Suc(i), то

\,I_{i} (t)=I'_{i} (t)+I_{j} (t)

Как и в системе с линейной структурой, суммарные затраты на хранение в эшелоне в момент времени \,t имеют вид:

\,\sum _{j}h'_{j} I'_{j} (t) =\sum _{j}h_{j} I_{j} (t) .

Задача нахождения оптимального размера запасов

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

Вложенная политика управления запасами -- это такая политика, в которой оформление заказа в узле \,i влечет за собой оформление заказа всеми наследниками этого узла, а, следовательно, -- в каждом узле эшелона. В системах с линейной и сборочной структурой вложенная политика оказывается доминирующей. В системах с древовидной структурой это свойство выполняется не всегда. В качестве примера рассмотрим систему со структурой, представленной на рисунке 1. Здесь узел 1 соответствует складу, который снабжает узлы 2 и 3. Предположим, что интенсивность спроса узлов 2 и 3 одинаковая, \,\lambda _{2} =\lambda _{3} , все \,h_{j} равны, \,k_{1} =k_{2} , \,k_{3} >k_{1} , \,k_{3} >k_{2} . Последние два неравенства приводят к тому, что заказы на узлах 2 и 3 буду проходить чаще, чем на узле 3, следовательно, политика управления запасами не является вложенной. Несмотря на это, в некоторых случаях применяется вложенная политика, поскольку ее применение значительно проще.

Рассмотрим политику управления запасами, учитывая предположение о стационарности интервалов между заказами и вложенности. Рассмотрим величину

\,g_{j} =h_{j} \lambda _{j} ,

\,U=(u_{1} ,...,u_{n} )

Тогда средние затраты в зависимости от продолжительности интервалов \,u_{j} принимают вид:

\,C(U)=\sum _{j}\left[\frac{k_{j} }{u_{j} } +\frac{1}{2} g_{j} u_{j} \right]

Задача поиска оптимальной политики управления запасами является задачей целочисленного линейного программирования следующего вида:

\,\min C(U)=\min \sum _{j}\left[\frac{k_{j} }{u_{j} } +\frac{1}{2} g_{j} u_{j} \right]

\,u_{i} =\xi _{ij} u_{j}

\,\xi _{ij} >0, \,\xi _{ij} -- целое,

\, (i,j)\in A .

References

  1. Zipkin P. (2000) Foundations of inventory management; The McGraw-Hill Companies, Inc.
Личные инструменты
Our Partners