Открытая транспортная задача. 3 страница

Рассмотрим другой проект, представленный следующей табли­цей:

Графическое описание проекта, построенное по этой таблице, имеет вид, показанный на рис. 2.

Рис.2

В этом графическом описании проекта, кроме тех работ, ко­торые указаны в таблице, использованы две «фиктивные» работы (3, 4) и (5, 6). На рисунке они показаны штриховыми линиями. Эти работы не требуют времени на их выполнение и используют­ся в графическом представлении проекта лишь для того, чтобы правильно отобразить взаимосвязь между работами. Получив гра­фическое представление проекта, мы обеспечили себе возмож­ность провести расчеты методом СРМ.

Определения:

Путь — последовательность взаимосвязанных работ, ведущая из одной вершины проекта в другую вершину. Например, {A, D, G} и {В, С, Е, С} — два различных пути, ведущие из вершины 1 в вер­шину 7 (см. рис. 2).

Длина пути — суммарная продолжительность выполнения всех работ пути.

Критический путь — путь, суммарная продолжительность вы­полнения всех работ которого является наибольшей.

Ясно, что минимальное время, необходимое для выполнения любого проекта, равно длине критического пути. Именно на ра­боты, принадлежащие критическому пути, следует обращать осо­бое внимание. Если такая работа будет отложена на некоторое время, то и срок окончания проекта будет отложен на то же вре­мя. Если необходимо сократить время выполнения проекта, то в первую очередь нужно сократить время выполнения хотя бы од­ной работы на критическом пути.

Для того чтобы найти критический путь, достаточно перебрать все пути и выбрать тот или те из них, что имеют наибольшую сум­марную продолжительность выполнения работ. Однако для боль­ших проектов реализация такого подхода связана с вычислитель­ными трудностями. Метод СРМ позволяет получить критический путь намного проще.

Пусть i и j — вершины, или события, проекта, (i,j) — работа проекта, s — событие «начало проекта» (start), f — событие «окон­чание проекта» (finish), Т — длина критического пути.

Введем следующие обозначения:

t(i,j) — время выполнения работы (i, j);

ES(i,j) —наиболее раннее время начала работы (i,j);

EF(i,j) —наиболее раннее время окончания работы (i,j);

LS(i,j) —наиболее позднее время начала работы (i,j),

LF(i,j) — наиболее позднее время окончания работы (i,j),

E_i — наиболее раннее время наступления события i;

L_i — наиболее позднее время наступления события i;

R(i,j) — полный резерв времени на выполнение работы (i,j) (время, на которое может быть отложена работа (i,j) без увеличения продолжительности выполнения все­го проекта);

r(i,j) — свободный резерв времени на выполнение работы (i,j) (время, на которое может быть отложена работа (i,j) без увеличения наиболее раннего времени Е_i наступ­ления последующего события j).

Если (i,j) — работа проекта, то имеют место соотношения:

для любого j ES(i,j) = Е_i;

для любого i LF(i,j) = L_j.

Для того чтобы использовать метод СРМ для нахождения критического пути, необходимо для каждой работы (i,j) опреде­лить наиболее раннее время начала и окончания работы (ES(i,j) и EF(i,j)) и наиболее позднее время начала и окончания работы (LS(i,j) и LF(i,j)).

Метод СРМ описывается следующими соотношениями:

(1)

для любой работы (s,j), выходящей из стартовой вершины s про­екта;

(2)

т.е. наиболее раннее время окончания любой работы (i,j) превы­шает наиболее раннее время начала этой работы (время наступ­ления предшествующего события i) на время ее выполнения;

(3)

т.е. наиболее раннее время начала работы (q, j) равно наиболь­шему из значений наиболее раннего времени окончания непо­средственно предшествующих ей работ;

(4)

т.е. длина критического пути равна наиболее раннему времени завершения проекта;

(5)

т.е. наиболее позднее время окончания любой работы, заверша­ющей проект, равно длине критического пути;

(6)

т.е. наиболее позднее время начала любой работы меньше наибо­лее позднего времени окончания этой работы (времени наступле­ния последующего события) на время ее выполнения;

(7)

т.е. наиболее позднее время окончания работы (/, q) равно наи­меньшему из значений наиболее позднего времени начала непо­средственно следующих за ней работ;

(8)

т.е. полный резерв времени на выполнение любой работы равен разности между наиболее поздним и наиболее ранним временем ее начала или разности между наиболее поздним и наиболее ран­ним временем ее окончания;

