Рациональные методики поиска оптимальных путей сетевых графиков и их автоматизация на ЭВМ

Рациональные методики поиска оптимальных путей сетевых графиков и их автоматизация на ЭВМ

Реферат

Курсовой проект 43 с., 5 рис., 6 блок-схем, 1 таблица, 1 источник.

СЕТЕВОЙ ГРАФИК, АНАЛИЗ ОПТЕМАЛЬНОСТИ СЕТЕВЫХ ГРАФИКОВ, РАЦИОНАЛЬНЫЕ

МЕТОДИКИ ПОИСКА ОСОБЫХ ПУТЕЙ СЕТЕВЫХ ГРАФИКОВ, АВТОМАТИЗАЦИЯ АНАЛИЗА

СЕТЕВЫХ ГРАФИКОВ НА ЭВМ.

Направление работы – изучение математических и алгоритмических

аспектов анализа оптимальности сетевых графиков.

Основная цель работы – найти и доказать рациональные методики поиска

особых путей сетевых графиков, легко поддающиеся автоматизации на ЭВМ и

сокращающие затраты на сетевое планирование, за счёт уменьшения сроков

разработки оптимальных сетевых графиков.

Используемый в работе метод исследований – аппарат формальной логики,

позволяющий осуществлять математические доказательства с минимальным

привлечением, для этого, формул.

В ходе работы получены блок-схемы алгоритмов расчёта параметров

сетевых графиков и поиска их особых путей, которые предполагается

использовать при создании конкретной программы анализа оптимальности

сетевых графиков на любом из известных языках программирования.

Новизна работы состоит в том, что разработанные методы позволяют найти

критический и наикратчайший пути сетевого графика без перебора всех

возможных вариантов, что даёт: во-первых – высокую скорость разработки

оптимальных сетевых графиков, а во-вторых – возможность точного ответа на

вопрос об оптимальности уже готового сетевого графика и высокую степень

оптимизации сетевых графиков по длительности в случае их неоптимальности.

Содержание

Введение 4

1 Постановка задачи 6

2 Теоретические основы сетевого планирования 9

3 Обоснование рациональных методик поиска особых путей сетевых

графиков 15

4 Автоматизация анализа оптимальности сетевых графиков на ЭВМ 22

4.1 Представление сетевого графика в машинной форме 22

4.2 Автоматизация расчёта параметров сетевого графика 27

4.3 Автоматизация процесса поиска особых путей сетевого графика 40

Заключение 42

Список использованных источников 43

Введение

Одним из основных экономических показателей, определяющих

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

конструкторских и других, поддающихся экономическому анализу, работ,

связанных с разработкой и внедрением на предприятие новой техники или с

организацией и управлением деятельности всего предприятия, является общая

продолжительность их выполнения. Естественно, что в рамках некоторого

рассматриваемого проекта, эта продолжительность существенно зависит от

структуры упорядочивания отдельных, входящих в него работ. Поэтому,

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

основной задачей сетевого планирования.

В основе решения указанной задачи лежит анализ смыслового содержания

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

возможность их параллельного выполнения. Последнее, является основным

фактором сокращения длительности всего проекта.

Распространены два метода оптимального планирования или упорядочивания

проектных работ. Один из методов, основан на построении ленточного графика,

где каждой работе присваиваются такие характеристики как время начала её

выполнения, её длительность, которые затем, в виде параллельных отрезков,

наносятся на шкалу времени. Другой из методов, основан на построении

сетевого графика, где структура упорядочивания работ изображается

графически в виде сигнального графа.

Выбор того или иного метода планирования зависит от числа работ,

входящих в состав проекта. Принято, что если число работ превышает 25, то

наиболее наглядный и удобный метод оптимального планирования – есть метод,

основанный на построении сетевого графика. На практике этот метод более

употребителен, в силу того, что число работ, входящих в некоторый

рассматриваемый проект, как правило, достигает нескольких сотен.

Для сетевого графика, существует два понятия оптимальности:

оптимальность по структуре и оптимальность по длительности. Оптимальность

по структуре характеризуется степенью параллельности исполнения отдельных

