Slow performance with simple constraint programming model

Question

Im pretty new in the world of CP. Currently Im trying to solved a single machine scheduling problem with changeovers.

Here is my code and model:

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)

With small instances (10 tasks) it worked almost instantly, but above that I wasnt able to resolve the instances.

Can the formulation be improved?

Laurent Perron · Accepted Answer · 2025-01-06 20:55:20Z

0

You can check this recipe or this example.

The idea is to use a circuit constraint to apply the delay between each task and its successor.

Note that using more that one worker is needed to get good performance. See this section on parallelism.

edited Jan 6 at 20:55

answered Jan 6 at 20:49

Laurent Perron

11.2k1 gold badge10 silver badges27 bronze badges

Sign up to request clarification or add additional context in comments.

Collectives™ on Stack Overflow

Slow performance with simple constraint programming model

1 Answer 1

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Related