РАСПРЕДЕЛЕНИЕ ОБОРУДОВАНИЯ В КОНВЕЙЕРНЫХ СИСТЕМАХ ОБРАБОТКИ ЗАЯВОК ПО КРИТЕРИЮ МАКСИМАЛЬНОЙ ПРОИЗВОДИТЕЛЬНОСТИ

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

При известной интенсивности входных потоков на заданный директивный период с первого дня по день с номером Т необходимо обеспечить обработку m типов заявок в объеме не менее соответствующего координате вектора b = (bp ..., Ьт), минимизируя к концу периода планирования общий объем необработанных заявок по всем видам. Обработка заявок вида / состоит в последовательном обслуживании заявок этого вида на Ж. операциях производственного цикла (/ = 1, т). Очереди заявок на каждой операции в начале

периода обработки задаются величинами 1С(0). Поступление заявок производится ежедневно в объеме ut, где — объем поступления заявок вида i на операцию j в день q (q = 1,Т) обработки заявок. Все операции обработки выполняются Ж приборами, специализация которых по операциям обработки задана величинами ai, где а. — производительность /-го прибора на операции 0~.

В этих условиях задача минимизации объемов очередей заявок к концу директивного периода длительностью Тдней при условии выполнения плановых ограничений обработки заявок, заданных вектором b = (bj, ..., bm), эквивалентна задаче максимизации общего объема обработанных заявок и может быть сформулирована следующим образом:

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

(для любого Ое 0; для любогор = 1,..., 7);

(xfj! > 0; для любых 0{.е 0).

Здесь 0 — совокупность всех операций; х?! — часть <7-го дня, в течение которого прибор / выполняет операцию О.j; R.j — множество операций-предшественников для операции Оф у^ — коэффициент ветвления для операций из множества R~ (i = 1, ..., m), обработка заявок которых происходит в день q на приборе /. Коэффициент задает долю объема заявок, обработанных на операции множества R~, которая поступит на операцию 0~.

Сформулированная задача распределения ресурсов является задачей линейного программирования (ЛП). Решение этой задачи может быть осуществлено с использованием соответствующих программных средств.

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

где с. — прибыль, получаемая при обработке единицы объема заявок вида/ (/= 1,..., т).

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

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

Утверждение 5.1. Пусть есть оптимальное распределение ресурсов

на один день и — объем обработанных заявок на

каждой операции СЕ за первый день. Если известно, что интенсивность поступления заявок в последующие Р- 1 день таковы, что выполняется система неравенств:

то решение задачи распределения ресурсов на один день может быть перенесено на все последующие дни, если объемы обработки заявок по каждому виду w.(i= 1,..., т) для решения на период в один день таковы, что выполняется следующее неравенство:

Доказательство утверждения 5.1 следует из того факта, что предлагаемое решение задачи (5.13)—(5.16) является оптимальным для ситуации, когда вектор b = (0,..., 0).

Учитывая неравенство (5.17), получим, что условия (5.15) также выполнены для заданного вектора , что и доказывает

сформулированное утверждение.

Проектировщика системы обработки заявок нередко интересует, в каком диапазоне могут меняться интенсивности поступления заявок производительности приборов, специализация приборов по операциям так, чтобы при изменении перечисленных параметров значение функционала задачи (5.13)—(5.16) не менялось.

Подобный анализ задачи и полученного решения носит название исследования задачи на устойчивость.

Введем следующие определения.

Определение 5.1. Назовем задачу (5.13)—(5.16) устойчивой по специализации приборов, если существует такое 8 > 0, что при увеличении всех нулевых элементов матрицы (ар на величину не более чем 8 > 0 значение функционала (5.13) в решении задачи (5.13)—(5.16) остается неизменным.

Определение 5.2. Задача (5.13)—(5.16) устойчива по интенсивности поступающего потока заявок, если существует такое 8 > 0, что при увеличении потока заявок ui на величину не более чем 8 значение функционала (5.13) задачи (5.13)—(5.16) остается неизменным.

Определение 5.3. Задача (5.13)—(5.16) устойчива по производительности приборов, если существует такое 8 > 0, что при увеличении всех ненулевых элементов матрицы (ар на величину не более чем 8, значение функционала (5.13) при решении задачи (5.13)—(5.16) сохраняется.

Определение 5.4. Задача (5.13)—(5.16) устойчива по числу приборов, участвующих в обработке поступающего потока заявок, если существует такое 8 > 0, что при увеличении числа приборов на один с производительностями прибора по всем видам операций не более 8 значение функционала (5.13) в решении задачи (5.13)—(5.16) не меняется.

Определение 5.5. Задача (5.13)—(5.16) устойчива по плановым ограничениям, заданным вектором b = (bv ..., bm), если существует такое 8 > 0, что при увеличении координат вектора b на величину не более чем е значение функционала (5.13) не изменяется.

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

Утверждение 5.2. Задача (5.13)—(5.16) устойчива по специализации приборов и по интенсивности потоков заявок, если выполняются следующие соотношения:

где Т* — число дней в директивном периоде планирования;

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

Устойчивость по специализации приборов вытекает из того, что по условию а) увеличение производительности приборов произойдет только на операциях, отличных от операций (/ = 1, ..., т). Из условий б) и в) следует, что загрузка приборов в оптимальном решении будет только на операциях OiN.

