Управление и оптимизация / Baktolov - Zadachi raspredeleniya resursov 2002

выполнения всех операций так чтобы операция i выполнялась по- следней.

1 вариант. Выполняем последовательно операции с 1 по n (исключая операцию i), а затем выполняем операцию i. В этом слу-

чае оценка снизу будет равна

Li (n) = 2qn − qi

2 вариант. Выполняем последовательно операции с 1 по (i-1), а затем операции с n по i (в обратном порядке). Оценка снизу будет

равна

Li (n) = 2qi−1 + L − qi

Если варианты 1 и 2 проделать в обратном порядке, то полу-

чим еще две оценки

Li (n) = L + qi − 2qi

Li (n) = 2(L − qi+1) + qi

Окончательная оценка снизу равна минимальному из полу-

ченных чисел Рассмотрим решение примера 2.1 полагая, что пункт 5 соеди-

нен с начальным пунктом 0 путем длины 1.

Сначала рассмотрим случай одностороннего движения. 1 шаг. Вычисляем (L=6)

С15=7+12=19,	D1=11,	F1=8
С25=8+12=20,	D2=16,	F2=4
С35=9+12=21,	D3=18,	F3=3
С45=10+12=22,	D4=13,	F4=9
С55=5+12=17,	D5=10,	F5=7

Выполним последней операцию 3 2 шаг. Вычисляем

42

С14=7+11=18,	D1=11,	F1=7
С24=8+11=19,	D2=16,	F2=3
С44=10+11=21,	D4=13,	F4=8

Здесь следует учесть, что выполняется операция, которая рас- положена ближе к начальному пункту, чем операция 3. Поэтому момент завершения операции 3 увеличится до 2L + q3 + T = 27 , и следовательно оценка снизу этого варианта F4=9. Для операции 5

имеем

С54=5+11=16,	D5=10,	F5=6
Выполняем предпоследней операцию 2.
3 шаг. Вычисляем
С13=14+9=16,	D1=11,	F1=5
С43=15+9=19,	D4=13,	F4=6
Однако при этом

С24=14+11=25, D2=16, F2=9 С35=15+12=27, D3=18, F3=9

Так, что оценка снизу этого варианта равна 9.

С53=5+9=14, D5=10, F5=4

Выполняем третьей операцию 5

4 шаг. Вычисляем
С12=7+5=12,	D1=11,	F1=1

при этом, С53, С24 и С35 увеличиваются на длину кольца, то есть на шесть, что дает соответствующее увеличение оценки снизу до 10.

С42=4+5=9, D4=13, F4=-4

Выбираем вариант, в котором второй выполняется операция 4, а первой операция 1. Окончательно получаем решение π=(1; 4; 5; 2; 3) со значением целевой функции

43

F = max(4 −11; 9 −13;14 −10;19 −16; 21 −18)= 4

Дерево ветвлений приведено на рис. 2.12. Полученное реше- ние является оптимальным, так как нижние оценки остальных под- множеств не менее 4.

[8]	[4]	[3]		[9]	[7]
1	2	3		4	5
	[7]	[3]		[9]	[6]
	1	2		4	5
	[5]	[9]		[4]
	1	4		5
		[10]		[4]
		1		4
		Рис. 2.12
	Рассмотрим теперь случай двустороннего движения.
	1 шаг. Вычисляем (L=6)
L1(5)=5,			С15=5+12=17,		D1=11,	F1=6
L2(5)=6,			С25=6+12=18,		D2=16,	F2=2
L3(5)=7,			С35=7+12=19,		D3=18,	F3=1
L4(5)=6,			С45=6+12=18,		D4=13,	F4=5
L5(5)=5,			С55=5+12=17,		D5=10,	F5=7

44

