简单的约束规划模型导致性能缓慢

Question

我对 CP 的世界还很陌生。目前我正在尝试通过切换来解决单机调度问题。

这是我的代码和模型：

from ortools.sat.python import cp_model
import random 


# Datos del problema
num_tasks = 20
processing_time_min = 1
processing_time_max = 10
changeover_time_min = 0
changeover_time_max = 5

# Generar tareas aleatorias
tasks = [
    {"id": i + 1, "processing_time": random.randint(processing_time_min, processing_time_max)}
    for i in range(num_tasks)
]

# Generar tiempos de cambio aleatorios (matriz de tiempos)
changeover = {
    (i + 1, j + 1): random.randint(changeover_time_min, changeover_time_max)
    for i in range(num_tasks)
    for j in range(num_tasks)
    if i != j
}

# Calcular la duración máxima total (cota superior)
processing_time_sum = sum(task["processing_time"] for task in tasks)
max_changeover = max(changeover.values())
max_duration = processing_time_sum + (len(tasks) - 1) * max_changeover

# Crear modelo
model = cp_model.CpModel()

# Variables
start_times = {task["id"]: model.NewIntVar(0, max_duration, f"start_{task['id']}") for task in tasks}
end_times = {task["id"]: model.NewIntVar(0, max_duration, f"end_{task['id']}") for task in tasks}

# Variable makespan (tiempo de finalización más tardío)
makespan = model.NewIntVar(0, max_duration, "makespan")

# Restricciones
for task in tasks:
    task_id = task["id"]
    model.Add(end_times[task_id] == start_times[task_id] + task["processing_time"])

# Evitar solapamiento de tareas y agregar tiempos de cambio
for i, task1 in enumerate(tasks):
    for j, task2 in enumerate(tasks):
        if task1["id"] != task2["id"]:
            bool_var = model.NewBoolVar(f"order_{task1['id']}_{task2['id']}")
            model.Add(start_times[task2["id"]] >= end_times[task1["id"]] + changeover[(task1["id"], task2["id"])]).OnlyEnforceIf(bool_var)
            model.Add(start_times[task1["id"]] >= end_times[task2["id"]] + changeover[(task2["id"], task1["id"])]).OnlyEnforceIf(bool_var.Not())

# Relacionar makespan con los tiempos de finalización
for task in tasks:
    model.Add(makespan >= end_times[task["id"]])

# Función objetivo: minimizar el makespan
model.Minimize(makespan)

# Resolver el modelo
solver = cp_model.CpSolver()
status = solver.Solve(model)

对于小型实例（10 个任务），它几乎可以立即工作，但除此之外我无法解决实例。

配方可以改进吗？

Answer 1

您可以查看这个食谱或这个示例。

这个想法是使用电路约束来应用每个任务与其后继任务之间的延迟。