Меню
Главная
Авторизация/Регистрация
 
Главная arrow Логистика arrow Методы управления ограниченными ресурсами в логистике

ДИНАМИЧЕСКИЕ МОДЕЛИ УПРАВЛЕНИЯ ОГРАНИЧЕННЫМИ РЕСУРСАМИ В ПРОМЫШЛЕННОЙ ЛОГИСТИКЕ

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

ОПТИМАЛЬНОЕ РАСПРЕДЕЛЕНИЕ ОГРАНИЧЕННЫХ РЕСУРСОВ НА ЗАДАННОМ ПЕРИОДЕ ПЛАНИРОВАНИЯ

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

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

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

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

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

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

Рассмотрим основные уравнения, описывающие функционирование конвейерных систем.

Технологическая схема обработки заявок в конвейерной системе может быть представлена в виде орграфа G(M, TV), в котором вершины имитируют операции обработки, а дуги задают технологическую последовательность обработки заявок на операциях. Обозначим через V(t, т) вектор-функцию компонента /, который представляет очередь заявок, имеющих время ожидания в системе не более чем т (т > 0). Введем также векторы-функции U(t, т) и Q(t, т) так, что ?/.(/, т) задает интенсивность поступления заявок с временем ожидания в системе не более т на операцию i в момент времени /. Аналогично определяется интенсивность обработки заявок QiJ, т) на операции /.

Будем полагать, что U(t, т) содержит в качестве аддитивной компоненты вектор-функцию UQ(t, т) внешних поступлений, по предположению имеющих нулевой возраст:

где /(т) — функция скачка, заданная следующим образом:

Для очереди VfJ, т) операции i уравнение баланса имеет вид

Его можно получить, учитывая, что приращение V.(t + At, т) - - V.(t, т) очереди за время dt складывается из разности (?/.(/, т) - Qj(t, т)) и объема заявок, выбывших из очереди вследствие старения. За время Побьем выбывших заявок составит

Интенсивность поступления заявок U(t, т) определим следующим образом:

где матрица D{t) такова, что величина dy(t)Qj(t, т) задает интенсивность заявок, передаваемых с элемента / на элемент j; d^t) — элементы матрицы D(t).

Уравнение (5.2) задает поступление заявок для системы обработки однородных заявок. Если же обрабатываются заявки нескольких видов, то для заявок К видов зададим межэлементные связи в технологическом графе G(M, TV), отражающем последовательность обработки заявок на операциях трехмерным матричным оператором D(t), действующим на матрицу Q(t, т):

Здесь — элементы соответствующих

матриц (/ = 1, ..., TVp j= 1, ..., К), где TV;. — число операций в цикле обработки заявок вида /; dUj{t) — элемент матрицы D(t) (/ = 1, ..., TV., j = 1,..., Nr 1= 1,..., К), при этом элемент d^fiQ-p, т) задает интенсивность заявок, передаваемых элементом i на элемент j для вида заявок /.

Динамика изменения очередей заявок на операциях без учета времени ожидания задается следующим соотношением:

Здесь Vft) — вектор-функция очередей на операциях /-го типа заявок; Dj матричный оператор межэлементных связей; (?.(/) — вектор производительностей на операциях по /-му виду заявок; ?/9.(/, т) — вектор внешних поступлений; Е — единичная матрица.

Производительности, с которыми происходит обработка заявок Q^t), на технологических операциях обеспечиваются при помощи ресурсов в системе обработки, заданных вектором С= (Ср ..., Ст). Для того чтобы обеспечить на операции / производительность обработки Qjj(f), необходимо выделить на этой операции ресурсы в количестве

где — m-мерный вектор трудозатрат на операции j

по виду заявок /.

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

Рассмотрим задачу оптимального распределения ресурсов по критерию максимизации суммарного объема обработанных заявок за директивный период в следующей постановке.

Необходимо максимизировать функционал

где при ограничениях:

Здесь Nj номер последней операции по /-му типу заявок; /Г. — множество операций предшественников для у'-й операции по виду заявок /'; интервал (О, Т) задает длительность периода планирования; b = (bv ..., b ) — вектор, задающий плановый объем заявок, который необходимо обработать к концу директивного периода.

