|
45 (1) (4 ) Q) * { 3 Рис. 3.5. Представление сети в виде «верш ина —событие» Однако, м ож но определить аналог та ки х сетей и в представлении «верш ина работа», рис. 3.6. Для этого определим понятие «фронта работ», к а к м аксимального множества независимых работ, то есть таких, которы е м о гут вы полняться одновременно. В сети рис. 3.6. м ожно выделить три различных фронта работ: (1;2), (3;2), (3;4). Заметим, что эти фронты в определенном смысле упо рядочены, а именно, ф ронт (1;2) расположен «левее» фронта (3;2), а последний — Рис. 3.6. Представление сети в виде «верш ина —работа» «левее» фронта (3;4). Д р уги м и словами, для л ю бы х д вух фронтов работы одного из н и х либо совпадают, либо предш ествую т работам другого. Т аким образом, сетям с упорядоченны ми событиями соответствую т сети с упорядоченны ми фронтами. О п т и м и з а ц и я п о с т о и м о с т и Задачи оптимизации комплексов работ по стоимости относятся к классу задач, для которы х сущ ествую т достаточно эффективные алгоритмы. Сначала рассмотрим простой случай, когда сетевой граф ик представляет собой последовательную цепочку работ. Примем, что зависимость стоимости от продолжительности является линейной для каж дой работы: S i(ti) = ai k iti, di < Xi < Di, i = 1, n , где d минимально возможная продолжительность работы, D ; —максимальная. Примем продолжительности всех работ равными максимальным Xi = Dj. П ри П этом продолжительность проекта Т = . i= l |
Для этого определим понятие «фронта работ», как максимального множества независимых работ, то есть таких, которые могут выполняться одновременно. В сети рис. 3.6. можно выделить три различных фронта работ: (1;2), (3;2), (3;4). Заметим, что эти фронты в определенном смысле упорядочены, а именно, фронт (1;2) расположен «левее» фронта (3;2), а последний «левее» фронта (3;4). Другими словами, для любых двух фронтов работы одного из них либо совпадают, либо предшествуют работам другого. Таким образом, сетям с упорядоченными событиями соответствуют сети с упорядоченными фронтами. Оптимизация по стоимости Задачи оптимизации комплексов работ по стоимости относятся к классу задач, для которых существуют достаточно эффективные алгоритмы. Сначала рассмотрим простой случай, когда сетевой график представляет собой последовательную цепочку работ. Примем, что зависимость стоимости от продолжительности является линейной для каждой работы: Si(Ti) = askjTi, dj < Ti £ Di, i = 1,n , где di минимально возможная продолжительность работы, Dj максимальная. Примем продолжительности всех работ равными максимальным ti = Di. При этом продолжительность проекта T = S D i i^t Если мы хотим сократить продолжительность проекта с минимальным увеличением стоимости, то очевидно, что в первую очередь необходимо сокращать продолжительность работы, имеющей минимальную величину коэффициента kj. Действительно, величина kj определяет 39 |