pizhurin_a_a_pizhurin_a_a_modelirovanie_i_optimizaciya_proce

Среднее число занятых каналов, или среднее число заявок под об­ служиванием, равно к = \ / ji = р. Эта формула верна для любой СМО с неограниченной очередью. Среднее число заявок в очереди Ьоч и среднее число заявок в системе Lcопределяются по следующим формулам:

	(6.7)
4 = 4 ч+ р-	(6.8)

Формулы (6.3), (6.5) и здесь остаются в силе.

Возвращаясь к задаче о загрузке оператора, рассчитаем по этим формулам основные характеристики процесса сортирования деталей при наличии двух операторов. Имеем, следовательно, двухканальную СМО: п = 2. Подставив это значение в формулу (6.6), найдем вероятность того, что в системе - в очереди и на сортировании - нет ни одной детали. Полу­ чаем ро = 0,429. Иными словами, оба оператора будут простаивать почти 43 % рабочего времени. По формулам (6.7) и (6.8) рассчитаем среднее чис­ ло деталей в очереди и в системе: L04 = 0,152; Lc = 0,952, т. е. очередь почти ликвидирована. Воспользовавшись формулами (6.3) и (6.5), найдем сред­ нее время пребывания деталей: в системе Wc- 0,238 мин; в очереди W04 =

=0,038 мин.

6.3.Классификация систем массового обслуживания

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

Примером может служить обслуживание определенного числа станков ра- бочим-наладчиком.

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

6.4. Одноканальная СМО с отказами

Представление о методах теории массового обслуживания можно получить, если рассмотреть вывод основных формул, характеризующих работу простейшей одноканальной СМО с отказами. Основные характери­ стики такой СМО: абсолютная пропускная способность А - среднее чис­ ло заявок, которое система может обслужить за единицу времени, и от­ носительная пропускная способность q - отношение среднего числа зая­ вок, обслуженных системой за единицу времени, к среднему числу посту­ пивших за это время заявок. Как и ранее, поток заявок предполагается пуассоновским с интенсивностью X, а время обслуживания распределено по показательному закону, причем интенсивность потока обслуживания равна \л Единственный канал системы обслуживания может находиться в одном из двух состояний: So- свободен или S\ - занят. Если система нахо­ дилась в состоянии 5*0, то приходящая заявка переведет ее в состояние S\. И, наоборот, если СМО была занята, то покидающая ее обслуженная заяв­ ка переведет систему в состояние So (если одновременно на ее вход не по­ ступит новая заявка). Обозначим через p 0(f) и р х(t) вероятности того, что

в произвольный момент времени t система находилась в состоянии So и S\ соответственно. В сумме эти вероятности, очевидно, равны 1:

PoW + Pi(f)=1-

(6-9)

Придадим теперь величине t малое приращение At и найдем веро­ ятность p 0(t+At) того, что в момент (/+Д^) система свободна, т. е. будет

находиться в состоянии So. Это может произойти в результате реализации одного из двух вариантов:

1)система была занята обслуживанием в момент f, а за время At ус­ пела его завершить, т. е. перейти из состояния S\ в So;

2)система была в состоянии So в момент t, а за время At не пришла ни одна заявка.

Обозначим через p X0(At) вероятность того, что система за время At

перейдет в So, будучи в момент t в состоянии S\. Тогда вероятность первого варианта равна произведению вероятностей p x( t ) - /?10(Дг). Аналогично, ве­

роятность второго варианта равна произведению P o ( t ) [ 1- /?0i(A/)]. Здесь

p 01(Af) - вероятность того, что система, находившись в момент t в со­

стоянии So, перейдет за время At в состояние Si. Следовательно, 1 - /?01(А^)

- это вероятность противоположного события, состоящего в том, что сис­ тема не перейдет в Si из So за время At. По правилу сложения вероятностей находим искомую вероятность p 0(t+At), складывая вероятности обоих ва­ риантов:

