КАТЕГОРИИ:
Архитектура-(3434)Астрономия-(809)Биология-(7483)Биотехнологии-(1457)Военное дело-(14632)Высокие технологии-(1363)География-(913)Геология-(1438)Государство-(451)Демография-(1065)Дом-(47672)Журналистика и СМИ-(912)Изобретательство-(14524)Иностранные языки-(4268)Информатика-(17799)Искусство-(1338)История-(13644)Компьютеры-(11121)Косметика-(55)Кулинария-(373)Культура-(8427)Лингвистика-(374)Литература-(1642)Маркетинг-(23702)Математика-(16968)Машиностроение-(1700)Медицина-(12668)Менеджмент-(24684)Механика-(15423)Науковедение-(506)Образование-(11852)Охрана труда-(3308)Педагогика-(5571)Полиграфия-(1312)Политика-(7869)Право-(5454)Приборостроение-(1369)Программирование-(2801)Производство-(97182)Промышленность-(8706)Психология-(18388)Религия-(3217)Связь-(10668)Сельское хозяйство-(299)Социология-(6455)Спорт-(42831)Строительство-(4793)Торговля-(5050)Транспорт-(2929)Туризм-(1568)Физика-(3942)Философия-(17015)Финансы-(26596)Химия-(22929)Экология-(12095)Экономика-(9961)Электроника-(8441)Электротехника-(4623)Энергетика-(12629)Юриспруденция-(1492)Ядерная техника-(1748)
Алгоритм задачи сетевого планирования
|
|
|
|
Рассмотренный графический способ построения сетевых графиков является удобным и наглядным только для задач, которые имеют небольшое количество работ и логических связей. Практически же приходится иметь дело с задачами, состоящими из огромного количества работ (тысячи и более), которые сложным образом взаимодействуют. Естесственно, что вычерчивать такой график неблагородный труд. Поэтому для анализа и оптимизации планов необходимо привлекать ЭВМ.
Алгоритм построения сетевого графика
1. Составляется упорядоченная структурная таблица, например, вида (таб.43):
Таблица 43
| № п/п | Работа ai | Опирается на работы | Время ti | |
| a 1 | – | t 1 | ||
| a 2 | – | t 2 | ||
| a 3 | – | t 3 | ||
| a 4 | a 1, a 2 | t 4 | ||
| a 5 | a 1, a 3, a 4 | t 5 | ||
| a 6 | a 2, a 3 | t 6 | ||
| a 7 | a 4 | t 7 | ||
| a 8 | a 4, a 5 | t 8 | ||
| a 9 | a 4, a 5, a 6 | t 9 | ||
| a 10 | a 8, a 9 | t 10 |
2. Записываются математические зависимости связей, взятых из упорядоченной структурной таблицы. Обозначим:
– минимально возможный срок начала работы 
(время отсчитывается от начала процесса);
– минимально возможный срок окончания работы .
Тогда
 ,
| (1) |
где 
– время выполнения работы .
Допустим, работа опирается на работы 
, тогда работа не может начаться раньше, чем кончится самая поздняя работа , т.е. можно записать
 .
| (2) |
Применяя формулу (2) и (1) ко всем работам по сети, находятся времена начала и окончания работ , а следовательно и минимальный срок окончания работ 
.
Вычислим величины и для показанной таблицы:
Работа 
: 
,
Работа 
: 
,
Работа 
: 
.
Работа 
опирается на работы 
, т.е. она может начаться тогда, когда закончится наиболее поздно кончающаяся из работ :
 ,
| (3) |
 .
| (4) |
Для последующих работ 
:
 .
| (5) |
Так определяются моменты начала и окончания всех работ. Время окончания всех работ, естесственно, равно максимальному из всех времён окончания , т.е.
 .
| (6) |
3. Находится критический путь. Для этого необходимо:
3.1. Найти работу , для которой время окончания 
максимально, следовательно, найденная работа будет критической и стоять первой от конца;
3.2. Среди формул (3), (4), (5) найти ту, по которой определяется момент начала – найденной критической работы ;
3.3. Величина выражена в виде максимума каких-то времён 
, …, необходимо найти то время из них, например 
, на котором достигается этот максимум (если таких времён будет несколько, то берётся любое из них). Работа 
, соответствующая времени окончания , будет также критической и стоять второй от конца на критическом пути;
3.4. Далее пункты 3.2 и 3.3 повторяются до тех пор, пока не будет найдена критическая работа, стоящая первой от начала процесса.
3.5. Путь составленный из полученных критических работ будет критическим путём.
Следует отметить, что максимум в каких-нибудь из формул (3)¸(5) может достигаться не на одной, а на нескольких работах, поэтому на сетевых графиках может быть не один, а несколько критических путей.
Аналогично отыскиваются некритические работы и дуги и соответствующие им резервы времени.
|
|
|
|
|
Дата добавления: 2015-04-29; Просмотров: 2274; Нарушение авторских прав?; Мы поможем в написании вашей работы!