Оптимизация использования технологического транспорта.

Задача: оптимизировать варианты использования технологического транспорта в соответствии с графиком работы основного производства.

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

Обычно технологические процессы могут быть описаны сетевым графиком. Па рис. 6.1 изображен пример такого графика.

Рис. 6.1 Сетевой график производства работ (пример).

 

Каждый элемент сетевого графика оформлен так, как показано на рис. 6.2.

Рис. 6.2. Оформление элементов сетевого графика:

 

I, j - номера "Завершения событий (например, i - завершение укладки фундаментных плит, j - завершение монтажа стен), t ₁ - здесь ранний срок начала работы i.. j. (например, подвозки стеновых панелей). t_j - поздний срок начала работы i... j. t_ij -продолжительность выполнения работы i.._ j. Х _ij - число автомобилей, необходимых для выполнения работы i.. j

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

На рис. 6.1 технологический процесс не может продолжаться меньше 13 смен (работы 0-1-4-5), работу 2-4 нельзя начать раньше, чем через 6 смен и т.д

Работы 0-1-4-5 нельзя отложить ни на одну смену, т.к. это приведет к увеличению продолжительности всего технологического процесса. Путь 0-1-4-5 называется критическим. На графике 6.1 есть еще один критический путь 0-2-4-5, те же 13 смен.

В узлах, расположенных на критическом пути, ранние и поздние сроки начала работ совпадают. В остальных узлах имеется резерв времени, здесь один такой узел - 2-й, где поздний срок начала работ равен 8. Работу 3-5 также можно начать с задержкой на 4 смены.

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

Примем условия задачи такими, как покачано из рис 6.1. Еще одно условие, в распоряжении руководителя 10 автомобилей.

Распишем возможные фронты работ (табл. 6.1).

Как видно из табл.6.1, из 3-1 возможных фронтов работ по условию обеспечения транспортом можно будет реализовать только 17 (светлый тон). Число смен, в которые должен уложиться любой реализуемый фронт работ, указано справа.

Таблица 6.1

Возможные фронты работ

Фронт	работы	Число автомобилей	Число смен	Фронт	Работы	Число автомобилей	Число смен
F1	0-1	3	4	F18	0-3,1-4	7	5
F2	0-2	6	6	F19	0-3,2-4	11
F3	0-3	3	5	F20	1-4,2-4	12
F4	1-4	4	6	F21	1-4,3-4	9	5
F5	2-4	8	2	F22	1-4,3-5	10	4
F6	3-4	5	5	F23	2-4,3-4	13
F7	3-5	6	4	F24	2-4,3-5	14
F8	4-5	7	3	F25	3-4,3-5	11
F9	0-1,0-2	9	4	F26	3-5,4-5	13
F10	0-1,0-3	6	4	F27	0-1,0-2,0-3	12
F11	0-2,0-3	9	5	F28	0-1,0-2,3-4	14
F12	0-1,2-4	11		F29	0-1,0-2,3-5	15
F13	0-1,3-4	8	4	F30	0-1,0-3,2-4	14
F14	0-1,3-5	9	4	F31	1-4,2-4,3-4	17
F15	0-2,1-4	10	6	F32	1-4,2-4,3-5	18
F16	0-2,3-4	11		F33	1-4,3-4,3-5	15
F17	0-2,3-5	12		F34	2-4,3-4,3-5	19

 

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

t₁+t₉+t₁₀+t₁₃+t₁₄=4 (все фронты, содержащие работы 0-1, должны быть реализованы за 4 смены).

t₂+t₉+t₁₁+t₁₅=6 (то же, но при наличии работ 0-2 за 6 смен).

t₃+t₁₀+t₁₁+t₁₈=5

t₄ +t₁₅+t₁₈+t₂₁+t₂₂=6

t₅=2

t₆+t₁₃+t₂₁=5

t₇+t₁₄+t₂₂=4

t₈=3

Здесь t_i время выполнения i-го фронта работ, число смен указано в скобках на лучах рис 6.1.

Выше получено, что работы (2-4) и (4-5) могут быть реализованы только отдельно, их значения определены ограничениями (t₅=2; t₈=3).

Для расчета оптимальных сочетаний других работ преобразуем указанные выше ограничения в систему уравнений:

t₁=4-t₉-t₁₀-t₁₃-t₁₄

