Тест№4. Теория расписаний. Задача упорядочения.

Справочный материал.

С понятием расписания почти каждый человек знаком и на интуитивном и на понятийном уровне. Однако расписания бывают разные: расписание занятий в школе или вузе, расписание движения поездов, расписание порядка обработки детали на заводе и т. д. Соответственно, и задачи, которые необходимо решать при составлении расписаний, также бывают разные. Мы здесь остановимся на двух таких задачах. Первая из них – задача упорядочения. Но сначала о понятиях и величинах, которые будут фигурировать при постановке и решении этой задачи:

- процесс в теории расписаний обычно называют работой или операцией, а совокупность работ мы будем обозначать как A = (a₁, a₂,…,a_n), где a_i – конкретная i – тая работа, а n – общее количество работ;

- начало работы t_si;

- длительность работы τ_i;

- конец работы t_fi=t_si+ τ_i;

- стоимость работы c_i;

- директивный срок D_i (момент времени, к которому необходимо закончить работу) и т. д.

Задача упорядочения состоит в том, чтобы найти такой порядок выполнения работ, чтобы минимизировать, например, общую длительность выполнения плана (задания) T.

Решением задачи является совокупность моментов начала t_si всех операций.

Условие следования a_k за a_i:

t_sk – t_si ≥ 0.

Условие несовпадения:

t_sk - t_si ≥ τ_i.

Пример. Работы A = (a_1, a₂, a₃, a₄, a₅), длительности работ: τ₁ =2, τ₂ =1, τ₃ = 2, τ₄=2, τ₅=1. Ограничения на порядок следования:

t₂ – t₁ ≥ 2,

t₃ – t₁ ≥ 2,

t₄ – t₂ ≥ 1,

t₅ – t₃ ≥2,

здесь t_j - переменная, соответствующая началам работ. Найти значения всех начал работ, чтобы общая длительность была наименьшей:

t₁ + t₂ + t₃ + t₄ + t₅ → min.

Как видно из постановки задачи – это задача линейного программирования (ЛП).

Решение. Из ограничений видно, что ограничений – четыре, а неизвестных – пять, поэтому одно из неизвестных можно выбрать почти произвольно (ориентируясь только на ограничения). Переменная t₁ входит в ограничения со знаком минус, поэтому можно положить t₁ = t_s1 = 0. Чтобы преобразовать ограничения в равенства, вводим четыре новых переменных t₁, t₂, t₃, t₄ (по одному на каждое из неравенств). Тогда задача принимает вид:

f(t)= t₂ + t₃ + t₄ + t₅ → min.

t₂ – t₆ = 2,

t₃ – t₇ = 2,

t₄ – t₂ – t₈ = 1,

t₅ – t₃ – t₉ =2.

Система ограничений не является канонической и не может быть напрямую решена симплекс-методом, но ее можно привести к канонической по методу Гаусса:

 

t₂ – t₆ = 2,

t₃ – t₇ = 2,

t₄ – t₆ – t₈ = 3,

t₅ – t₇ – t₉ = 4.

Переменные t_2, t_3, t_4, t₅ являются в этой системе базисными переменными, а переменные t_6, t_7, t_8, t₉ - свободными переменными. После этого из данной системы легко выразить целевую функцию через свободные переменные

f(t)= 11 +2 t₆ +2 t₇ + t₈ + t₉.

Задача с данной целевой функцией и с этими ограничениями уже будет канонической и легко решается симплекс – методом:

t_s1 = 0, t_s2 = 2, t_s3 = 2, t_s4 =3, t_s5 = 4.

Расписание выполнения работ, соответствующее этому решению и приведенным выше длительностям работ, приведено ниже в виде графика

Ганта:

Работы	Сроки
a1	**********	*********
a2			*********
a3			*********	*********
a4				*********	*********
a5					*********

0 1 2 3 4 5

 

Задание. Для работ A = (a₁, a₂, a₃, a₄, a₅, a₆), длительности которых и ограничения заданы ниже в таблице вариантов заданий, найти оптимальные по времени сроки начала работ и построить расписание в виде графика Ганта.

