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

Реферат

Курсовой проект 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, то наиболее наглядный и удобный метод опти¬мального планирования – есть метод, основан¬ный на построении сетевого графика. На практике этот метод более употребите¬лен, в силу того, что число работ, входящих в некоторый рассматриваемый проект, как правило, достигает не¬скольких сотен.

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

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

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

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

Как правило, экономисту-проектировщику не представляется сложным, с первого раза, построить оптимальный по структуре сетевой график, когда будет обеспечена максимальная параллельность исполнения отдельных работ. Всё зави¬сит от понимания им сущности и содержания каждой работы, входящей в состав сетевого графика.

Труднее обстоит дело с распределением трудовых ресурсов по отдельным видам работ, от которого зависит оптимальность сетевого графика по длительно¬сти. Проблема в том, что практически невозможно предугадать, как от¬разится на длительности всего проекта и соотношении длительностей различных путей его сетевого графика, перенос трудовых ресурсов с одних работ на другие, в резуль¬тате которого, при неизменной трудоемкости работ, происходит увеличение дли¬тельности первых и уменьшение длительности вторых. В таких условиях, ос¬та¬ётся только один способ оптимизации сетевого графика по длительности. Этот способ основан на методе проб и ошибок, когда, первостепенную важность играет задача проверки и анализа оптимальности уже готового, полностью рассчитанного сете¬вого графика, с целью выявления ошибок в распределении трудовых ресурсов. Рассмотрим эту задачу и связанные с ней трудности подробнее.

Для сетевого графика существуют понятия пути и его продолжительности. Под путем понимается любая цепочка непрерывно следующих, друг за другом, последовательных во времени работ, от начала проекта до его завершения. Под длительностью пути понимается суммарная длительность всех, входящих в него, последовательных работ. Более понятными, данные определения станут при рас¬смотрении следующего раздела. Сейчас же, важно другое, что каждый сетевой график имеет в своём составе два особых пути: критиче¬ский и наикратчайший. Критическим путём является путь, имеющий наибольшую продолжительность среди других возможных путей сетевого графика. Наикрат¬чайшим путём является путь, который, в отличие от критического пути, имеет наименьшую продолжи¬тельность во всём сетевом графике. На понятиях этих двух путей основан наибо¬лее простой и распространенный критерий оптимальности сетевого графика, фор¬мализуемый следующим образом:

, (1.1)

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

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

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

Из критерия (1.1) следует, что некоторый рассматриваемый сетевой график принимается оптимальным, если отношение длительности его наикратчайшего пути к длительности его критического пути не менее 0.7, или, что тоже самое, ес-ли длительность наикратчайшего пути отличается от длительности критиче¬ского пути не более чем на 30%.

Забегая вперёд, можно сказать, что длительность критического пути, легко найти путём расчёта некоторых, принятых параметров сетевого графика, которые будут подробно рассмотрены в следующем разделе. Длитель¬ность же наикрат¬чайшего пути, в общем случае неизвестна, и для её нахождения требуется сумми¬ровать длительности всех, входящих в него работ.

Теперь встаёт проблема, – а как найти работы, принадлежащие наикратчай¬шему пути, чтобы иметь возможность просуммировать их длительности? Решить данную проблему, для человека, интуитивно или простым перебором вариантов, очень проблематично, особенно при большой, сильно разветвленной структуре се¬тевого графика. Зачастую и ЭВМ справиться с этой задачей не может, в силу того, что её быстродействие ограничено, а число всех возможных вариантов путей сете¬вого графика, уже при стах событиях, может достигать миллионов или даже сотен миллионов.

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