работ. Оптимальность по длительности характеризуется рациональным

распределением трудовых ресурсов между параллельными видами работами,

которое обеспечивает примерно равную их продолжительность.

На сегодняшний день нет, и не предвидится появление, строгих методов и

алгоритмов построения оптимального сетевого графика, поддающихся

автоматизации на ЭВМ. Это связано с тем, что процесс построения

оптимального сетевого графика требует от экономиста-проектировщика опыта и

интуитивных свойств мышления, реализовать которые на ЭВМ практически не

возможно.

По другому обстоит дело с задачей анализа оптимальности уже готового

сетевого графика. Надо сказать, что с этой задачей экономист-проектировщик

сталкивается систематически при оптимизации сетевого графика по

длительности, когда каждое очередное принятое решение о перераспределении

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

Очевидно, что если автоматизировать процесс решения рассматриваемой задачи,

то это существенно снизит продолжительность разработки сетевого графика, а

значит и затраты на сетевое планирование в целом. Так вот, задача анализа

оптимальности сетевого графика математически формализуема и, с некоторыми

трудностями, решаема на ЭВМ. В данном курсовом проекте, как раз и будут

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

оптимальности сетевых графиков, легко автоматизируемые на ЭВМ.

Постановка задачи

Как правило, экономисту-проектировщику не представляется сложным, с

первого раза, построить оптимальный по структуре сетевой график, когда

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

Всё зависит от понимания им сущности и содержания каждой работы, входящей в

состав сетевого графика.

Труднее обстоит дело с распределением трудовых ресурсов по отдельным

видам работ, от которого зависит оптимальность сетевого графика по

длительности. Проблема в том, что практически невозможно предугадать, как

отразится на длительности всего проекта и соотношении длительностей

различных путей его сетевого графика, перенос трудовых ресурсов с одних

работ на другие, в результате которого, при неизменной трудоемкости работ,

происходит увеличение длительности первых и уменьшение длительности вторых.

В таких условиях, остаётся только один способ оптимизации сетевого графика

по длительности. Этот способ основан на методе проб и ошибок, когда,

первостепенную важность играет задача проверки и анализа оптимальности уже

готового, полностью рассчитанного сетевого графика, с целью выявления

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

с ней трудности подробнее.

Для сетевого графика существуют понятия пути и его продолжительности.

Под путем понимается любая цепочка непрерывно следующих, друг за другом,

последовательных во времени работ, от начала проекта до его завершения. Под

длительностью пути понимается суммарная длительность всех, входящих в него,

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

рассмотрении следующего раздела. Сейчас же, важно другое, что каждый

сетевой график имеет в своём составе два особых пути: критический и

наикратчайший. Критическим путём является путь, имеющий наибольшую

продолжительность среди других возможных путей сетевого графика.

Наикратчайшим путём является путь, который, в отличие от критического пути,

имеет наименьшую продолжительность во всём сетевом графике. На понятиях

этих двух путей основан наиболее простой и распространенный критерий

оптимальности сетевого графика, формализуемый следующим образом:

[pic], (1.1)

[pic] – коэффициент напряжённости наикратчайшего пути;

[pic] – длительность наикратчайшего пути, [pic];

[pic] – длительность критического пути, [pic].

Из критерия (1.1) следует, что некоторый рассматриваемый сетевой

график принимается оптимальным, если отношение длительности его

наикратчайшего пути к длительности его критического пути не менее 0.7, или,

что тоже самое, если длительность наикратчайшего пути отличается от

длительности критического пути не более чем на 30%.

Забегая вперёд, можно сказать, что длительность критического пути,

легко найти путём расчёта некоторых, принятых параметров сетевого графика,

которые будут подробно рассмотрены в следующем разделе. Длительность же

наикратчайшего пути, в общем случае неизвестна, и для её нахождения

требуется суммировать длительности всех, входящих в него работ.

Теперь встаёт проблема, – а как найти работы, принадлежащие

наикратчайшему пути, чтобы иметь возможность просуммировать их

длительности? Решить данную проблему, для человека, интуитивно или простым

перебором вариантов, очень проблематично, особенно при большой, сильно