t₂=6-t₉-t₁₁-t₁₅

t₃=5-t₁₀-t₁₁-t₁₈                  (6.1)

t₄=6-t₁₅-t₁₈-t₂₁-t₂₂

t₆=5-t₁₃-t₂₁

t₇=4-t₁₄-t₂₂

Для решения системы уравнений (6.1) составим исходную матрицу, в которой в качестве базиса укажем время выполнения простых фронтов работ (F1..F8), а в целевой строке - сложных фронтов работ из (6.1) с обратным знаком.

Таблица 6.2

Исходная матрица

	-t9	-t10	-t11	-t13	-t14	-t15	-t18	-t21	-t22	Число смен
t1	1	1	0	1	1	0	0	0	0	4
t2	1	0	1	0	0	1	0	0	0	6
t3	0	1	1	0	0	0	1	0	0	5
t4	0	0	0	0	0	1	1	1	1	6
t6	0	0	0	1	0	0	0	1	0	5
t7	0	0	0	0	1	0	0	0	1	4
	1	1	1	1	1	1	1	1	1	30

 

Кроме того, надо учесть работы (2-4) и (4-5), которые с другими не совмещаются, на их выполнение потребуется еще 5 смен.

Таким образом, если в базисе будут простые фронты работ, вся работа может быть выполнена через 35 смен.

Сделаем попытку улучшить базис, воспользовавшись методом модифицированных Жордановых исключений. Для этого в нижнюю строку столбцов t_i впишем любые положительные числа, например 1. При достижении оптимального плана они примут неположительные значения.

Используем следующий алгоритм:

1. Выберем, начиная с верхней строки, ключевую строку, и, начиная с левого, ключевой столбец. На их пересечении получим ключевой элемент.

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

2.  Составим промежуточную матрицу 6.3. В этой матрице:

2.1)все элементы ключевой строки переписываем без изменения,

2.2)все элементы ключевого столбца (кроме ключевого элемента)
меняют свой знак,

2.3)другие элементы таблицы определяем по формуле

,

Где а₁₁ – прежний элемент таблицы,

а₂₂  - ключевой элемент,

а₁₂ – соответствующий элемент ключевой строки,

а₂₂ - соответствующий элемент ключевого столбца.

Примечания: 1)если в строке таблицы замещаемый фронт работ отсутствует (т.е. в ключевом столбце коэффициент равен нулю), строка переписывается без изменений, но далее, см. действие (3), ее надо разделить на ключевой элемент, 2)нижняя строка участвует в алгоритме на общих основаниях.

3. Далее все элементы таблицы делятся на ключевой элемент, здесь
на 1. Нижнюю строку делить на ключевой элемент не обязательно.

4. В базисе простой фронт работ меняется на сложный, в целевой
строке - наоборот.

Первая преобразованная матрица приведена в табл. 6.3.

 

Таблица 6.3

1-я преобразованная матрица

	-t1	-t10	-t11	-t13	-t14	-t15	-t18	-t21	-t22	Число смен
t9	1	1	0	1	1	0	0	0	0	4
t2	-1	-1	1	-1	-1	1	0	0	0	2
t3	0	1	1	0	0	0	1	0	0	5
t4	0	0	0	0	0	1	1	1	1	6
t6	0	0	0	1	0	0	0	1	0	5
t7	0	0	0	0	1	0	0	0	1	4
	-1	0	1	0	0	1	1	1	1	26

 

Поскольку при первом преобразовании добиться неположительных значений всех цифр в нижней строке не удалось, для дальнейших преобразований воспользуемся второй строкой и третьим столбцом, принимая их за ключевые (табл. 6.3). Второй столбец использовать для замещения фронта F2 смысла нет, т.к. фронт F10 работы 0-2 не включает.

Получим ситуацию, обозначенную в табл. 6.4.

 

 

Таблица 6.4

2-я преобразованная матрица

	-t1	-t10	-t2	-t13	-t14	-t15	-t18	-t21	-t22	Число смен
t9	1	1	0	1	1	0	0	0	0	4
t11	-1	-1	1	-1	-1	1	0	0	0	2
t3	1	2	-1	1	1	-1	1	0	0	3
t4	0	0	0	0	0	1	1	1	1	6
t6	0	0	0	1	0	0	0	1	0	5
t7	0	0	0	0	1	0	0	0	1	4
	0	1	-1	1	1	0	1	1	1	24

 

