19. Составление расписания выполнения комплекса работ в кратчайшие сроки методами теории графов.

Определение. Графом G называется пара (V, E), где – непустое множество вершин графа, а– множество ребер графа, причем каждое ребро – это неупорядоченная пара различных вершин.

Определение. Ориентированные графы - графы с ориентированными (имеющими направление) ребрами. У таких графов каждое ребро выходит из его начальной в его конечную вершину и называется дугой. Всякая вершина, в которую не входит ни одна дуга, называется источником, а вершина, из которой нет выходящих дуг – стоком.

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

Используя алгоритм Демукрона, получаем следующий порядок выполнения процессов: D,B,C,F,G,A,E. Очевидно, что для выполнения всех процессов в указанном порядке потребуется ровно 28 часов. Однако за счет параллельного выполнения некоторых процессов можно добиться значительного сокращения этого срока. Для этого нужно, чтобы каждый исполнитель приступал к выполнению своего процесса сразу, как только появится такая возможность, т.е. как только завершится выполнение предшествующих процессов.

Если моменты начала и окончания каждого процесса будут такими, как указано в таблице, то выполнение всего комплекса процессов завершится за 20 часов. Нетрудно убедиться, что указанные в таблице моменты начала и окончания процессов не нарушают отношение предшествования между ними, заданное в условии задачи.