№№ варианта	Длительности работ	Ограничения
	τ1 =2, τ2 =1, τ3 = 2, τ4=2, τ5=1, τ6=1	t2 – t1 ≥ 2, t3 – t1 ≥ 2, t4 – t2 ≥ 1, t5 – t3 ≥2, t6 – t4 ≥2
	τ1 =1, τ2 =2, τ3 = 1, τ4=2, τ5=2, τ6=1	t2 – t1 ≥ 1, t3 – t1 ≥ 2, t4 – t2 ≥ 2, t5 – t3 ≥1, t6 – t4 ≥2
	τ1 =2, τ2 =1, τ3 = 2, τ4=2, τ5=3, τ6=2	t2 – t1 ≥ 2, t3 – t1 ≥ 2, t4 – t2 ≥ 1, t5 – t3 ≥2, t6 – t4 ≥2
	τ1 =2, τ2 =1, τ3 = 1, τ4=1, τ5=2, τ6=2	t2 – t1 ≥ 1, t3 – t1 ≥ 1, t4 – t2 ≥ 1, t5 – t3 ≥2, t6 – t4 ≥1
	τ1 =2, τ2 =1, τ3 = 1, τ4=2, τ5=1, τ6=2	t2 – t1 ≥ 1, t3 – t1 ≥ 2, t4 – t2 ≥ 1, t5 – t3 ≥1, t6 – t4 ≥2
	τ1 =2, τ2 =1, τ3 = 2, τ4=2, τ5=1, τ6=1	t2 – t1 ≥ 2, t3 – t1 ≥ 2, t4 – t2 ≥ 1, t5 – t3 ≥2, t6 – t4 ≥2
	τ1 =1, τ2 =2, τ3 = 1, τ4=2, τ5=2, τ6=1	t2 – t1 ≥ 1, t3 – t1 ≥ 2, t4 – t2 ≥ 2, t5 – t3 ≥1, t6 – t4 ≥2
	τ1 =2, τ2 =1, τ3 = 2, τ4=2, τ5=3, τ6=2	t2 – t1 ≥ 2, t3 – t1 ≥ 2, t4 – t2 ≥ 1, t5 – t3 ≥2, t6 – t4 ≥2
	τ1 =2, τ2 =1, τ3 = 1, τ4=1, τ5=2, τ6=2	t2 – t1 ≥ 1, t3 – t1 ≥ 1, t4 – t2 ≥ 1, t5 – t3 ≥2, t6 – t4 ≥1
	τ1 =2, τ2 =1, τ3 = 1, τ4=2, τ5=1, τ6=2	t2 – t1 ≥ 1, t3 – t1 ≥ 2, t4 – t2 ≥ 1, t5 – t3 ≥1, t6 – t4 ≥2

 

Тест№5. Теория расписаний. Задача распределения

Задача состоит в том, чтобы распределить совокупность работ

A = (a₁, a₂, …, a_n) по ресурсам (рабочим местам, расположенным в линию). Известны τ_i и множество предшествующих ей работ.

Критерии: число рабочих мест или время выполнения работ.

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

Для этой цели используется метод ветвей и границ. Рассмотрим на примере трех ресурсов A, B, C.

Общее время выполнения всех работ

T=max_{1≤u1≤u2≤n} [ ∑ ^u1_k=1 τ_ik^A + ∑^u2_k=u1 τ_ik^B + ∑^u3_k=u2 τ_ik^C ] (1)

Здесь k - очередность выполнения работы a_i на каждом из ресурсов: A, B, C.

Ресурс A завершает обслуживание последовательности π из r работ A^* за время

T_A(π) = ∑^r_k=1 τ_ik^A (2)

Ресурс B завершает обслуживание последовательности π из r работ A^* за время

T_B(π) = max_1≤u≤r [ ∑^u_k=1 τ_ik^A + ∑^r_k=u τ_ik^B ] (3)

Ресурс С завершает обслуживание последовательности π из r работ A^* за время

T_C(π) = max_1≤u≤r [ ∑^u1_k=1 τ_ik^A + ∑^u2_k=u1 τ_ik^B + ∑^r_k=u2 τ_ik^C ] (4)

На основе формул (2)-(4) формируется следующая оценка γ(π) времени выполнения работ по ресурсам:

T_A(π)+ ∑_kЄA\A^* τ^A_k + min _kЄA\A^*(τ^B_k + τ^C_k)

γ(π) = T_B(π) + ∑_kЄA\A^* τ^B_k + min _kЄA\A^* τ^C_k (5)