разветвленной структуре сетевого графика. Зачастую и ЭВМ справиться с этой

задачей не может, в силу того, что её быстродействие ограничено, а число

всех возможных вариантов путей сетевого графика, уже при стах событиях,

может достигать миллионов или даже сотен миллионов.

Так вот, оказывается, эта проблема решаема, причём без перебора

вариантов и сравнительно быстро даже для человека, не говоря уже об ЭВМ.

Основной целью данной курсового проекта, как раз и является цель показать,

а точнее доказать рациональные методики поиска особых путей сетевого

графика, которые не только дают возможность проверки его оптимальности, но

и позволяют рационально выполнить его оптимизацию по длительности.

Последнее заключается в том, что если экономист-проектировщик будет знать,

как проходят особые пути сетевого графика, то он сможет, в целях

оптимизации, правильно перераспределить трудовые ресурсы, а именно –

перенести ресурсы с работ, принадлежащих наикратчайшему пути, на работы,

принадлежащие критическому пути, и тем самым уровнять длительности этих

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

Теоретические основы сетевого планирования

Прежде, чем преступать к обоснованию рациональных методик поиска

особых путей сетевого графика, необходимо напомнить, что вообще собой

представляет сетевой график, и какими основными параметрами он

характеризуется.

Итак, сетевой график – есть математическая модель упорядочивания

проектных работ типа “Сигнальный граф” (см. пример на рис.2.1 ). Любой

сигнальный граф состоит только из двух элементов: дуг и вершин. В контексте

сетевого планирования, дугами являются отдельные работы, изображаемые на

сетевом графике в виде стрелок так, что начала стрелок, соответствует

началам выполнения работ, концы стрелок – их завершению. Вершинами

сигнального графа являются так называемые события, которые изображаются на

сетевом графике в виде кружков, с порядковыми номерами в нижних квадрантах.

Как раз события сетевого графика и служат для целей упорядочивания

проектных работ, которое заключается в том, что исходящая из некоторого

события работа не может начаться, пока не завершаться все входящие в него

работы.

Существует масса правил, узаконенных стандартом, придерживаться

которых необходимо при построении сетевых графиков. Наиболее важные из них:

Любой сетевой график должен иметь начальное событие, работы из которого

только исходят, и конечное событие, в которое они только входят;

Любой путь сетевого графика должен быть полным. То есть, любая цепочка,

непрерывно следующих друг за другом, последовательных во времени работ,

должна начинаться в исходном событии сетевого графика, а заканчиваться в

конечном;

Сетевой график не должен иметь замкнутых петель. То есть, недопустимо,

чтобы конец некоторой работы являлся бы началом другой работы,

предшествующей первой по времени.

Имея только структуру сетевого графика, невозможно разрешить вопрос о

его оптимальности. Требуется проводить расчеты еще целого ряда, принятых

параметров. К этим параметрам относятся:

ранние и поздние сроки наступления событий;

ранние и поздние сроки начала и окончания работ;

резервы времени работ и событий.

Ранний срок наступления события – это минимально возможный срок,

необходимый для выполнения всех работ, предшествующих данному событию.

Расчёт ранних сроков наступления событий ведут в порядке – от начального

события проекта (с номером 0) до завершающего. При расчёте принимают, что

ранний срок наступления начального события равен 0. Для определения раннего

срока наступления [pic]-го события пользуются правилом, математически

записываемым так:

[pic] , (2.1)

[pic] – ранний срок наступления рассматриваемого события, [pic];

[pic] – номер рассматриваемого события;

[pic] – номера предшествующих событий, соединенных с рассматриваемым

работами;

[pic] – ранний срок наступления [pic]-го предшествующего события, [pic];

[pic] – длительность работы, соединяющей [pic]-е предшествующее событие с

рассматриваемым, [pic].

Таким образом, ранний срок наступления [pic]-го события – есть максимально

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

длительностей работ соединяющих предшествующие события с рассматриваемым.

Забегая вперёд, надо сказать, что эти суммы равны ранним срокам окончания

соответствующих работ. Тогда, ранний срок свершения события – есть

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

Поздний срок наступления события – это максимально допустимый срок

