Материал: Рациональное размещение работ по времени. методические указания к проведению практических занятий и самостоятельной работе по дисциплине «Организационно-технологическое проектирование». Баркалов С.А., Курочка П.Н

Построенные матрицы (рис. 2 - 6) позволяют решить задачу при любом b ≤19, применяя второй этап алгоритма. Так, например, при b = 12, получаем решение, в котором x2 = 1, x3 = 1, С=7.

Рассмотрим один частный случай задачи, для которого удаётся получить эффективный метод решения. Пусть имеется m проектов, каждый из которых состоит из двух типов работ, выполняемых последовательно, сначала первая, а затем вторая. Все работы первого типа выполняются одной группой проектировщиков (или одним проектировщиком). Поэтому они не могут выполняться одновременно. Для выполнения работ второго типа имеется достаточное количество специалистов. Поэтому они могут вестись параллельно. Обозначим через ai продолжительность работы первого типа для проекта i, через bi - продолжительность работы второго типа для проекта i. Рассмотрим сначала случай, когда ни одна работа не отдаётся на субподряд.

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

ности убывания bi.

Рассмотрим численный пример. Имеются пять проектов. Значения ai и bi приведены в табл. 2.

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

τi + bi ≤T , для всех i

(τi - время окончания выполнения работы первого типа проекта i).

11

Это условие означает, что если работа первого типа проекта i выполняется на субподряде, то проект будет выполнен за время, не большее требуемого Т. Если это условие нарушается, то очевидно соответствующая работа не может быть отдана на субподряд. Далее примем, что Т< Tmin, где Tmin – минимальная продолжительность выполнения всех проектов при условии, что ни одна работа первого типа не отдается на субподряд. Как и ранее, в примере будем предполагать, что все проекты пронумерованы по убыванию bi. Пусть R – множество проектов, работы первого типа которых не отданы на субподряд. Очевидно, что эти работы должны выполняться в очередности их номеров. Имея это ввиду, обозначим хi=0, если работа первого типа проекта i отдана на субподряд, хi=1 - в противном случае. На переменные хi имеются следующие ограничения:

где di =T − bi .

Задача заключается в определении {xi} максимизирующих

(сi – стоимость на субподряде работы первого типа проектаi) при ограничениях (9). Для решения этой задачи применим метод динамического программирования. Для этого рассмотрим декартову систему координат на плоскости

(рис. 7).

На горизонтальной оси отмечены номера проектов, а на вертикальной ве-

личины ∑i xia j . Сеть строится следующим образом: из начала координат про-

j=1

водятся две дуги в точки (0,1) и (а1;1), если a1≤ d1. Первая дуга соответствует тому, что работа первого типа проекта 1 отдана на субподряд, а вторая тому, что эта работа не отдана на субподряд.

Из каждой полученной точки также проводятся две дуги, соответствующие двум возможным вариантам для проекта Z (работа первого типа либо отдана на субподряд, либо не отдана). Так, из точки (0;1) получаются две точки (0;2) и (а2;2), если конечно a2≤ d2. Соответственно из точки (а1;1) получаются две точки (а1;2) и (а1+а2;2), если а1+а2≤ d2. Продолжая таким образом, получаем сеть (см. рис. 7). Эта сеть тесно связана с допустимыми решениями задачи (9),

12

(10). А именно каждый путь сети, соединяющий начальную вершину с одной из конечных, определяет некоторое допустимое решение задачи. Верно и обратное, каждому допустимому решению задачи соответствует некоторый путь в сети, соединяющий начальную вершину с одной из конечных. На рис. 7 изображена сеть для случая Т = 26.

Рис. 7

Примем длины горизонтальных дуг равными 0, а длины наклонных - стоимости соответствующих работ на субподряде. В этом случае длина любого пути, соединяющего начало координат с одной из конечных вершин сети равна разности суммарной субподрядной стоимости всех работ и стоимости работ, передаваемых на субподряд для соответствующего решения. Таким образом, решение задачи свелось к определению пути, соединяющего начальную вершину с одной из конечных и имеющего максимальную длину. Стоимости субподрядных работ указаны у наклонных дуг на рис. 7. Путь максимальной длины выделен толстыми дугами. Этому пути соответствует решение, в котором на субподряд передаются работы 1, 3 и 5.

13

Задание

1. Проект состоит из 8 независимых работ. При этом считается, что зависимость скорости работы wi от количества ресурсов ui имеет следующий вид:

wi = ui , i =1,8 . Рассматривается один вид ресурсов, его производительность N

единиц объёма на единицу времени указана в табл. 5. Объёмы Wi каждой работы i, а также стоимость сi передачи её на субподряд также приведены в таблице. Требуется выяснить, какие работы необходимо передать на субподряд, чтобы проект завершился за время, не большее T1, а стоимость работ, переданных на субподряд, была минимальна.

2. Пусть имеется 8 проектов, каждый из которых состоит из двух типов проектных работ, выполняемых последовательно, сначала первая, а затем вторая. Все работы первого типа выполняются одной группой проектировщиков (или одним проектировщиком). Поэтому они не могут выполняться одновременно. Для выполнения работ второго типа имеется достаточное количество специалистов. Поэтому они могут вестись параллельно. ai - продолжительность работы первого типа для проекта i; bi - продолжительность работы второго типа для проекта i и сi - стоимость передачи работы первого типа проекта i на субподряд приведены в табл. 5. Требуется определить проекты, работы первого типа которых передаются на субподряд так, чтобы стоимость субподрядных работ была минимальна, а все 8 проектов были завершены не позже момента времени T2.

14

15