Утверждение 5.3. Задача (5.13)—(5.16) устойчива по производительности приборов и по их числу, если для каждой операции обработки выполняются следующие условия:

где Т — день окончания планового периода.

Доказательство. Доказательство утверждения 5.3 следует из того факта, что весь объем поступивших заявок на обработку в систему полностью обработан, поэтому наращивание производительности участвующих в обработке приборов не может увеличить значения функционала (5.13) задачи (5.13)—(5.16).

Утверждение 5.4. Задача (5.13)—(5.16) устойчива по плановым ограничениям тогда и только тогда, когда выполняется следующая система неравенств:

Доказательство. Достаточность условия (5.18) вытекает из того, что при увеличении координат вектора b значение функционала

(5.13) в оптимальном решении может только уменьшиться, поэтому, взяв в качестве е величину, равную

получим по определению устойчивость задачи (5.13)—(5.16) при изменении плановых ограничений.

Необходимость условия (5.18) для устойчивости задачи (5.13)— (5.16) непосредственно вытекает из определения устойчивости по плановым ограничениям.

При анализе решений задачи (5.13)—(5.16) нередко необходимо не только выяснить, устойчива ли задача (5.13)—(5.16) по исходным параметрам, перечисленным в определениях 5.1—5.5, но и в случае, если задача устойчива, вычислить максимальное увеличение (уменьшение) входного параметра, при котором значение функционала

(5.13) сохраняется.

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

где х'91 — доля времени работы прибора / на операции 0{. в день q в решении (5.13)—(5.16) при интенсивностях поступления заявок и| + е; х?! — доля времени работы прибора / на операции 0~ в день q при прежних интенсивностях поступления заявок м|.(/= 1, ..., m,j= 1, ...,N-q= 1,..., Т).

Задача вычисления максимального приращения производительности приборов, при котором сохраняется значение функционала задачи оптимального распределения ресурсов (5.13)—(5.16), формулируется так:

где решение x-f — решение задачи (5.13)—(5.16) при производительности приборов — решение задачи (5.13)—(5.16) при производительности приборов а?..

Кроме критерия минимизации объема необработанных заявок к концу директивного периода показателем эффективности работы системы может быть необработанный объем заявок, время ожидания которых в системе превышает заданное время т

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

Перечисленные факторы обосновывают распределение ресурсов в системе обработки по выбранному критерию.

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

Интенсивность поступления заявок на операцию i в день j со временем ожидания не менее Q дней задается величиной «Гр (/= 1,..., N; j= 1, ..., Т; Q= 1, ..., т), где х — максимальное число дней, которое заявка может находиться в системе обработки.

Очереди заявок на операциях на начало директивного периода задаются величинами V9 (объем очереди на операции / со временем ожидания не менее Q дней).

Выполнение обработки заявок на всех операциях осуществляется N приборами, производительность которых на операциях задается элементами матрицы а .

Здесь а — дневная производительность на операции q прибора р.

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

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

где uj — объем заявок, поступающий на операцию i в день j.

Объемы очередей на начало директивного периода рассчитываются по формуле

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

Сформулированная задача при введенных обозначениях сведена к задаче распределения ресурсов по критерию максимизации объема обработанных заявок за директивный период, рассмотренной ранее при условии, что вектор плановых ограничений b = (0,..., 0).

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

 
Посмотреть оригинал
< Пред   СОДЕРЖАНИЕ   ОРИГИНАЛ     След >