(9)

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

Из приведенных выше определений и соотношений непосред­ственно вытекают следующие утверждения:

1. Длина критического пути равна Т.

2. Если R(i,j) = 0, то работа (i,j) лежит на критическом пути;

если R(i,j) > 0, то работа (i,j) не лежит на критическом пути.

3. Если время начала работы (i,j), не лежащей на критичес­ком пути, отложить на срок меньший, чем r(i,j), то наиболее ран­нее время наступления последующего события не изменится.

4. Если время начала работы (i,j), не лежащей на критичес­ком пути, отложить на срок меньший, чем R(i,j), то время, необ­ходимое на выполнение всего проекта, не увеличится.

Примеры

Пример 1. Реконструкция торгового центра.

Департамент Юго-Западного округа Москвы рассматривает возможность реконструкции торгового центра у станции метро «Юго-Западная». После сноса старых палаток проектом преду­сматривается строительство павильонов для сдачи их в аренду тор­говым фирмам. Работы, которые необходимо выполнить при ре­ализации проекта, а также их взаимосвязь и время выполнения указаны в следующей таблице:

Вопросы:

1. Сколько работ на критическом пути?

2. Какова длина критического пути?

3. На сколько недель можно отложить начало выполнения работы Е, чтобы это не повлияло на срок выполнения проекта?

4. На сколько недель можно отложить начало выполнения ра­боты В, чтобы это не повлияло на срок выполнения проек­та (полный резерв времени)?

5. На сколько недель можно отложить начало выполнения работы С, чтобы это не изменило наиболее поздний срок наступления последующего события (свободный резерв времени)?

Решение. Для того чтобы определить срок выполнения про­екта, достаточно найти длину критического пути. Для этого по­строим графическое представление проекта (рис. 3).

Рис.3

Критический путь для этого проекта может быть найден с по­мощью прямых расчетов по методу СРМ, описанному в разделе «Модели». Те же результаты можно получить, воспользовавшись программой POMWIN. Для этого достаточно ввести в программу исходную информацию, описывающую проект в виде следующей таблицы:

Результаты расчетов будут представлены в виде следующей таб­лицы:

Эта таблица содержит информацию, позволяющую ответить на все вопросы задачи. Строка «Project 26» указывает на то, что дли­на критического пути равна 26. На критическом пути лежат все работы, значения резерва времени которых, указанные в послед­нем столбце, равны нулю. Это работы А, Е, F, G, I.

Таким образом, если отложить начало работы Е, то срок вы­полнения проекта увеличится. В то же время работу В можно на­чать не в нулевой момент времени, а в момент 6, т.е. начало вы­полнения работы В можно отложить на 6 недель. Критический путь для этого проекта показан на рис. 4 полужирными стрелками.

Рис. 4

Возможен другой способ введения исходной информации в программу POMWIN. Этот способ использует графическое пред­ставление проекта и как следствие описывает дуги в виде пары вершин. Соответствующее описание проекта приведено в следу­ющей таблице:

Результаты расчетов будут представлены в виде следующей таб­лицы:

Ответы: 1. Пять работ. 2. 26 недель. 3. Начало выполнения работы E отложить нельзя. Ответ — 0.

4. На шесть недель. 5. На три недели.

Вопросы

Вопрос 1. Метод СРМ разработан для:

1) описания проектов путем указания всех работ, предшеству­ющих данной работе;

2) описания проектов путем представления каждой работы в виде пары узлов сети;

3) минимизации издержек на сокращение продолжительности проекта;

4) нахождения критического пути для проектов с заданным временем выполнения каждой работы;

5) нахождения критического пути для проектов с неопределен­ным временем выполнения работ.

Вопрос 2. Узел-событие сетевого графика выражает результат:

1) начаты все работы, выходящие из узла;

2) закончены все работы, входящие в узел;

3) начата хотя бы одна работа, выходящая из узла;

4) закончена хотя бы одна работа, входящая в узел;

5) закончены все работы, входящие в узел, и начата хотя бы одна работа, выходящая из узла.

Вопрос 3. Наиболее раннее время наступления события равно:

1) минимальной длине пути из данного узла в конечный;

2) максимальной длине пути из данного узла в конечный;

3) максимальной длине пути из начального узла в данный;

4) максимальному времени наиболее раннего окончания работ, входящих в данный узел;

5) минимальному времени наиболее позднего начала работ, выходящих из данного узла.