Рассмотримчастный случай задачи (5.3)—(5.6) при условии, что

Граф, задающий последовательность обработки заявок, является цепью.

Приводимый ниже алгоритм распределения ресурсов максимизирует функционал (5.3) при ограничениях (5.4)—(5.6) для любого интервала [0, /] е [О, Т].

Описание алгоритма.

Шаг 0. Полагаем

Шаг 1. На все операции, начиная с операции /, ресурсы выделяются в количестве

Будем считать, что ресурсы не выделяются на операции 1,1. Производительности на операциях для всех

задаются следующим образом:

Здесь

Шаг 2. Изменяем значение i по формуле / = / + 1. Если i < 1, то выход из алгоритма, в противном случае перейти к шагу 1.

Докажем, что алгоритм оптимально распределяет ресурсы по критерию максимального объема обработки заявок за любой период

Обозначим

Предположим, что существует распределение ресурсов, обеспечивающее производительности qn{t),..., qN (t)> для которых выполняются ограничения (5.4) и существует такой момент времени f е [О, Т], что

где Vl.(f) — величина очереди на операции / (/ = 1,..., Nx) в момент времени /*, если ресурсы распределены согласно приведенному алгоритму; Vu(t ) — величина очереди среди заявок на операции i (i = 1, ..., TVj), если производительности на операциях заданы функциями qu(t),...,qw(t).

Не уменьшая общности, можно считать

В силу соотношения (5.7) имеем

В свою очередь,

Тогда объем заявок, обработанный к моменту времени t* при производительностях qn(t),..., qlN (/), может быть представлен так:

Оценим время обработки /обр этого объема заявок при выполнении ограничений (5.4):

где / > к.

Неравенство (5.9) противоречит тому, что к моменту времени t* может быть обработан объем заявок, заданный правой частью равенства (5.8), что означает оптимальность приведенного алгоритма.

Рассмотрим алгоритм распределения ресурсов при обработке одного вида заявок, если на операции обработки поступает поток заявок заданной интенсивности.

Пусть система обработки заявок состоит из N{ последовательных операций. На каждую операцию поступает поток заявок, интенсивность которого задана интегрируемыми функциями Uy{t) (/ = 1, ..., N{). Обработка заявок, поступающих на операцию /, заключается в последовательной обработке заявок на операции /, /+ 1,..., Nv после чего обработка заявок считается завершенной.

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

Необходимо распределить ресурсы так, чтобы объем обработанных заявок был бы максимален для любого интервала (0, 0 ? с= (О, Т).

Объем очереди на операции i определяется для каждого момента /е (О, Т) из следующего соотношения:

где q{ м(0 — производительность обработки заявок на / - 1 в момент времени t.

Рассмотрим следующий алгоритм распределения ресурсов по указанному выше критерию.

Шаг 0. Положим

Шаг 1.Вычислить такое е/+1, что для всех t е (е;, е/+1) выражение сохраняет знак.

Если fft) > 0, то для всех t е (е7, ?/+1) производительность на операции определяется по формуле

а на операциях j = i + 1,..., Nx по формуле

где ?/+| — такое минимальное число из интервала (0, Т), что для него выполняется соотношение

Если е/+1 > Т, то переход к шагу ВЫХ.

Если е/+1 < Т, то переход к шагу 3.

Если fft) < 0, то для всех t е е, ее+1).

Шаг 2. Вычисление АС;(0-

Положить i = i - 1. Если i < 1, то перейти к шагу 3, иначе — переход к шагу 1.

Шаг 3. На интервале (ге, ?е+1) распределение ресурсов завершено. Производительности qn(t),...,qlN (t) задаются следующим образом: qy = 0;j=l,2,1;

Если ?е+1 > Т, то переход к шагу ВЫХ, иначе положить 1=1 + 1; / = ТУр ACNi+l = С. Перейти к шагу 1.

Шаг ВЫХ. Распределение ресурсов на интервале (О, Т) завершено. Работа алгоритма закончена.

Покажем, что алгоритм распределяет ресурсы по критерию максимальной производительности системы для любого интервала (О, t) с (О, Т). Не уменьшая общности, проведем доказательство для интервала (0, t) <= (0, ?,).

Если, для всех t е (0, ?j) и в этом

случае алгоритм оптимален на отрезке (О, Т). Проведем доказательство для случая, когда существует такое К (1 < К < jV,), что fft) < 0 для / = К+ 1,..., Nx иfft) > 0 для / = 1,..., К. Предположим, что существуют для которых t* е (0, ?,), и выполняется

неравенство

Здесь Vu(t) и VXj(t*) — очереди для операции i в предположении, что производительности на операциях заданы соответственно функциями %(t) и qu{t), которые были построены в результате работы алгоритма (/ = 1,..., N^. Из неравенства (5.10) следует, что

Из предположения о существовании К получим

Учитывая неравенство (5.11), получим

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

Последнее неравенство противоречит тому, что возможно существование производительностей, которые обрабатывают объем заявок, заданный левой частью неравенства (5.11), что и доказывает оптимальность приведенного выше алгоритма.

Рассмотрим алгоритм решения задачи (5.3)—(5.6) для случая обработки К видов заявок, если ориентированный граф G(M, N), задающий технологический маршрут обработки заявок, состоит из К параллельных цепей, каждая из которых задает последовательность обработки для заданного вида заявок.

Ниже приводится описание алгоритма оптимального распределения ресурсов в предположении, что Ь; = 0 (/ = 1, ..., К); u;;(t) = О (/ = 1,..., K;j= 1,..., N); существует

Описание алгоритма.

Шаг 0. Положить т = 0.

Шаг 1. Решаем задачу линейного программирования следующего вида:

где S* — множество путей, соединяющих операции, на которых существуют очереди заявок, с конечными операциями обработки по данному виду заявок; С= (Ср ..., Ст) — вектор ресурсов, участвующих в обработке; Р — множество видов заявок, среди операций которых существует хотя бы одна с ненулевой очередью; S* — множество путей, отражающих последовательность обработки заявок вида /, на начальной операции которых есть ненулевая очередь; множество операций, входящих в путь /'.

Шаг 2. Вычисляем значение выражения

где qa — производительность обработки заявок на пути, соединяющем операцию 0{. с конечной операцией OiN .

Если d = Т- т, то распределение ресурсов на интервале [О, Т] закончено, выход из алгоритма, иначе пересчитаем длины очередей на операциях с ненулевыми очередями по формуле

Если существует К» > 0, то переход к шагу 1, иначе — выход из алгоритма.

Приведенная процедура разбивает интервал планирования обработки заявок на отрезки (0, tx), [tv t2),..., [tn_vT), каждый из которых характеризуется одним и тем же множеством операций, на которых существуют неотрицательные очереди необработанных заявок. Правая граница каждого отрезка соответствует моменту завершения обработки очереди на одной из операций.

Докажем следующую теорему.

Теорема 5.1. Приведенный выше алгоритм распределения ресурсов максимизирует общий объем обработанных заявок на временном интервале (0, t) для любого t е (О, Т).

Доказательство. Предположим, что существуют производительности qiN (t) (/= 1,..., К) на конечных операциях обработки и существует t* & (О, Т], такое, что

Очевидно, что t* ё (0, /j), так как на интервале (0, /j) алгоритм задает максимально возможную производительность обработки при заданном распределении заявок по операциям.

Предположим, что е (tx, //+1).

Производительности qiN (t), построенные в алгоритме, очевидно, удовлетворяют соотношению:

Обозначим

Тогдасуществует множество таких отрезков, что для отрезков выполняется следующее:

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

(5.12), получим, что

что противоречит первоначальному предположению и, следовательно, доказывает утверждение теоремы 1.

 
Посмотреть оригинал
Если Вы заметили ошибку в тексте выделите слово и нажмите Shift + Enter
< Пред   СОДЕРЖАНИЕ ОРИГИНАЛ   След >
 

Популярные страницы