Выполним последней операцию 3
2 шаг. Вычисляем
L1(4)=5,	С14=5+11=16,	D1=11,	F1=5
L2(4)=6,	С24=6+11=17,	D2=16,	F2=1
L4(4)=6,	С44=6+11=17,	D4=13,	F4=4
L5(4)=5,	С54=5+11=16,	D5=10,	F5=6
Четвертой выполним операцию 2
3 шаг. Вычисляем
L1(3)=5,	С13=5+9=14,	D1=11,	F1=3
L4(3)=4,	С43=4+9=13,	D4=13,	F4=0
L5(3)=5,	С53=5+9=14,	D5=10,	F5=4

при этом, увеличив значения L2(4)=8 и L3(5)=9, что приводит к уве- личению оценок С24 и С35. Выполняем третьей операцию 4

4 шаг. Вычисляем

L1(2)=3,	С12=3+7=10,	D1=11,	F1=-1
при этом, увеличивается на 2 единицы оценки L4(3), L2(4) и L3(5),
что дает оценку снизу F1=3.
L5(2)=3,	С52=3+7=10,	D5=10,	F5=0

Окончательно получаем вариант π=(1; 5; 4; 2; 3) со значением

критерия

F = max(4 −11; 10 −10; 13 −13; 17 −16; 19 −18) = 1

Это решения является оптимальным.

2.4.Оптимизация календарного графика для радиальной транспортной схемы

Выше мы рассмотрели алгоритм построения оптимальных планов перемещения бригады для линейной и кольцевой транс-

45

портных схем. Рассмотрим еще один частный случай, когда транс- портная схема является радиальной (см. рис. 2.13.)

		1	2
		β1	α2
		α1
			β2
		α5
			α3
	5	0
		β5	3
			β3

α4β4

4

Рис. 2.13.

Заметим, что время αi перемещения из начального пункта в пункт i, где выполняется работа i, в объщем случае не равно времени βi возвращения в начальный пункт. Дело в том, что αi может включать время на подготовительные работы, подбор инструмента и т.д., а βi может включать время на подготовку техники и инструмента к отъезду. Таким образом, время перехода бригады от операции i к операции j равно

lij = βi + α j

(2.6)

Такой граф называется псевдопотенциальным [1]. Любой его

гамильтонов контур имеет одну и ту же длину

46

L = å(αi + βi )

i

Таким образом, продолжительность выполнения всех опера-

ций одной бригадой равна

T = å(αi + βi + τi )	(2.7)
i

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

смотрим задачу определения очередности выполнения операций минимизирующей

η = max(ti − Di )	(2.6)
i

где ti – момент завершения i-ой операции; Di – желательный срок завершения i-ой операции. Пусть π=(i1, i2, … in) очередность выпол- нения операций. Тогда

tik	= kå−1(αij + βij + τij )+ αik + τik		= åk (αij	+ βij + τij )− βik			(2.7)
	j=1		j=1
Из (2.6) и (2.7) получаем
	åk (αij + βij + τij )≤ βik	+ Dik + η,		k =			(2.8)
					1,n
	j=1

Покажем, что оптимальным является выполнение операций в очередности возрастания величин (βi+Di).

Пусть в решении π имеет место

βiq + Diq > βiq+1 + Diq+1

Поменяем очередность выполнения операций iq и iq+1, то есть снача- ла выполняем операцию iq+1, а затем iq.

Покажем, что в новом решении неравенства (2.8) будут вы- полняться при той же величине η.

47

Имеем

qå−1(αi	j	+ βi	j	+ τi	)+ (αi	q+1
j=1				j

q+1(

å αij + βij

j=1

+ βi

+ τi

q+1

)≤ qå+1(αi

j

+ βi

+ τi )≤ βi

q+1

+ Di

+ η

q+1

j=1

j

j

q+1

+ τi

)≤ βi

q+1

+ Di

q+1

+ η < βi

+ Di

+ η

j

q

q

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

вания)	pi = βi	+ Di .
Пример 2.2. Данные об операциях приведены в табл. 2.5.
							Таблица 2.5
i	1		2	3	4	5		6
αi	3		4	6	5	1		2
βi	5		2	4	8	3		1
Di	10		4	23	34	50		57
pi	15		6	27	42	53		58
τi	3		2	1	4	5		3