Вопрос 4. Наиболее позднее время наступления события равно:

1) Минимальной длине пути из данного узла в конечный;

2) максимальной длине пути из данного узла в конечный;

3) максимальной длине пути из начального узла в данный;

4) максимальному времени наиболее раннего начала работ, выходящих из данного узла;

5) минимальному времени наиболее позднего начала работ, выходящих из данного узла.

Вопрос 5. Для того чтобы сократить время выполнения проек­та, необходимо:

1) сократить время выполнения каждой работы на критичес­ком пути;

2) сократить время выполнения одной работы на критическом пути;

3) сократить время выполнения каждой работы проекта;

4) сократить время выполнения одной работы проекта;

5) увеличить длину критического пути.

Вопрос 6. Полный резерв времени выполнения работы равен разности между:

1) наиболее поздним и наиболее ранним временем ее начала;

2) наиболее ранним временем ее начала и наиболее ранним временем ее окончания;

3) наиболее поздним временем ее начала и наиболее поздним временем ее окончания;

4) наиболее ранним временем ее окончания и наиболее позд­ним временем ее начала;

5) наиболее поздним временем ее окончания и наиболее ран­ним временем ее начала.

Задачи

Задача 1. Экономический факультет МГУ разрабатывает новую программу для повышения квалификации преподавателей, обуча­ющих количественным методам анализа экономики. Желательно, чтобы эту программу можно было реализовать в наиболее сжатые сроки. Имеются существенные взаимосвязи между дисциплина­ми, которые необходимо отразить, составляя расписание занятий. Например, методы управления проектами PER Т/ СРМ должны рассматриваться лишь после того, как слушатели обсудят различ­ные аспекты (коммерческие, финансовые, экономические, техни­ческие и др.) проектного анализа, связанные с жизненным цик­лом проекта.

Дисциплины и их взаимосвязь указаны в следующей таблице:

Найдите минимальное время, за которое можно выполнить программу.

Вопросы:

1. Какова длина критического пути?

2. Какое количество дисциплин находится на критическом пути?

3. Каков резерв времени изучения дисциплины f?

Задача 2. Консалтинговая компания «Системы управленческих решений» специализируется на разработке систем поддержки про­ектов. Компания заключила контракт на разработку компьютер­ной системы, предназначенной для помощи руководству фирмы при планировании капиталовложений.

Руководитель проекта разработал следующий перечень взаимо­связанных работ:

Окончание таблицы

Постройте графическое представление проекта. Используйте метод СРМдля нахождения критического пути.

Вопросы:

1. Какова длина критического пути?

2. Сколько работ находится на критическом пути?

3. Каков резерв выполнения работы F?

Задача 3. Рассмотрите следующий проект:

Найдите критический путь.

Вопросы:

1. За какое минимальное время может быть выполнен проект?

2. Сколько работ находится на критическом пути?

3. На сколько недель можно отложить выполнение работы D без отсрочки завершения проекта в целом?

4. На сколько недель можно отложить выполнение работы С без отсрочки завершения проекта в целом?

Задача 4. Проект пусконаладки компьютерной системы состоит из восьми работ. Непосредственно предшествующие работы и про­должительность выполнения работ указаны в следующей таблице:

Найдите критический путь.

Вопросы:

1. Сколько времени потребуется для выполнения проекта?

2. Сколько работ на критическом пути?

3. Чему равно наиболее раннее время начала работы С?

4. На сколько дней можно отложить выполнение работы С без отсрочки завершения проекта в целом?

5. Чему равно наиболее позднее время окончания работы F?

6. На сколько дней можно отложить выполнение работы F без отсрочки завершения проекта?

Задача 5. Московский государственный университет рассмат­ривает предложение о строительстве новой библиотеки. Работы, которые следует выполнить перед началом строительства, пред­ставлены ниже:

Найдите критический путь.

Вопросы:

1. Сколько работ находится на критическом пути? (Фиктив­ные работы не учитываются.)

2. Через какое минимальное время после принятия решения о реализации проекта можно начать работу по строительству библиотеки?

3. На сколько недель можно отложить выбор архитектурной мастерской?

4. Чему равно наиболее позднее время завершения работы по обеспечению финансирования?

Ситуации

Ситуация 1. Программа «Здоровье жителей пригородной зоны».

