Задача о сетевом графике возникает при планировании сроков выполнения комплекса работ. При выполнении сложного проекта — строительстве завода, запуске космического корабля и т. д. — необходимо за наименьшее время выполнить много разных работ. При планировании сроков выполнения комплекса работ будем считать известным, какие работы надо выполнить, и время, необходимое для выполнения каждой работы. Пример . Необходимо выполнить 16 работ. Данные о затратах времени, необходимых для выполнения каждой работы, заданы в виде матрицы. Каждая работа может начинаться только после окончания работ, расположенных выше и левее данной. Надо найти минимальное время выполнения всего комплекса, свободный и полный резерв каждой работы, критический путь и все критические работы.
Самый главный вопрос, который студент должен понимать — какую задачу мы решаем? Что означают данные нам числа? Что мы ищем? В данном примере надо запланировать выполнение 16 работ. Будем считать, что они пронумерованы слева направо и сверху вниз. Так время выполнения 8 работы равно 5 (это 4-я работа во втором ряду), а время выполнения 11 работы равно 4 (это 3-я работа в третьем ряду). Что мы еще знаем об этих работах? Есть ограничения на порядок выполнения работ. Что можно сказать, например, о работе 7? Ее время выполнения равно 4, ее нельзя начинать, пока не закончены работа 3 (сосед сверху) и работа 6 (сосед слева). Что мы еще знаем об этой работе? Пока мы ее не закончим, нельзя начинать работу 8 ( сосед справа) и работу 11 (сосед снизу).
Для отыскания самого раннего срока начала некоторой работы надо найти всех ее предшественников и определить максимум из самых ранних сроков окончания этих работ. Для отыскания самого раннего срока окончания работы надо к сроку самого раннего ее начала прибавить время ее выполнения.
В этом примере работы занумерованы так, что номер предшественника всегда меньше номера самой работы, то определять самые ранние сроки будем в порядке увеличения номеров работ.
Работу 1 начнем в момент 0. Ее длительность равна 6, поэтому мы закончим ее выполнение в момент 6. Работу 2 можно начинать сразу после окончания работы 1. Поэтому самое раннее начало работы 2 равно времени самого раннего окончания работы 1, т.е. 6. Так как время выполнения равно 5, то самое раннее окончание работы 2 равно 6+5=11. Для работы 3 самые ранние сроки выполнения 11 — 18. Работу 4 можно начать после выполнения работы 3. Поэтому самые ранние сроки ее выполнения 18-24. Работу 5 можно начать после выполнения работы 1. Поэтому самые ранние сроки ее выполнения 6-11.У работы 6 два предшественника. Ее можно начинать сразу, как закончится работа 2 и работа 5. В данном случае сроки окончания этих работ случайно совпали. Поэтому, самые ранние сроки выполнения работы 6 это 11-13. У работы 7 тоже два предшественника — работы 3 и 6. Работа 3 может закончиться в 18, работа 6 — в 13. Так как должны закончиться обе работы, то из моментов их окончания надо взять максимум. mах(13,18)=18. Это и есть самое раннее время начало работы 7. Поэтому, самые ранние сроки выполнения работы 7 это 18-22. У работы 8 самые ранние сроки 24-29. Аналогично надо подсчитать ранние сроки выполнения остальных работ. Результаты удобно записать в виде таблицы.
Ранний срок выполнения работ.
Мы нашли ранние сроки выполнения каждой работы и, тем самым, минимальное время выполнения всего комплекса. Данные нам 16 работ можно выполнить за 38 единиц времени и нельзя сделать быстрее.
Подсчитаем самые поздние сроки выполнения каждой работы при условии, что мы должны уложиться в самый ранний срок выполнения всего комплекса работ.
Работу 16 необходимо закончить к 38. Поэтому самый поздний срок ее окончания равен 38. Ее длительность равна 2. Поэтому самый поздний срок начала равен 38 — 2 = 36.
Самый поздний срок окончания любой работы определяется самыми поздними сроками начала ожидающих ее работ и равен минимальному из этих сроков. Самый поздний срок начала работы равен самому позднему сроку ее окончания минус время ее выполнения.
Работу 15 необходимо закончить до начала работы 16. Поэтому самый поздний срок ее окончания равен самому позднему сроку начала работы 16, т.е. 36. Самый поздний срок ее начала равен 36-3 =33.
Работу 12 необходимо закончить до начала работы 16. Поэтому самый поздний срок ее окончания равен самому позднему сроку начала работы 16, т.е. 36. Самый поздний срок ее начала равен 36-7 =29.
Без работы 11 не могут начаться работы 12 и 15. Работу 15 надо начать не позднее 33, а работу 12 надо начать не позднее 29. Из этих сроков надо выбрать минимальный. Работу 11 необходимо закончить к 29. Поэтому самый поздний срок окончания равен 29. Самый поздний срок начала равен 29 -4 = 25.
Аналогично надо подсчитать поздние сроки выполнения остальных работ. Результаты удобно записать в виде таблицы.
Поздние сроки выполнения работ.
22-28 28-33 33-36 36-38 При этом мы обязательно должны выйти на ноль. У самой первой работы самое позднее время начала должно получиться равным 0. Если у Вас получилось по-другому, то Вы где-то ошиблись.
Важной характеристикой комплекса работ являются резервы, т.е. время, на которое без больших неприятных последствий можно задержать ту или иную работу.
Определим два вида резервов.
Полный резерв- время, на которое можно задержать выполнение работы i без изменения времени окончания всего комплекса работ:
Для нахождения полного резерва нужно от самых поздних сроков выполнения работы отнять самые ранние. Для нахождения свободного резерва надо найти минимальное время, когда эта работа кому-либо понадобится, и отнять самое раннее время окончания данной работы.
Найдем полные резервы для всех работ в нашем примере: Результаты удобно записать в виде таблицы.
Например, для 13 работы (первой в нижнем ряду) ранние сроки 13-19, а поздние сроки 22-28. Мы можем подсчитать полный резерв по срокам начала. Самый ранний 13, а самый поздний 22. Между ними интервал в (22-13) 9единиц времени. Можно подсчитать полный резерв по срокам окончания. Самый ранний 19, а самый поздний 28. Между ними интервал в (28-19) 9 единиц времени. Как и следовало ожидать, результат совпал. При расхождении надо проверять арифметику.
Свободный резерв — время, на которое можно задержать выполнение i-й работы без изменения самых ранних сроков начала последующих работ: . Здесь минимум берется по всем тем работам к, для которых работа / является предшественником.
Для вычисления свободного резерва надо определить, какие работы не могут начаться, пока не закончиться данная работа, из ранних сроков начала этих работ выбрать минимальный, и от него отнять самое раннее время окончания данной работы. Для вычисления свободных резервов достаточно знать ранние сроки выполнения работ. Для вычисления полных резервов надо знать и ранние, и поздние сроки.
Легко заметить, что. Отсюда следует, что если полный резерв равен нулю, то и свободный резерв равен нулю. Обратное может быть не верным. Найдем свободные резервы для всех работ в нашем примере:
Например, для работы 6. Ранние сроки выполнения — 11-13. Без окончания работы 6 не могут начаться работы 7 и 10. Работа 7 не может начаться ранее 18 ин возражает против задержки работы 6. Но работа 10 собирается начинаться именно в 13, поэтому свободный резерв работы 6 равен 0.
Работы, полный резерв которых равен нулю, называются критическими. У этих Ра бот ранние сроки совпадают с поздними. В данном примере критическими работами являются работы 1,2,3,4,8,12,16. Последовательность критических работ образует один или несколько критических путей, т.е. последовательностей вершин, соединяющих начало комплекса с его окончанием. В рассматриваемом примере критический путь состоит из всех критических работ 1-2-3-4-8-12-16. Если бы нам нужно было бы выполнить только эти 7 работ, образующих критический путь, то на них мы бы затратили то же время, что и на весь. наш комплекс. Мы бы с 0 до 6 выполнили бы работу 1, затем с 6 до 11 работу 2, затем с 11 до 18 работу 3, затем с 18 до 24 работу 4, затем с 24 до 29 работу 8, затем с 29 до 36 работу 12, затем с 36 до 38 работу 16.
Иногда в графе может быть несколько критических путей, но каждая работа, у котерой полный резерв равен нулю, обязательно входит хотя бы в один из критических путей.
Условие наличия решения.
Можно ли выполнить комплекс работ, заданный произвольной таблицей или графом’ Если, например, у каждой работы есть хотя бы один предшественник, то весь комплекс невыполним. Мы не можем начать ни одной работы. Если, например, у работы 5 предшественник работа 3, а у работы 3 предшественник работа 5, то весь комплекс невыполним. Мы не можем начать работу 3, пока не закончим работу 5, и не можем начать работу 5, iiok;i не закончим работу 3. Обычно такие ситуации возникают из-за ошибок в начальных данных. Сетевой график не должен содержать ориентированных циклов, т. е. в нем не должно быть такого множества вершин, в котором в каждую последующую вершину идет ориентированная дуга из предыдущей.
Такого фрагмента не должно быть в сетевом графике.
Если в графе имеется такой цикл, то ни одну из работ, соответствующих вершинам цикла, выполнить невозможно, так как для этого нужно выполнить ее предшественника.
Как проверить, есть ли в ориентированном графе циклы?
Теорема. В графе наверняка нет ориентированных циклов, если вершины занумерованы так, что каждое ребро идет из вершины с меньшим номером в вершину с большим номером.
Доказательство очевидно.
Для проверки отсутствия циклов и нахождения такой нумерации вершин можно воспользоваться следующим алгоритмом:
1) Найти в графе вершину, в которую не входит ни одна дуга. Присвоить ей номер I.
2) Среди вершин, не имеющих номера, найти такую, в которую либо не входит ни од
на дуга, либо входят дуги только из уже пронумерованных вершин. Найденная вершина получает следующий свободный номер.
Этот шаг повторяется пока это возможно.
Если в результате все вершины получат номера, то в графе нет ориентированных циклов. Если же не все вершины получили номера, то среди оставшихся вершин есть цикл. Это означает, что требования противоречивы. Наш комплекс работ выполнить невозможно.