наступления рассматриваемого события, определяемый из условия, что после

наступления этого события в свой поздний срок остаётся достаточно времени,

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

событий ведут в обратном порядке – от завершающего события проекта до

начального (с номером 0). При расчёте принимают, что поздний срок

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

Для расчёта позднего срока наступления [pic]-го события пользуются

правилом, математически записываемым так:

[pic], (2.2)

[pic] – поздний срок наступления рассматриваемого события, [pic];

[pic] – номер рассматриваемого события;

[pic] – номера последующих событий, соединённых с рассматриваемым работами;

[pic] – поздний срок наступления [pic]-го последующего события, [pic];

[pic] – длительность работы, соединяющей [pic]-е последующее событие с

рассматриваемым, [pic].

Таким образом, поздний срок наступления [pic]-го события – есть минимально

возможная разность из разностей поздних сроков наступления последующих

событий и длительностей работ, соединяющих последующие события с

рассматриваемым. Забегая вперёд, необходимо сказать, что эти разности равны

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

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

работ.

Зная ранний и поздний сроки наступления события, можно определить

резерв времени события:

[pic], (2.3)

[pic] – резерв времени рассматриваемого события, [pic].

Резерв времени события показывает насколько можно отсрочить наступление

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

продолжительности всего проекта.

Ранний срок начала работы совпадает с ранним сроком наступления её

начального события, а ранний срок окончания работы превышает его на

величину продолжительности этой работы:

[pic]; (2.4)

[pic], (2.5)

[pic] – ранний срок начала работы, исходящей из [pic]-го события и входящей

в [pic]-е событие, [pic];

[pic] – ранний срок окончания данной работы, [pic];

[pic] – длительность этой работы, [pic];

[pic] – раннее начало события, из которого исходит рассматриваемая работа,

[pic];

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

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

продолжительности этой работы:

[pic]; (2.6)

[pic], (2.7)

[pic] – поздний срок окончания работы, исходящей из [pic]-го события и

входящей в [pic]-е событие, [pic];

[pic] – поздний срок начала данной работы, [pic];

[pic] – длительность этой работы, [pic];

[pic] – позднее окончание события, в которое входит рассматриваемая работа,

[pic].

Полный резерв времени некоторой работы – это максимальное время, на

которое можно отсрочить её начало или увеличить продолжительность, не

изменяя директивного срока наступления завершающего события сетевого

графика:

[pic], (2.8)

[pic] – полный резерв времени работы, исходящей из [pic]-го события и

входящей в [pic]-е событие, [pic].

Свободный резерв времени некоторой работы – максимальное время, на

которое можно отсрочить её начало или увеличить её продолжительность при

условии, что все события наступают в свои ранние сроки:

[pic], (2.9)

[pic] – свободный резерв времени работы, исходящей из [pic]-го события и

входящей в [pic]-е событие, [pic].

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

рассмотренные параметры сетевого графика рассчитаны для случая,

представленного на рисунке 2.1 . Здесь, длительности работ, являющиеся

исходными данными для расчёта, выбраны произвольным образом. Параметры

работ обозначены соответствующими символами возле стрелок. Параметры

событий отражены в трёх квадрантах соответствующих кружков. В левых

квадрантах отражены значения ранних сроков свершения событий. В правых –

значения поздних сроков свершения событий. В верхних – значения резервов

времени событий.

Как говорилось в предыдущем разделе, длительность критического пути

легко найти из расчёта параметров сетевого графика. Теперь можно сказать,

чему она равна, – она равна сроку свершения завершающего события сетевого

графика и, соответственно, определяет длительность выполнения всех

проектных работ. Последнее заключается в том, что проектные работы не могут

завершиться в срок, меньший, чем длительность критического пути, и в тоже

время, если все проектные работы выполняются вовремя, то срок их завершения

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

Обоснование рациональных методик поиска особых путей сетевых

графиков

Обоснование рациональных методик поиска особых путей сетевого графика

основано на смысле полного резерва времени работы, который показывает, на

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

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

вытекает из правил расчёта сетевого графика и давно известен, поэтому

Страницы: 1, 2, 3