1. Математические методы сетевого планирования и управления.
1.1 Основные понятия сетевого планирования и управления.
В основе методов СПУ лежит графическое представление проекта (комплекса работ для достижения поставленной цели) в виде сетевого графика. Сетевой график можно рассматривать как совокупность Gнекоторого количества точек и соответственно между нимиустановленныхсвязей. Объект G называетсяграфом, точки — его вершинами, связи между ними –дугами.Ориентация дуг, т. е. указание «начала» и «конца» каждой из них, делает графориентированным(орграфом). Граф считается заданным, если заданы все его вершины и дуги.
Если элементам графа поставить в соответствие некоторые параметры, то получим сеть. Параметры могут быть заданы вершинам или дугам графа. Орграф превращается в сеть, если каждой вершине Xi поставлено в соответствие некоторое число di, называемое интенсивностью вершины, а каждой дуге (Xi, Xj) — неотрицательное число ri,j, называемое ее пропускной способностью. Понятие сети лежит в основе системы сетевого планирования и управления (СПУ).
Сетевой график – это ориентированный граф без контуров, дуги которого имеют одну или несколько числовых характеристик. Будем отождествлять вершины орграфа ссобытиями, а дуги —работами. События и работы — основные понятия в СПУ.
Работа– это любые действия, трудовые процессы, сопровождающиеся затратами ресурсов или времени и приводящие к определенным результатам. На сетевых графиках работы изображают отрезками прямых линий с указанием направления (т. е. стрелками). Рядом со стрелкой указываются числовые характеристики: время выполнения работы, расход ресурса, количество исполнителей и так далее. Под работами подразумеваются не только реальные хозяйственные или технологические процессы, требующие затрат времени и ресурсов для их осуществления, но и процессы, потребляющие только время. Например, естественная сушка материалов, затвердение бетона и т. п. Также принято считать работами и те процессы, которые не требуют ни затрат времени, ни ресурсов. Это так называемые зависимости, илификтивные работы. Они показывают, что одна работа не может совершаться раньше другой. На сетевых графиках фиктивные работы обычно изображают пунктирными стрелками.
Событиеобозначает факт окончания всех работ в него входящих или начала работ из него выходящих. Событие не имеет протяженности во времени. На сетевом графике события изображаются геометрическими фигурами (круги, квадраты), но чаще кругами с указанием номера или шифра события. В каждое событие может входить и выходить из него несколько работ, а каждая работа ограничена двумя событиями. Событие выражает логическую связь между работами, заключающуюся в том, что работы, входящие в данное событие, непосредственно предшествуют работам, выходящим из него; ни одна выходящая из данного события работа не может начинаться до окончания всех работ, входящих в это событие.
Событие, с которого начинается выполнение проекта, является исходным, оно не имеет предшествующих работ. Событие, которое констатирует факт завершения проекта, называетсязавершающим, оно не имеет последующих работ. Все прочие события являютсяпромежуточными.
Решаем задачу сетевого планирования с помощью Python
Приветствую, меня зовут Алёна. Недавно на математический основах информатики в университете мы проходили задачу сетевого планирования, с помощью которой можно смоделировать процесс производства изделий. Мне была интересна данная тема и я решила поделиться с вами, как решить задачу сетевого планирования с использованием языка Python.
Определения
Сетевая модель — сетевой график, элементами которого (вершинами / дугами / и тем и другим) поставлены в соответствие некоторые величины, называемые весами.
С помощью сетевой модели будем моделировать процесс производства некоторого нового изделия. Вершины будут соответствовать моментам начала или окончания выполнения работ, дуги будут соответствовать условиям взаимозависимости выполняемых работ, а веса на дугах будут соответствовать ожидаемым длительностям выполнения работ.
Суть задачи: требуется определить минимально возможное время, за которое можно выполнить все работы.
Терминология
- i — номер работы
- t(i) — длительность выполнения работы i
- K(i) — множество работ, предшествующих работе с номером i
Для решения задачи пользуются специальной схемой расчета временных характеристик, позволяющей не только дать ответ на поставленный вопрос, но и найти дополнительные характеристики, позволяющие более эффективно управлять процессом изготовления нового изделия.
К таким характеристикам относятся:
- t(rn, i) — время самого раннего начала выполнения работы с номером i
- t(rk, i) — время самого раннего окончания выполнения работы с номером i
- t(pn, i) — время самого позднего начала выполнения работы с номером i
- t(pk, i) — время самого позднего окончания выполнения работы с номером i
- r(i) — резерв времени работы с номером i , т.е. время, на которое не в ущерб времени общего окончания выполнения всех работ, можно задерживать выполнение работы с номером i
- T(k) — время выполнения всех работ изделия. T(k) — длина критического пути, а критическим путём называют путь, соединяющий некоторую начальную работу — не имеющую предшествующих работ, и некоторую конечную работу — не имеющую последующих, т.е. от неё зависящих работ, суммарное время выполнения всех работ которого максимально.
Формулы
Для расчета временных характеристик будем пользоваться следующими формулами:
- t(rn,i) = 0, если K(i) — пустое множество.
- t(rk,i) = t(rn,i) + t(i)t(rn,i)= max t(rk,j), где максимум берется по всем работам j из множества K(i).
- t(pk,i) = t(rk,i), если работа i не имеет последующих.
- t(pn,i) = t(pk,i) — t(i)t(pk,i) = min t(pn,j), где минимум берется по тем работам j, которые принадлежат множеству K(i), т.е. по тем работам, от которых зависит работа с номером i.
- r(i) = t(pn,i) — t(rn,i) = t(pk,i) — t(rk,i). Работы критического пути — это те работы, резервы времени которых нулевые (r(i) = 0).
Условия
- Граф должен быть без петель и контуров, т.е. антирефлексивным бинарным отношением.
- Вы должны знать конечную работу. Значение времени критического пути смотрится у конечной работы в столбце t(pk, i).
Пример задачи
Итоговая таблица с вычисленными значениями примет вид:
Конечная работа с номером 12. Смотрим у неё значение столбца t(pk, i). Время, за которое гарантированно можно выполнить все работы = 22.
Пишем алгоритм на Python
Начнём с создания модели, которая будет поступать на вход и второй модели, которая будет заполнять нашу таблицу для планирования. Для удобства использую namedtuple (почитать про него можно тут: https://habr.com/ru/articles/438162/):
from collections import namedtuple input_model = namedtuple("input_model", ["time", "set_k"]) row = namedtuple("row", ["i", "time", "set_k", "rn", "rk", "pn", "pk", "r"])Считаем количество работ, которое нужно будет обработать:
По введённым данным начинаем решать задачу сетевого планирования:
- Если у работы нет предшествующих работ (длина множества K(i) = 0), значит это первая работа, с которой начнёт работать наш завод.
- Иначе — определяем максимальное значение раннего окончания зависимых работ.
- Обновляем таблицу.
for number, model in models.items(): time = model.time set_k = model.set_k if len(set_k) == 0: rn = 1 else: rn = max([table[s].rk for s in set_k]) + 1 rk = rn + model.time - 1 table[number] = row(i=number, time=time, set_k=set_k, rn=rn, rk=rk, pn=None, pk=None, r=None) При подсчётах можно увидеть прибавление или убавление единицы. Это дополнительный такт времени, в принципе решать задачу можно без него.
Продолжаем решать задачу сетевого планирования. Проходимся с конца таблицы (последней работы) для подсчётов:
- Ищем все посещённые работы с помощью функции search_next_numbers .
- t(pk, i) — времени самого позднего окончания выполнения работы, считается как минимальное значение выполненных работ.
- t(pn, i) — времени самого позднего начала выполнения работы, считается как t(pk, i) минус время выполнения работы.
- r — резерв времени, считается как t(pn, i) минус t(rn, i).
- В конце можно увидеть assert: проверка на корректность решения задачи (резерв времени должен быть всегда равен времени позднего окончания — времени раннего окончания). Эта строка необязательна, так как использование assert’ов в коде можно отключить и лучше использовать вызовы ошибок с помощью raise Error :).
- Обновляем данные в таблице.
for number, model in list(models.items())[::-1]: visited = search_next_numbers(number) current_row = table[number] if visited: k = min(visited, key=lambda num: table[num].pn if table[num].pn is not None else 10000000000) pk = table[k].pn - 1 else: pk = current_row.rk pn = pk - current_row.time + 1 r = pn - current_row.rn assert r == pk - current_row.rk and r >= 0, print(f", r=, ") table[number] = table[number]._replace(pk=pk, pn=pn, r=r) Для вывода таблицы я использовала библиотеку prettytable. Написала функцию, которая по созданному словарику с табличными данными, будет выводить таблицу:
from prettytable import PrettyTable def print_table(data: dict[int, row]): pretty_table = PrettyTable() pretty_table.field_names = ["i", "t(i)", "K(i)", "t(rn, i)", "t(rk, i)", "t(pn, i)", "t(pk, i)", "r(i)"] for line in data.values(): pretty_set = line.set_k if len(line.set_k) > 0 else "<>" pretty_table.add_row([line.i, line.time, pretty_set, line.rn, line.rk, line.pn, line.pk, line.r]) print(pretty_table) print_table(table) Заключение
Задачи сетевого планирования могут быть использованы в различных сферах деятельности, подразумевающих организацию процессов и контроль за временем выполнения работ. Например, в строительстве они применяются для планирования и управления проектами, определения зависимостей между работами и трудозатрат, а также для контроля за выполнением сроков. В промышленности задачи сетевого планирования используются для оптимизации производственных процессов и расчета затрат времени и ресурсов на производство изделий. В общем, задачи сетевого планирования могут быть полезны для управления любыми проектами, где время является критическим фактором успеха.
Спасибо за просмотр! Делитесь в комментарии своими мыслями по поводу алгоритма и самой задачи сетевого планирования. До встречи в новых статьях.