Как мы можем как можно больше сгруппировать задачи одного типа в пакет задач с помощью ortools cp-sat?

Вопрос или проблема

from ortools.sat.python import cp_model
import pandas as pd

model = cp_model.CpModel()


# 1. Данные

tasks = {'Задача A1', 'Задача A2', 'Задача B1', 'Задача B2'}

packages = {'Пакет 1', 'Пакет 2', 'Пакет 3'}

max_package_size = 2

distances = {
    ('Задача A1', 'Задача A2'): 0,
    ('Задача A1', 'Задача B1'): 1,
    ('Задача A1', 'Задача B2'): 1,
    ('Задача A2', 'Задача B1'): 1,
    ('Задача A2', 'Задача B2'): 1,
    ('Задача B1', 'Задача B2'): 0,
}


# 2. Переменные решения

var_task_to_package_matrix = {
    (task, package): model.NewBoolVar(f"задача {task} --> группа {package}")
    for task in tasks
    for package in packages
}

var_package_is_formed_indicator = {
    package: model.NewBoolVar(f"пакет {package} сформирован")
    for package in packages
}


# 3. Ограничения

for package in packages:
    # В каждом пакете может быть не более двух задач
    model.add(
        sum(var_task_to_package_matrix[task, package] for task in tasks) <= max_package_size
    )

for task in tasks:
    # Одна задача должна быть в одном пакете и только в одном
    model.add(
        sum(var_task_to_package_matrix[task, package] for package in packages) == 1
    )

for package in packages:
    # Пакет формируется, если в него назначена хотя бы одна задача
    model.AddMaxEquality(
        var_package_is_formed_indicator[package],
        [var_task_to_package_matrix[task, package] for task in tasks]
    )


# 4. Цель

total_distances = 1

total_number_of_formed_packages = sum(var_package_is_formed_indicator[package] for package in packages)

model.Minimize(total_distances + total_number_of_formed_packages)


# 5. Решение

solver = cp_model.CpSolver()
status = solver.Solve(model=model)


L = []

if status == cp_model.OPTIMAL or status == cp_model.FEASIBLE:

    for task in tasks:
        for package in packages:
            tmp = {'задача':task, 'пакет': package, 'индикатор': solver.value(var_task_to_package_matrix[task, package])}
            L.append(tmp)

    df = pd.DataFrame(L)
    df = df[df['индикатор']==1]
    print(df)
else:
    print('Модель невозможно реализовать или она недействительна')

Ответ или решение

Для эффективного распределения задач в группы и минимизации количества формируемых пакетов с использованием библиотеки OR-Tools CP-SAT, необходимо создать модель, которая учтет различные типы задач и их "близость" друг к другу. В данной ситуации основными целями являются:

1. Минимизация количества сформированных пакетов.
2. Группировка задач одного типа в рамках одного пакета.

Основные шаги реализации

1. Определение данных

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

tasks = {'Task A1', 'Task A2', 'Task B1', 'Task B2'}

packages = {'Package 1', 'Package 2', 'Package 3'}

max_package_size = 2

distances = {
    ('Task A1', 'Task A2'): 0,  # Задачи одного типа
    ('Task A1', 'Task B1'): 1,  # Разные типы
    ('Task A1', 'Task B2'): 1,  # Разные типы
    ('Task A2', 'Task B1'): 1,  # Разные типы
    ('Task A2', 'Task B2'): 1,  # Разные типы
    ('Task B1', 'Task B2'): 0,  # Задачи одного типа
}

2. Определение переменных решения

Создадим бинарные переменные для представления задач и пакетов, а также переменные, указывающие на формирование пакетов.

var_task_to_package_matrix = {
    (task, package): model.NewBoolVar(f"task {task} -> package {package}")
    for task in tasks
    for package in packages
}

var_package_is_formed_indicator = {
    package: model.NewBoolVar(f"package {package} is formed")
    for package in packages
}

3. Ограничения

• Ограничьте количество задач в каждом пакете.
• Каждая задача должна принадлежать ровно одному пакету.
• Пакет считается сформированным, если в него добавлена хотя бы одна задача.

for package in packages:
    model.add(
        sum(var_task_to_package_matrix[task, package] for task in tasks) <= max_package_size
    )

for task in tasks:
    model.add(
        sum(var_task_to_package_matrix[task, package] for package in packages) == 1
    )

for package in packages:
    model.AddMaxEquality(
        var_package_is_formed_indicator[package],
        [var_task_to_package_matrix[task, package] for task in tasks]
    )

4. Оптимизация критериев

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

total_distance_sum = model.NewIntVar(0, 10, "total_distance_sum")

# Рассчитаем расстояние для каждого пакета
for package in packages:
    for task1 in tasks:
        for task2 in tasks:
            if task1 != task2:
                distance = distances.get((task1, task2), 1)  # Допустим, если расстояние не указано, оно равно 1
                model.AddMultiplicationEquality(
                    total_distance_sum,
                    [var_task_to_package_matrix[task1, package], var_task_to_package_matrix[task2, package], distance]
                )

# Целевая функция
model.Minimize(total_distance_sum + sum(var_package_is_formed_indicator[package] for package in packages))

5. Решение

Запустите модель и получите результаты.

solver = cp_model.CpSolver()
status = solver.Solve(model)

if status == cp_model.OPTIMAL or status == cp_model.FEASIBLE:
    L = []
    for task in tasks:
        for package in packages:
            tmp = {'task': task, 'package': package, 'indicator': solver.Value(var_task_to_package_matrix[task, package])}
            L.append(tmp)

    # Выводим результаты
    df = pd.DataFrame(L)
    df = df[df['indicator'] == 1]
    print(df)
else:
    print('Модель не разрешима или недействительна')

Заключение

Данный подход обеспечивает группировку задач одного типа и минимизацию количества пакетов. Важно помнить, что для сложных задач могут потребоваться дополнительные ограничения и модификации модели. Использование библиотеки OR-Tools CP-SAT позволит эффективно решать задачи оптимизации в сфере управления проектами и распределения ресурсов.