Программа «Здоровье жителей пригородной зоны» создана бо­лее года назад как коммерческая корпорация. Эта корпорация должна стать основой организации здравоохранения открытого типа НМО. Цель НМО — обеспечить абонентов из пригородной зоны услугами медицинской помощи по полной предоплате.

В соответствии с законом США от 1973 г. работы по планиро­ванию и организации НМО обеспечиваются федеральными гран­тами. Организационные работы включают три обязательных эта­па: основание НМО (6 месяцев), планирование (12 месяцев) и начальное развитие (12 месяцев). Правительственные гранты вы­деляются на каждый этап и автоматически не продлеваются.

В соответствии с законом предусмотрено два типа НМО: за­крытый и открытый. НМО закрытого типа организуется на базе медицинского центра, обеспечивающего амбулаторное обслужи­вание. Как правило, врачи работают в НМО закрытого типа на постоянной основе и получают зарплату.

НМО открытого типа не имеет своего медицинского центра. В этом случае НМО заключает контракт с Независимой ассоци­ацией врачей IPA. Медицинское обслуживание осуществляется как на производстве, так и в домашних условиях. Обычно рабо­та по контракту с НМО открытого типа составляет лишь неболь­шую долю практики врачей из независимой ассоциации.

Для контроля издержек и выполнения налоговых обязательств новые НМО создают отдел маркетинга, который возглавляет ди­ректор по маркетингу. Задача этого отдела — привлечь новых або­нентов, как индивидуальных, так и коллективных. Причем не только домохозяев и персонал фирм, работающих в сфере действия НМО, но и предпринимателей.

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

Программа «Здоровье жителей пригородной зоны» ориентиро­вана на создание НМО открытого типа и поэтому предполагает сотрудничество с IPA. Услуги, связанные с госпитализацией, пре­доставляются по контракту с окружным госпиталем.

В текущем году федеральный грант предоставлен программе для выполнения работ по планированию. Грант действует 12 ме­сяцев. Этап начального развития, следующий за этапом планирования, также должен быть завершен за 12 месяцев. Таким обра­зом, работа НМО может начаться после завершения обоих этапов, общая продолжительность которых составляет два года. В насто­ящее время руководство программы готовит заявку на фант для выполнения работ на этапе начального развития.

Джон Томас, исполнительный директор программы, разраба­тывает перечень мероприятий, которые необходимо провести на этапе начального развития компании с тем, чтобы этот этап дей­ствительно мог быть завершен в 12-месячный срок. На предыду­щем этапе планирования деятельность Джона Томаса была связа­на в основном с организацией и координацией работы врачей. Пришлось приложить значительные усилия для создания IPA. На этапе планирования он использовал сети СРМ для координации работ и собирается вновь применить их на заключительном, тре­тьем этапе, который должен начаться через месяц.

Джон Томас убежден, что на этапе начального развития мож­но и нужно разрабатывать сети СРМ для анализа работ в облас­ти маркетинга и финансов. Однако, несмотря на то, что эти виды деятельности связаны друг с другом, он сомневается в том, что удастся провести их комплексный анализ. Поэтому он попросил директора по маркетингу Билла Харли и директора по финан­сам Джека Дункана независимо друг от друга разработать сети СРМ для контроля мероприятий в соответствующей сфере дея­тельности.

В следующей таблице описана сеть СРМ для мероприятий, выполненных IPA на этапе планирования:

Окончание таблицы

Определив критический путь для данной сети, Джон Томас пришел к выводу, что этап планирования действительно может быть завершен за год (52 недели). Он установил также, какие ра­боты могут быть отложены и на сколько без увеличения срока вы­полнения данного этапа проекта.

Джон Томас попросил директоров по маркетингу и финансам определить все работы, которые должны быть выполнены на эта­пе начального развития, оценить время, необходимое для их вы­полнения, и установить взаимозависимость этих работ.

Маркетинг. Билл Харли, директор по маркетингу, решил соста­вить список всех работ и затем представить их в виде сети. Пер­вая из намеченных работ — работа А — нанять и обучить новый персонал, занимающийся маркетингом. На выполнение этой ра­боты требуется 5 недель.

После завершения этой работы планируется провести одновре­менно четыре работы:

В — сформировать набор медицинского оборудования для пре­доставления медицинской помощи (3 недели);

С — организовать информирование местного населения и фор­мирование общественного мнения (10 недель);

D — связаться с предпринимателями в сфере действия НМО (6 недель);

Е — разработать рекламный проспект для предпринимателей (3 недели).