Ро{t + д*) = Р\ (ОАо(Л')+ Ро{t) [l - Poi (А01

(6-10)

Можно показать, что вероятности p l0(At) и p 0l(At) приближенно равны:

p l0(А?)« jiA?; p 0l(At) « XAt. С учетом этих равенств выражение (6.10) лег­ ко привести к виду

	(6.П)
Заменим p x(t) его выражением (6.9) и	перейдем к пределу при
Дг-»0. Тогда в левой части уравнения (6.11)	окажется производная от

функции p Q(t):

Фо(0 = ц - ( ц + х)^0(4	(6.12)
dt

Это дифференциальное уравнение легко решается. Полагая, что в начальный момент времени t = 0 система свободна, примем в качестве на­ чальных условий /?0(0) = 1. В этом случае решение уравнения (6.12) имеет

вид
К+ |!		К+ |1	(613)
Для отыскания величины	р 0,	соответствующей установившемуся
режиму, перейдем в уравнении	(6.13) к пределу при / —> оо. Получим
р 0 = Ц.ДА. + |i). По определению,	р 0 -	это вероятность того, что в момент

времени t система свободна. Это то же самое, что вероятность того, что пришедшая в данный момент заявка будет обслужена. Следовательно, в установившемся режиме найденное значение р 0 - это отношение среднего числа обслуженных заявок к среднему числу поступивших заявок для мо­ мента t, т. е. величина р 0 равна относительной пропускной способности системы q\ q = ц/(А, + ц). Абсолютная пропускная способность системы

равна А = Xq - ^ji/(X + ji).

Найдем вероятность того, что заявка, пришедшая в момент t, не бу­ дет обслужена, т. е. вероятность отказа: р 0тк = 1- р о = 1 - Она равна, оче­

видно, отношению среднего числа необслуженных заявок к числу заявок, поступивших за единицу времени. При / - > оо /?отк = 1-ц/(А. + ц) =

=V(k+n)-

6.5.Задачи управления запасами в деревообработке

6.5.7. Проблемы управления запасами

Необходимость создания запасов является отличительной чертой любого производственного процесса. В роли запасов могут выступать раз­ личные ресурсы: пиловочное сырье на складах лесопильного цеха и гото­ вая пилопродукция; межоперационный запас заготовок для оборудования, работающего в составе технологической линии; комплекты запасных час­ тей и инструментов и т. д. Запасы, имеющиеся в системе, расходуются и время от времени возобновляются. На рис. 6.1, а приведен пример графика

Рис. 6.1. Различные стратегии пополнение запасов:

а - общий случай; б - периодическая стратегия; в - случай равномерного спроса

изменения объема р товаров на складе в зависимости от времени. В мо­ менты t\, t2, t3, /4 происходит возобновление запаса, а в промежутки време­ ни между ними - его расходование. Можно выделить два способа или, как говорят, две стратегии пополнения запасов:

1) периодическая стратегия (рис. 6.1, б): поставки осуществляются через равные промежутки времени Г, объем их при этом может быть раз­ личным;

2) стратегия с критическим уровнем: заявка на пополнение запаса подается при достижении некоторого минимального его уровня на складе Рмт, который еще позволяет избежать дефицита товаров. Этот уровень на­ зывается точкой заказа.

Предположим вначале, что промежуток времени между подачей за­ явки на пополнение запаса и получением товара пренебрежимо мал. Такие поставки называют мгновенными. Тогда заявку на пополнение запаса следует подать в тот момент, когда он будет исчерпан. Мгновенность по­ ставок позволит предотвратить дефицит. Следовательно, здесь р тin= 0.

Пусть теперь поставка товара осуществляется с задержкой, и про­ межуток времени между подачей заявки и получением товара равен т. Если мы в этом случае, пользуясь стратегией с критическим уровнем, хотим из­ бежать дефицита, то заявку на пополнение запаса следует подавать рань­ ше, чем он будет исчерпан, т. е. при уровне p min > 0. Предположим, что за единицу времени со склада потребляется одинаковое количество товара М9 и, следовательно, его расходование описывается линейной функцией вре­ мени (рис. 6.1, в). Такой характер спроса называется равномерным. Оче­ видно, ЧТО при ЭТИХ условияхр т\п= М Т .

Управление запасами связано с тремя видами издержек:

1)издержки хранения состоят из затрат на размещение, физическое хранение запасов, а также затрат на замороженные в них фонды. Обычно эти издержки считают пропорциональными среднему уровню запасов;

2)издержки пополнения - это расходы, связанные с осуществлени­ ем заказа на новые товары;

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

Как видно, изменение уровня имеющихся запасов по-разному влия­ ет на те или иные виды издержек. Например, увеличение объема товаров на складе позволяет избежать издержек дефицита, но одновременно при­ водит к увеличению стоимости их хранения. Если процессом поступления товаров на склад можно управлять, то возникает оптимизационная задача управления запасами: определить количество приобретаемого или изго­ тавливаемого товара, подлежащего хранению, а также частоту или сроки его поступления, при которых издержки всех трех видов в сумме будут минимальными.

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

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

6.5.2. Оптимальный объем партии

Рассмотрим систему управления запасами с периодической страте­ гией поставок и равномерным спросом. Пусть товар поставляют на склад партиями по п единиц в каждой. Продолжительность функционирования системы равна т. За это время должно быть поставлено N единиц товара. Количество партий составляет, следовательно, m = N /n , а период между