T_C(π) + ∑_kЄA\A^* τ^C_k

Функция γ(π) вычисляется для каждой из оставшихся работ A\A^* на r – том шаге построения перестановки работ. В перестановку включается работа, имеющая значение, меньшее γ(π).

Пример. Построить оптимальное по быстродействию расписание выполнения совокупности работ A=(a_1, a₂, a₃, a₄, a₅) на ресурсах A, B, C. Времена выполнения каждой работы на каждом ресурсе приведены в таблице

ak	a1	a2	a3	a4	a5
τ^Ak
τ^Bk
τ^Ck

Процесс решения этой задачи методом ветвей и границ представлен на Рис.1. На первом этапе рассматриваются все пять работ (вершин дерева решения задачи) в качестве 1-го элемента перестановки. Для каждой из них вычисляются оценки γ(a₁) одноэлементной перестановки π=a₁ по формулам (5):

γ_A(a₁)= 5 + (4+7+2+3) + (1 + 1)=23;

γ_B(a₁)= (5+8) + (4+1+8+1) + 1 =28;

γ_C(a₁)= (5 + 8 + 1) + (9 + 4 + 4 +1)= 32.

Из них выбирается максимальная: γ(a₁) = γ_C(a₁)=32. Еюи помечается соответствующая вершина дерева (Рис. 1).

 

 

29

32

a1

32

a2

31

a3

34

a4

29

a5

30

a1

33

29

29

30

a2

a3

a5

29

a1

29

a3

29

a5

29

a3

a5

a5

Рис.1.

 

После вычисления оценок для всех работ по минимальной оценке γ_A(a_k)=29

в качестве 1-го элемента перестановки выбирается работа a₄. Аналогичным образом выбираются 2-й и последующие элементы перестановки π из оставшихся работ.

График Ганта оптимальной последовательности работ (Рис. 2) строится с использованием вышеприведенной таблицы. Каждой работе в графике ставится в соответствие потребляемый ею ресурс A, B, C.

Раб. Сроки

5

*

*

* A

* B

* C

4

*

* A

*

*

*

*

*

* B

*

*

*

* C

3

*

*

*

*

*

*

* A

* B

*

*

*

* C

2

*

*

*

* A

*

*

*

* B

*

*

*

*

*

*

*

*

* C

1

*

*

*

*

*

* A

*

*

*

*

*

*

*

* C

0 5 10 15 20 25 30

 

Задание

Построить оптимальное по быстродействию расписание выполнения совокупности работ A=(a_1, a₂, a₃, a₄, a₅) на ресурсах A, B, C. Времена выполнения каждой работы на каждом ресурсе приведены в таблице для каждого варианта.

№ 1
k	1	2	3	4	5
^Ak
^Bk
^Ck

 

№2
k	1	2	3	4	5
^Ak
^Bk
^Ck

 

№3
k	1	2	3	4	5
^Ak
^Bk
^Ck

 

№4
k	1	2	3	4	5
^Ak
^Bk
^Ck

 

№ 5
k	1	2	3	4	5
^Ak
^Bk
^Ck

 

№ 6
k	1	2	3	4	5
^Ak
^Bk
^Ck

 

№ 7
k	1	2	3	4	5
^Ak
^Bk
^Ck

 

№ 8
k	1	2	3	4	5
^Ak
^Bk
^Ck

 

№ 9
k	1	2	3	4	5
^Ak
^Bk
^Ck

 

№ 10
k	1	2	3	4	5
^Ak
^Bk
^Ck

 

№ 11
k	1	2	3	4	5
^Ak
^Bk
^Ck

 

№ 12
k	1	2	3	4	5
^Ak
^Bk
^Ck

 

№ 13
k	1	2	3	4	5
^Ak
^Bk
^Ck

 

№ 14
k	1	2	3	4	5
^Ak
^Bk
^Ck

 

№ 15
k	1	2	3	4	5
^Ak
^Bk
^Ck

 

№ 16
k	1	2	3	4	5
^Ak
^Bk
^Ck

 

№ 17
k	1	2	3	4	5
^Ak
^Bk
^Ck

 

№ 18
k	1	2	3	4	5
^Ak
^Bk
^Ck

 

№ 19
k	1	2	3	4	5
^Ak
^Bk
^Ck