Составление «скользящих» графиков .

Поволжский Государственный Университет Телекоммуникаций и Информатики

Факультет Информационных систем и технологий

Кафедра: «Информационные системы и технологии»

 

Лабораторная работа №4

«Задачи дисбаланса. Составление «скользящих» графиков»

 

 

Выполнила:

Студентка 3 курса

Группы ИСТ-72

Краснова Татьяна

Проверила: Захарова О.И.

 

Самара

2019

Задачи дисбаланса

Минимизация дисбаланса при сборке изделий из комплектующих.

Изделия двух типов (А и В) собираются с использованием комплектующих 4-х видов (1, 2, 3 и 4). Структура изделий определена в таблице (изделие типа А состоит из 3-х комплектующих 1-ого типа, 10-ти комплектующих 2-ого типа и т.д.).

 

Тип	Вид комплектующих
изделия	1	2	3	4
А	3	10	7	1
В	0	8	5	4

 

Комплектующие выпускаются на двух различных заводах. В следующей таблице приведены данные, характеризующие производительность заводов по выпуску комплектующих и недельный ресурс времени, которым располагает каждый из заводов для их производства. Цена изделий вида А - $40, вида В - $27.

Завод	Недельный фонд времени (час)	Производительность по видам комплектующих (ед/час)
		1	2	3	4
1	130	10	5	7	8
2	90	8	6	12	3

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

Определим варьируемые переменные Xij как еженедельные затраты времени (в час) для производства комплектующих i-ого вида на j-ом заводе (i=1, 2, 3, 4; j=1, 2). Тогда суммарное количество комплектующих, выпускаемых 2-мя заводами (по видам комплектующих), определится выражениями:

N1=10*X11+8*X12; (комплектующие 1-ого вида)

N2=5*X21+6*X22; (комплектующие 2-ого вида)

N3=7*X31+12*X32; (комплектующие 3-его вида)

N4=8*X41+3*X42 (комплектующие 4-ого вида).

Введемдополнительные варьируемые переменные “второго уровня” Nia - количество комплектующих i-ого вида, используемых для сборки изделия А, аналогично Nib (Nia + Nib = Ni; i=2, 3, 4).

При решении этой задачи целесообразно использовать понятие полного комплекта - набора комплектующих, из которых может быть собрано одно изделие. Так для изделия А полным комплектом является набор (3,10, 7, 1), а для изделия В - (0, 8, 5, 4). Любой комплект составляется из порций комплектующих разных видов. Для изделия А это 4 порции:

1. из трех комплектующих 1-ого вида;

2. десяти 2-ого вида;

3. семи 3-его вида;

4. одной комплектующей 4-ого вида.

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

Например, все комплектующие 1-ого вида используются для сборки изделий А. Какое количество изделий типа А можно собрать из комплектующих 1-ого вида? Очевидно это количество определяется тем, сколько порций можно собрать из комплектующих 1-ого вида, т.е. величиной [N1/3] (квадратные скобки определяют здесь целую часть частного).

Комплектующие 2-ого вида делятся на две части, одна из них идет на сборку изделий типа А, вторая – на сборку изделий типа B, при этом N2а+N2b=N2. Величина [N2а/10] определит количество порций, и соответственно количество изделий типа А, которые можно собрать с учетом объема имеющихся комплектующих 2-ого вида -N2a.

Таким образом, общее количество изделий типа А, которое может быть собрано при наличии комплектующих 1¸4 –ого видов в количестве (N1, N2a, N3a, N4a), определится формулой:

Кол-во_Изделий_А = MIN ([N1/3], [N2a/10], [N3a/7], [N4a]);

Аналогично для изделий типа B:

Кол-во_Изделий_В = MIN ([N2b/8], [N3b/5], [N4b/4]).

Содержимое целевой ячейки: Z = 40*Кол-во_Изделий_А +27*Кол-во_Изделий_В.

Ограничения: по времени производства

для завода 1:    X11 + X21 + X31 + X41 <= 130;

для завода 2:    X12 + X22 + X32 +X42 <= 90.

по видам комплектующих: Nia + Nib = Ni; i=2, 3, 4; Nia, Nib = целые.

Максимизировать Z.

Таким образом в этой задаче, общее число варьируемых переменных (изменяемых ячеек) равно 14. Из них 8 переменных Xij имеют размерность времени, а 6 переменных (Nia, Nib) - безразмерны.

Решение:

Изменяемые ячейки 1-ого уровня: F4:I5.