Оптимальная очередь выполнения операций π=(2; 1; 3; 4; 5; 6). Ве-

личина задержки сверх желательных сроков

η= max(6 − 4;14 −10; 26 − 23; 39 − 34; 53 − 50; 61 − 57)=

=max(2; 4; 3; 5; 3; 4)= 5

Пусть теперь число бригад равно m>1. Рассмотрим задачу минимизации времени выполнения всех операций. Обозначим через Qk множество операций, выполняемых k-ой бригадой. Время вы- полнения Tk согласно (2.7) составит

48

Tk = å(αi + βi + τi ) = åCi		(2.7)
i Qk	i Q
где Сi=αi+βi+τi. Время выполнения всех операций равно
	T = max Tk	(2.9)
	k

Задача заключается в разбиении всех операций на m, групп, так чтобы величина критерия (2.9) была минимальной. Это извест- ная «задача о камнях», которая относиться к сложным, комбина- торным задачам.

Рассмотрим методы ее решения для крайних случаев, когда число бригад «велико» и когда число бригад «мало»..

Пусть число бригад равно 2. В этом случае эффективным яв- ляется метод динамического программирования. Рассмотрим его на примере.

Пример 2.3.

i		1		2	3	4	5
αi		8		5	9	4	6
	Заметим, что åCi = 32 . Следовательно, необходимо опреде-
			i
лить множество работ, Q, выполняемых первой бригадой, такое
чтобы величина åCi				была возможно ближе к 16. Построим систе-
		i Q

му координат, на одной оси которой отметим номера операций, а на другой время работы первой бригады (рис. 2.14).

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

49

15

10

5

0

1

2

3

4

5

Рис. 2.14

(1; с1)=(1; 8). Если она выполняется второй бригадой, то проводим горизонтальную линию в точку с координатами (1; 0). Из каждой полученной точки проводим две линии (наклонную и горизонталь- ную) в зависимости от того какая бригада выполняет вторую опера- цию, и т.д. Получаем сеть, приведенную на рис. 2.14. Положим длины горизонтальных дуг равными 0, а длины наклонных величи- нам Сi соответствующих операций. Задача свелась к определению пути, соединяющего начало координат с одной из конечных вершин и имеющего максимальную длину среди всех путей, длина которых не превышает 16. Таких путей два, и каждый имеет длину 15. Соот- ветственно получаем два оптимальных решения. В первом первая

50

бригада выполняет операции 2, 4 и5 (время работы равно 15), а вто- рая – операции 1,3 (время работы равно 17). Во втором – первая бригада выполняет операции 3, 5 (время работы равно 15), вторая – операции 1, 2, 4 ( время работы равно 17).

Перейдем к рассмотрению случаев, когда число бригад «ве- лико», Долее точно примем, что каждой бригаде назначается не бо- лее двух операций. Следовательно n≤2m. Пусть n=m+k, где k≤m. Пусть далее операции пронумерованы по возрастанию Сi, то есть С1≤С2≤…≤Сn. Оптимальное решение получается по следующему правилу. (m-k) операций с номерами (2k+1), …, (m+k) выполняются по одной (m-k) бригадами, а 2k операций выполняются по две k бригадами, причем первая бригада выполняет операции 1 и 2k, вто-

рая – 2 и 2k-1, третья – 3 и 2k-2 и т.д. Пример 2.4. Пусть n=9, m=6.

i	1	2	3	4	5	6	7	8	9
Сi	2	3	5	6	8	9	10	11	11

Так как n=m+3, то k=3. Следовательно операции 7,8 и 9 вы- полняются по одной. Далее одна из бригад выполняет операции 1 и 6, вторая – 2 и 5 и третья – 3 и 4. Время выполнения всех операций

T= max(10;11;11; 2 + 9; 3 + 8; 5 + 6)=11

2.5.Произвольная транспортная схема

Вслучае достаточно большого числа бригад, когда каждой бригаде достается не более двух операций, удается эффективно ре-

51