поставками равен Т = х/т . Предположим далее, что поставки мгновенные, в системе не допускается дефицит (рис. 6.2) и затраты на хранение про­ порциональны количеству товаров на складе и времени их хранения. За­ данными величинами являются: длительность работы системы х, общий объем поставок N; затраты сх на хранение единицы товара в течение еди­ ницы времени; плата с2 за заказ одной партии продукта, не зависящая от объема партии. Требуется определить оптимальный размер партии товара, то есть значение п, при котором суммарные затраты на хранение и возоб­ новление запасов минимальны.

Выделим на рис. 6.2 отрезки, соответствующие времени хранения 1-й, 2-й,..., z-й единицы товара из числа поступивших на склад в составе первой партии. Теперь легко заметить, что суммарное время хранения всех

Рис. 6.2. Стратегия, рассматриваемая при выводе формулы для оптимального объема партии

«единиц товара одной партии равно площади треугольника ОАВ, т. е.

«Г/2. Следовательно, суммарные затраты на их хранение равны с,«Г/2.

Величина затрат на хранение всех т партий составит поэтому с^птТ/2. Добавив к ней плату за заказ партий, равную с2т, получим следующее вы­ ражение для общих затрат:

с = с{птТ/2 + с2т.	(6.14)
Подставив в первое слагаемое вместо тТ величину т, а во второе
вместо m - его выражение, m = N /n , перепишем формулу (6.14)	в виде

с = Cj«t/2 + c2N /n.

Для отыскания оптимального размера партии возьмем производную от этого выражения по « и приравняем ее нулю:

dc/dn - Cj т/2 - c2N / «2 = 0.

В результате получим уравнение с1«2т = 2с2Лг, решив которое най­ дем искомое значение для «:

« — «опт — ^ 2 c2N / CjT.

Взяв вторую производную от с по «, нетрудно убедиться, что она положительна, и, следовательно, полученное значение действительно соответствует абсолютному минимуму суммарных затрат. Обозначим N/x = М Величина М - это объем спроса за единицу времени. Тогда по­ следнее выражение можно переписать так:

nom = j2 ^ M ] 7 v

(6.15)

Формулу (6.15) называют формулой Уилсона. Она наглядно иллю­ стрирует противоположный характер влияния затрат на хранение и затрат, связанных с возобновлением запасов, на оптимальный размер партии. Уве­ личение затрат первого вида требует уменьшения объема партии, а затрат второго вида - его увеличения.

Теперь легко определяется и оптимальное значение периода между поставками:

7-опт = x/ mo = * nm /N = д/2с2/с| М .

(6.16)

Пример. В сборочный цех деревообрабатывающего комбината в течение меся­ ца (т = 30 дней) поступают 3 ООО заготовок. Принято, что соотношение между затрата­ ми с1 на хранение одной заготовки в течение дня и расходами С2 на доставку в цех од­

ной партии заготовок составляет примерно сх/с 2 «1/500. Найдем оптимальный размер

партии. Предварительно	определим М = N /z = 3000/30 = 100. По	формуле (6.15)
п0ТП= л/2 *500 -100 «317.	Оптимальный период между поставками	отыскивается по

формуле (6.16): 70пт = ^/2 • 500/100 « 3,17, то есть составляет несколько больше 3 дней.

218

6.5.5. Управление запасами и планирование производства

Пусть теперь вопрос об управлении запасами решается совместно с составлением производственной программы. Предположим, что производ­ ственная деятельность предприятия (отдельного цеха) рассматривается в течение планового периода, состоящего из т отрезков (например, в тече­ ние 12 мес). Для каждого из них имеется точный прогноз спроса на выпус­ каемую продукцию, равный dxдля /-го отрезка времени. Требуется опре­ делить объем Xi выпуска продукции в каждый промежуток времени, / = 1, 2,..., т. При этом предполагается, что спрос dt можно удовлетворить в конце /-го промежутка, используя полностью или частично продукцию, из­ готовленную за это время. На экономические показатели производствен­ ной деятельности влияют как величины объемов производства, так и уро­ вень запасов, поэтому в некоторые промежутки времени может оказаться выгодным производство продукции в объеме, несколько превышающем спрос в этот период, с тем, чтобы хранить излишки для удовлетворения будущего спроса.

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

с,=Л(*,.гД

(6Л7)

Тем самым предполагается, что функции f могут быть различными для разных промежутков времени. Эти функции называют функциями за­

трат.

Построим оптимизационную модель данной задачи. Ее целевая функция запишется в виде

тт

^ = Z c;= X /(* .> z/)-»m in.		(6.18)
1= 1	1= 1

Ограничения задачи:

1) к концу последнего т-го отрезка времени уровень запасов дол­ жен быть нулевым:

zm=0;

(6.19)

2) переменные х, неотрицательны и ограничены сверху некоторым значением R:

О<x( <R, / = 1, 2,..., т\

(6.20)

3) балансовое условие: запасы к концу г-го промежутка времени равны их уровню на конец предыдущего (/ - 1)-го отрезка плюс объем вы­

пуска Xj минус спрос di:

(6.21)

при этом уровень запасов z0 к началу планового периода предполагается заданным;

4) в пределах каждого отрезка времени должно быть обеспечено полное и своевременное удовлетворение спроса. С учетом выражения (6.21), для выполнения этого ограничения достаточно потребовать неотри­ цательности переменных z{.

Zj > 0 , / =	1, 2 ,...,	т .	(6.22)
Таким образом, поставленная	задача	сведена к модели	(6.18) -

- (6.22). Если дополнительно предположить, что каждая из переменных х{ принимает лишь дискретные значения, то для ее решения пригоден метод динамического программирования (см. гл. 5). Процесс естественным обра­ зом разбивается на т этапов, соответствующих отдельным промежуткам времени планового периода. По (6.18) целевая функция аддитивна. Пере­ менная Xi является управлением, а переменная z, - координатой состояния на z-м шаге, причем заданы начальное и конечное состояния - соответст­ венно z0 и zm. Соотношение (6.21) определяет переход системы из очеред­ ного состояния в следующее.

Если сделать дополнительное предположение о линейности функ­ ций (6.17):

(6.23)

где cii и bi - некоторые положительные постоянные, то задача (6.18) - (6.22) сводится к задаче линейного программирования. Элементами решения ее будут только переменные xh поскольку величины z, можно выразить через них с помощью соотношения (6.21). В самом деле, перепишем его пооче­ редно для / = 1, 2,...:

Zj —Zq + хх dx,

z2 = Zj + x2 - d2;

Сложив левые и правые части всех этих i равенств, после упроще­ ний получим

(6.24)

j=l -

Рассмотрим наиболее простой частный случай этой задачи.

Пример: Допустим, что спрос dh объемы производства х, и линейные функции затрат (6.23) одинаковы для любого промежутка времени, то есть

	d. = d > 0; х. = х; с. = ах + bzt,
где г, примет вид
	Zj = z0 + i (х - d ) .	(6.25)
Имеем, следовательно, экстремальную задачу с единственной переменной х. Ее
целевая функция
W =	= amx + bY,zi = amx + bmz0 + b{x - tf)(l + 2 + ... + m).
/=1	t=i
Воспользовавшись формулой для суммы членов арифметической прогрессии,
получим
	W = т [ах + bz0 + Ъ(х - d )(1 + т)/2] -> min.	(6.26)
Ограничения задачи: х >0, а также неравенства (6.22), которые, с учетом (6.25),
запишутся так:
	zQ+ i(x - d )> 0, /' = 1, 2,..., т.	(6.27)

При этом последнее из них должно обратиться в равенство [см. (6.19)]. Коэф­ фициенты а и b в уравнении (6.26) положительны, поэтому целевая функция является возрастающей. Поскольку она линейна, то минимум ее будет достигаться при наи­ меньшем допустимом значении х.

Рассмотрим сначала простейший случай z0= 0. Для него из уравнения (6.27)

сразу получаем оптимальное решение: хопT= d, то есть в каждый отрезок времени долж­ но быть выпущено ровно столько продукции, сколько потребляется в конце промежут­ ка времени. Составляющая целевой функции, связанная с затратами на хранение, в этом случае равна нулю, и Wom = mad. Пусть теперь zq > 0. Естественно полагать при этом, что минимальный запас не превосходит суммарного спроса за весь плановый пе­ риод, то есть

z0 < md. .t (6.28)

Тогда, очевидно, х0[ГТ< d, следовательно, второе слагаемое в каждом из ограни­ чений (6.27) отрицательно. Для выполнения всех этих ограничений поэтому достаточно потребовать выполнения последнего из них, где второе слагаемое наибольшее по абсо­ лютной величине: z0 + m{x - d)> 0. С учетом (6.19) его следует сразу записать в виде

равенства: z0 + m(x - d ) = 0 , откуда

x o n v = d ~ z o / m -

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

Рассмотренные выше задачи управления запасами являются про­ стейшими. Все они относятся к детерминированным системам, в которых уровень спроса предполагается заданным однозначно. Более реальным бы-