Приветствую, меня зовут Алёна. Недавно на математический основах информатики в университете мы проходили задачу сетевого планирования, с помощью которой можно смоделировать процесс производства изделий. Мне была интересна данная тема и я решила поделиться с вами, как решить задачу сетевого планирования с использованием языка 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

1. Создание моделей для хранения входных данных, считывание данных, хранение исходных данных.

Начнём с создания модели, которая будет поступать на вход и второй модели, которая будет заполнять нашу таблицу для планирования. Для удобства использую 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"])

Считаем количество работ, которое нужно будет обработать:

n = int(input("Введите количество работ="))

Создаём словарь, в который будем помещать исходные данные, на которых будет строиться наше решение. Для удобства я использую типизацию, с которой в дальнейшем мне удобнее писать код:

models: dict[int, input_model] = dict()

Считываем данные (ничего нового). Сначала считываем время, которое тратит работа с номером i, потом вводим множество K(i) - множество работ, которые предшествует введённой работе с номером i (работа c номером i зависит от множества K(i)):

for i in range(1, n + 1):
    time = int(input(f"Введите время t({i})="))
    raw_k = input(f"Введите через пробел множество K({i})=")
    set_k = set(map(lambda data: int(data), raw_k.split()))
    models[i] = input_model(time=time, set_k=set_k)

Создаём таблицу, в которой будут храниться итоговые данные:

table: dict[int, row] = dict()

2. Считаем значения t(rn, i), t(rk, i).

По введённым данным начинаем решать задачу сетевого планирования:

• Если у работы нет предшествующих работ (длина множества 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)

При подсчётах можно увидеть прибавление или убавление единицы. Это дополнительный такт времени, в принципе решать задачу можно без него.

3. Считаем t(pk, i), t(pn, i), r.

Продолжаем решать задачу сетевого планирования. Проходимся с конца таблицы (последней работы) для подсчётов:

• Ищем все посещённые работы с помощью функции 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"{current_row}, r={r}, {pk - current_row.rk}")
    table[number] = table[number]._replace(pk=pk, pn=pn, r=r)

4. Выводим итоговую таблицу.

Для вывода таблицы я использовала библиотеку 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)

Заключение

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

С полным алгоритмом решения задачи сетевого планирования можно ознакомиться по ссылке.

Спасибо за просмотр! Делитесь в комментарии своими мыслями по поводу алгоритма и самой задачи сетевого планирования. До встречи в новых статьях.