Изменяемые ячейки 2-ого уровня: G12:I13.

Целевая ячейка: J19.

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

· по времени производства J4:J5<=J7:J8.

· по видам комплектующих: G14:I14 = G9:I9.

· G12:I13 = целые.

Изменяемые ячейки 1-ого уровня: F4:I5.

Изменяемые ячейки 2-ого уровня: G12:I13.

Целевая ячейка: J19.

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

· по времени производства J4:J5<=J7:J8.

· по видам комплектующих: G14:I14 = G9:I9.

· G12:I13 = целые.

Модель производства с запасами

Фирма переводит свой завод на производство новых изделий, которые планируется выпускать в течение 4-х месяцев. Оценки спроса на изделия в каждый из этих месяцев приведены в таблице:

 

Месяц поставки изделия	1	2	3	4
Спрос (штук)	100	200	180	300

 

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

¨ избытка изделий, произведенных в предшествующие месяцы;

¨ изделий, произведенных в текущем месяце;

¨ изделий, произведенных в последующие месяцы для погашения

невыполненных ранее заказов.

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

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

 

Месяц производства изделия	1	2	3	4
Выпуск (штук)	50	180	280	270

 

Требуется уточнить (доопределить) эту программу таким образом, чтобы она обеспечивала минимальные издержки, обусловленные несогласованностью спроса и предложения (дисбалансом).

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

Математическая формулировка задачи

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

Определим матрицу стоимостей производства и хранения изделий:

 

Месяц пр-ва (i)	Месяц потребления (j)				Программа выпуска изделий (шт)
	1	2	3	4
1	4	4,5	5	5,5	50
2	6	4	4,5	5	180
3	8	6	4	4,5	280
4	10	8	6	4	270
Спрос (шт)	100	200	180	300

$4;                (при i=j) $4 + $0,5*(j-i); (при j>i); $4 + $2*(i-j); (при i>j).

 

                  Cij =

 

В таком же виде определим программу производства изделий:

 

Месяц пр-ва (i)	Месяц потребления (j)				Программа выпуска изделий (шт)
	1	2	3	4
1	X11	X12	X13	X14	50
2	X21	X22	X23	X24	180
3	X31	X32	X33	X34	280
4	X41	X42	X43	X44	270
Спрос	100	200	180	300

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

предложение (объемы производства):

X11+X12+X13+X14= 50;

X21+X22+X23+X24=180;

X31+X32+X33+X34=280;

X41+X42+X43+X44=270.

спрос:

X11+X21+X31+X41=100;

X12+X22+X32+X42=200;

X13+X23+X33+X43=180;

X14+X24+X34+X44=300.

Целевая функция:

Z= S_i S_j (Xij*Cij) для i=1,2,3,4; j=1,2,3,4.

Изменяемые ячейки: B12:E15, целевая ячейка F17.

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

по производственной программе: F4:F7=F12:F15;

по спросу: B8:E8=B16:E16.

естественные: B12:E15 целые, неотрицательные.

Составление «скользящих» графиков .

Составление скользящего расписания при нестационарном потребительском спросе.

Математическая формулировка задачи

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

Допустим, что продавцы в магазине работают по 8 часов (в смену). В соответствии с данными задачи количество требуемых продавцов меняется через 4 часа. Если предположить, что в первую смену работает X1 продавцов, во вторую –X2 и т.д., то график работы продавцов можно представить следующим рисунком.

Жирные линии означают смены, которые начинаются через 4 часа и продолжаются 8 часов. Смены перекрываются, т.е., например, с 4-х до 8 часов в торговом зале присутствуют (X1+X2) продавцов, с 8 до 12 часов – (X2+X3) продавцов, а с 0 часов до 4-х работают (X1+X6) продавцов. Этот «скользящий» график и образует расписание смен.

X1¸X6 определяют изменяемые (варьируемые) переменные, которые следует определять из условия минимального общего количества продавцов, т.е. целевая функция в этой задаче определяется выражением

: (Х1+Х2+Х3+Х4+Х5+Х6)Þmin.

В качестве ограничений при этом будут выступать условия:

Х1+Х6>=2; X1+X2>=2; X2+X3>=5; X3+X4>=7; X4+X5>=7; X5+X6>=4.

Кроме того (Х1¸Х6) должны быть целыми и положительными.

Ячейка F8 – целевая.

Ограничения: E2:E7>=F2:F7; E2:E7 – целые и неотрицательные.