2.3. Задача календарного планирования при учете совмещения агрегированных операций

Коэффициент совмещения по началу kij означает, что работу j можно начинать только когда выполнена определенная часть kij работы i.

Пусть работа i начинается и заканчивается раньше работы j. В этом случае получаем сетевой график, показанный на рис. 2.5.

Работа iQ"^)^' - kij) „Q

I I

Работа j (^aiU^jO

Рис. 2.5.

Если работа i начинается раньше работы j, а заканчивается позже, то получаем сетевой график, показанный на рис. 2.6.

Работа iQb^fi - kT 4Q3jvQ 6-=L—6

Работа j

Рис. 2.6.

операций,

Аналогично можно изобразить остальные случаи. Пример 2.4. Рассмотрим проект из трех коэффициенты совмещения которых приведены ниже: ( 0 12 ^ ( 0 3 1 ^

203 420

3 0 4 v4 2

K =

Q =

Пусть очередность начала и окончания работ одна и та же - (1, 2, 3), то есть работа 1 начинается (заканчивается) раньше работы 2, а работа 2 - раньше работы 3.

[1] [7]

1 работа (6) » Ф

[1Х Д [7Х ^ 2 работа %Г(^2Г®(3Г(7)

3 работа ——>d)(-^{9)

[5] [10] [13]

Рис. 2.7.

Примем, что продолжительности работ заданы и коэффициенты совмещения измеряются в единицах времени. Продолжительность первой работы равна 7, второй - 9, третей - 6. Продолжительность проекта, определяемая критическим путем (показан на рис. 2.7 толстыми дугами) равна 13.

Задача. Определить очередность начала и окончания работ, при которой продолжительность проекта минимальна.

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

a. = mink..

bi = minq..

j*i

di = ti - bi.

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

Имеется n деталей. Каждая деталь сначала обрабатывается на первом станке в течении времени ai. Затем деталь доставляется на второй станок (время доставки равно (dj - а1))и обрабатывается на нем в течении времени b.. Одновременно на одном станке может обрабатываться только одна деталь. Требуется определить очередность обработки деталей, при которой продолжительность обработки всех деталей минимальна. Пусть детали обрабатываются в очередности их номеров. Тогда продолжительность обработки определяется выражением

(i-i

(i-i

T = max

^ aj + d. +Xb = B + max ^ C. + d.

V j=1 0

Vj=1 i

n

где B = ^ bj, с. = a. - bj.

i

Обозначив S = T - B, приведем это выражение к виду

SC.>d., i = in. (2.3.1)

j=i

Системе неравенств (2.3.1) можно дать другую содержательную интерпретацию.

Задача о лекторе.

некоторую сумму bb а тратит в городе i сумму ai. Какую минимальную сумму нужно иметь лектору, чтобы посетить все города?

Очевидно, что условие (2.3.1) является необходимым условием поездки в город i, если до этого лектор посетил города от 1 до (i-1). Из этой содержательной интерпретации сразу следует правило выбора оптимальной очередности посещения городов. Очевидно, что сначала следует посещать города, в которых оплата лекций bi превышает расходы ai, то есть после посещения которых сумма денег у лектора увеличивается. Столь же очевидно, что эти города лектору следует посещать в очередности возрастания (неубывания) транспортных расходов di. Далее лектор посещает города, в которых он тратит больше чем получает, но уже в очередности убывания (невозрастания) транспортных расходов.

Пример 2.5. Получим оценку снизу для задач из примера 2.4. Имеем:

a: = 1, b: = 2, с: = -1, d: = 5; a2 = 3, b2 = 2, c2 = 1, d2 = 7; a3 = 2, b3 = 1, с3 = 1, d3 = 5. Согласно полученному правилу, сначала обрабатывается первая деталь, затем - вторая, и затем - третья. Продолжительность обработки составит 11 дней. Фактическая продолжительность проекта при этой очередности равна13, как было показано ранее. Теперь можно организовать ветвление, то есть разбиение множества всех решений на подмножества.

Рассмотрим три подмножества. В первом подмножестве первой выполняется первая операция. Оценка снизу остается прежней, то есть Т(1) = 11, хотя фактическая продолжительность равна 13.

Во втором подмножестве первой выполняется вторая операция. Оценка снизу равна Т(2) = 12. Заметим, что фактическая продолжительность в данном случае также равна 12, то есть оценка снизу является точной.

В третьем подмножестве первой выполняется третья операция. Оценка снизу также равна 12 и определяется очередностью (3, 1, 2). Однако, фактическая оценка при этой очередности равна 14.

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

Ему соответствует очередность работ (2, 1, 3) с продолжительностью проекта Т = 12 (рис. 2.8).

2 работ

3

работа ——

[5] [11] [12]

Рис. 2.8.