Работа F — разработка планов ежемесячной регистрации або­нентов (4 недели) — может быть начата после завершения работ В и D.

После того как будет разработан рекламный проспект для пред­принимателей, его необходимо распространить. На эту работу G нужно 4 недели.

После того как будет распространен рекламный проспект и разработаны планы ежемесячной регистрации абонентов, могут одновременно выполняться две работы:

Н — провести переговоры о заключении контрактов с предпри­нимателями на обслуживание персонала фирм (8 недель);

I — подготовить рекламные материалы для персонала фирм (6 недель).

После выполнения работы H могут быть заключены контрак­ты с предпринимателями (работа J, 6 недель). После выполнения работы I следует напечатать рекламные материалы для персонала фирм (работа К, 3 недели).

После того как заключены контракты с предпринимателями и напечатаны рекламные материалы для персонала фирм, можно начать работу L по привлечению индивидуальных абонентов. Эта работа может проводиться до конца второго этапа, но требует не менее 16 недель на выполнение.

Далее остается предусмотреть выполнение двух работ. Это орга­низация симпозиума НМО (работа М, 16 недель) и его проведение (работа N, 2 недели). Организация симпозиума не может начаться, пока не будет завершена работа С.

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

Вы приглашены в качестве помощника Джона Томаса, испол­нительного директора, чтобы помочь рассчитать время выполне­ния комплекса работ по маркетингу и финансам на начальной стадии развития медицинского центра.

Задания

1. Нарисуйте сеть работ на этапе планирования. Определите критический путь и резерв времени для каждой работы. Ве­рен ли вывод Джона Томаса о том, что этап планирования можно выполнить за год?

2. Нарисуйте сеть работ по маркетингу. Рассчитайте крити­ческий путь для этой сети. Могут ли работы по маркетингу быть выполнены в течение года?

3. Нарисуйте сеть работ по финансам. Рассчитайте критичес­кий путь для этой сети. Могут ли работы по финансам быть выполнены в течение года?

4. После координационного совещания Томаса, Харли и Дун­кана выяснилось, что работы по маркетингу и финансам взаимосвязаны: работа D финансового отдела может прово­диться только после того, как завершена работа J отделом маркетинга. Определите критический путь для всех работ на этапе начального развития НМО. Верно ли утверждение, что весь комплекс работ может быть выполнен за год?

(Переработано из: Latona J.C; Nathan J. Cases and Readings in Production and Operations Management. — Boston: Allyn and Bacon, 1993)

Ответы и решения

Ответы на вопросы: 1—4, 2 — 2, 3—4, 4—5, 5—2, 6—1.

Задача 1. Решение.

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

Выполняя расчеты, получаем следующие результаты:

Ответы: 1. 15 дней. 2. 3. 3. Шесть дней.

Задача 2. Решение.

Рис.5

На основании таблицы непосредственно предшествующих работ можно по­строить следующее графическое представление проекта (рис. 5).

На этом рисунке работа, выходящая из вершины 3 и входящая в вершину 5, является фиктивной. Ее продолжительность равна нулю.

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

Окончание таблицы

Выполняя расчеты, получаем следующие результаты:

Ответы: 1. 23 недели. 2. 4. 3. Восемь недель.

Задача 3. Решение.

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

Выполняя расчеты, получаем следующие результаты:

Ответы: 1. За 22 недели. 2. Четыре работы. 3. Работу D нельзя отложить без отсрочки завершения проекта в целом. 4. На две недели.

Задача 4. Решение.

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

Выполняя расчеты, получаем следующие результаты:

Ответы: 1. 21 день. 2. 5. 3. Третий день. 4. На один день. 5. Восемнадцатый день. 6. Выполнение работы F откладывать нельзя.

Задача 5. Решение.

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

Выполняя расчеты, получаем следующие результаты:

Ответы: 1. 5. 2. Через 49 недель. 3. На две недели. 4. Не позднее чем на 41-й неделе.

Глава 8. Сетевой анализ проектов. Метод PERT

Цели

В данной главе показаны возможности использования метода PERT (Program Evaluation and Review Technique — метод оценки и обзора программы) для контроля сроков выполнения проекта. Метод PERT ориентирован на анализ таких проектов, для кото­рых продолжительность выполнения всех или некоторых работ не удается определить точно. Прежде всего речь идет о проектиро­вании и внедрении новых систем. В таких проектах многие рабо­ты не имеют аналогов. В результате возникает неопределенность в сроках выполнения проекта в целом.