Ситуация стала лучше, однако перспективы получения более оптимального плана сохранились. Улучшаем третью строку в табл 6.4 Заменяем работы фронта FЗ на работы фронта F10. После преобразований (см. табл. 6.5) полученные результаты делим на ключевой элемент (здесь он равен 2), кроме цифр нижней строки.

 

Таблица 6.5

3-я преобразованная матрица

	-t1	-t3	-t2	-t13	-t14	-t15	-t18	-t21	-t22	Число смен
t9	½	-1/2	½	½	½	-1/2	0	0	0	5/2
t11	-1/2	-1/2	-1/2	-1/2	-1/2	½	½	0	0	7/2
t10	½	2/2	-1/2	½	½	-1/2	½	0	0	3/2
t4	0	0	0	0	0	2/2	2/2	2/2	2/2	12/2
t6	0	0	0	2/2	0	0	0	2/2	0	10/2
t7	0	0	0	0	2/2	0	0	0	2/2	8/2
	-1	-1	-1	1	1	1	1	1	1	22.5

 

Перспектива улучшения плана сохранилась. Берем следующую строку (t₄) и тот фронт работ, который может заменить фронт F4, т.е. F15. Результат заносим в табл. 6.6.

 

Таблица 6. 6

4-я преобразованная матрица

	-t1	-t3	-t2	-t13	-t14	-t15	-t18	-t21	-t22	Число смен
t9	½	-1/2	½	½	½	1/2	1/2	1/2	1/2	5.5
t11	-1/2	1/2	1/2	-1/2	-1/2	-½	0	-1/2	-1/2	0.5
t10	½	1	-1/2	½	½	1/2	1	1/2	½	4.5
t4	0	0	0	0	0	1	1	1	1	6
t6	0	0	0	1	0	0	0	1	0	5
t7	0	0	0	0	1	0	0	0	1	4
	-1	-1	-1	-1	1	-1	0	1	1	25.5

 

Ситуацию улучшить не удалось. Заменим фронт работ Рб на фронт Р13, результат см. в табл. 6.7.

 

Таблица 6.7

5-я преобразованная матрица

	-t1	-t3	-t2	-t6	-t14	-t4	-t18	-t21	-t22	Число смен
t9	½	-1/2	½	-½	½	1/2	1/2	0	1/2	3
t11	-1/2	1/2	1/2	1/2	-1/2	-½	0	0	-1/2	3
t10	½	1	-1/2	-½	½	1/2	1	0	½	2
t15	0	0	0	0	0	1	1	1	1	6
t13	0	0	0	1	0	0	0	1	0	5
t7	0	0	0	0	1	0	0	0	1	4
	-1	-1	-1	-1	1	-1	0	0	1	23

 

Работы фронта F7 (3-5) входят во фронты F14 и F22. В качестве ключевого столбца выбираем фронт F22, при котором полнее используются автомобили (см. табл. 6.1). Получим оптимальную матрицу, нижняя строка которой положительных чисел не имеет (табл. 6.8).

 

 

Таблица 6.8

Оптимальная матрица

	-t1	-t3	-t2	-t6	-t14	-t4	-t18	-t21	-t7	Число смен
t9	½	-1/2	½	-½	0	1/2	1/2	0	-1/2	1
t11	-1/2	1/2	1/2	1/2	0	-½	0	0	-1/2	5
t10	½	1	-1/2	-½	0	1/2	1	0	-½	0
t15	0	0	0	0	0	1	1	1	-1	2
t13	0	0	0	1	0	0	0	1	0	5
t22	0	0	0	0	1	0	0	0	1	4
	-1	-1	-1	-1	-1	-1	0	0	1	17

Кроме того, как оговаривалось ранее, работы фронтов Р5 и Р8 должны быть добавлены к указанным в базисе табл. 6.8, это еще 5 смен.

Остается построить график реализации полученных результатов, имея в виду очередность выполнения работ F9, F11, F13, F15, F5, F22, F8. С решением задачи удается справиться за 22 смены, причем работы 0-2, которые не лежат на критическом пути, можно выполнить с некоторым запасом времени в рамках фронтов F9, F11, F15 (рис. 6.3).

Рис. 6.3. График выполнения работ автомобилями.