Programación de restricciones para la programación del trabajo con Google OR-Tools

En entradas anteriores ya he presentado las herramientas Google OR para la programación lineal. En este post quiero demostrar las capacidades de las herramientas Google OR para la programación con restricciones. Más específicamente, voy a resolver un problema de programación de trabajos utilizando la programación de restricciones con las herramientas de Google OR.

A diferencia de la programación lineal, la programación de restricciones permite tipos arbitrarios de funciones de restricción. Además, la programación de restricciones suele centrarse en la identificación de una solución factible en lugar de soluciones óptimas. Es decir, en la programación con restricciones, el problema que se resuelve a menudo puede no tener una función objetivo que optimizar.

La programación de trabajos es un buen ejemplo de programación con restricciones. En este ejemplo, una fábrica quiere hacer una programación de trabajos para una semana. El modelo de turnos permite 3 turnos en los 7 días de la semana, con 24 horas de funcionamiento por día.

La fábrica tiene 5 trabajadores. Un trabajador no debe trabajar 2 turnos seguidos en un día determinado. Además, la diferencia en la cantidad de turnos por trabajador no debe superar 1 turno.

Un turno sólo puede asignarse a un trabajador.

Un trabajador no debe trabajar 2 turnos en el mismo día.

Usando las herramientas OR de Google para la programación de restricciones encuentro un plan de trabajo factible en el código siguiente:

# importando google o tools y declarando la plantilla del modelo
from ortools.sat.python import cp_model
model = cp_model.CpModel()
# Declarar una lista vacía que se utilizará para almacenar los índices de la combinación trabajador-turno-día
turnosalternativos = {}

# Establecer el número de trabajadores, días y horarios, así como los horarios máximos por día,
# así como la diferencia del importe máximo del turno por trabajador
trabajadoras = 5
turnos = 3
dia = 7
turnosmaximosportrabajador = 1
differenciamaxima = 1

# crear una tupla como índice de lista de opciones de turno, para cada combinación de trabajador, turno y día
# Utiliza google o herramientas para crear una variable booleana que indique si determinado trabajador trabaja ese día, en ese turno
for x in range(trabajadores):
    for y in range(dias):
        for z in range(turnos):
            turnosalternativos[(x,y,z)] = model.NewBoolVar("turno con id" + str(x) + " " + str(y) + " " + str(z))

# Ahora añadimos la restricción de que el turno sólo se asigne a un trabajador
for y in range(dias):
    for z in range(turnos):
        model.Add(sum(turnosalternativos[(x, y, z)] for x in range(trabajadores)) == 1)
# Ahora añadimos la restricción de que un trabajador sólo trabaje un turno al día
for x in range(trabajadores):
    for y in range(dias):
        model.Add(sum(turnosalternativos[(x,y,z)] for z in range(turnos)) <= 1)
# Ahora añadimos la restricción de que todos los trabajadores tengan la misma cantidad de turnos, con algunas desviaciones permitidas con una diferencia máxima permitida
turnosminimasportrabajador = (turnos* dias) // trabajadores
print(turnosminimasportrabajador)
turnosmaximosportrabajador = turnosminimasportrabajador + differenciamaxima
for x in range(trabajadores):
    turnosfinal = 0
    for y in range(dias):
        for z in range(turnos):
            turnosfinal += turnosalternativos[(x,y,z)]
    model.Add(turnosminimasportrabajador <= turnosfinal)
    model.Add(turnosfinal<= turnosmaximosportrabajador)

# antes de resolver el problema añado una impresora de solución (este código está tomado directamente de la documentación de Google)
class ImpresoraDeSolucion(cp_model.CpSolverSolutionCallback):
    def __init__(self, turnosalternativos, trabajadores, dias, turnos, sols):
        val = cp_model.CpSolverSolutionCallback.__init__(self)
        self._turnosalternativos = turnosalternativos
        self._trabajadores = trabajadores
        self._dias = dias
        self._turnos = turnos
        self._soluciones= set(sols)
        self._soluciones_recuento = 0
    def on_solution_callback(self):
        if self._soluciones_recuento in self._soluciones:
            print("solucion " + str(self._soluciones_recuento))
            for y in range(self._dias):
                print("dia " + str(y))
                for x in range(self._trabajadores):
                    trabaja = False
                    for z in range(self._turnos):
                        if self.Value(self._turnosalternativos[(x,y,z)]):
                            trabaja = True
                            print("trabajador " +str(x) +" trabaja en dia " + str(y) +" turno " + str(z))
                    if not trabaja:
                        print('  trabajador {} no trabaja'.format(x))
            print()
        self._soluciones_recuento += 1
    def soluciones_recuento(self):
        return self._soluciones_recuento

# resolver el modelo
solver = cp_model.CpSolver()
solver.parameters.linearization_level = 0
# resolverlo y comprobar si la solución era factible
solrange = range(1) 
impresora_de_solucion = ImpresoraDeSolucion(turnosalternativos, trabajadores,
                                        dias, turnos, solrange)
solver.SearchForAllSolutions(model, impresora_de_solucion)
4
solucion 0
dia 0
 trabajador 0 no trabaja
 trabajador 1 trabaja en dia 0 turno 0
 trabajador 2 no trabaja
 trabajador 3 trabaja en dia 0 turno 2
 trabajador 4 trabaja en dia 0 turno 1
dia 1
 trabajador 0 no trabaja
 trabajador 1 no trabaja
 trabajador 2 trabaja en dia 1 turno 0
 trabajador 3 trabaja en dia 1 turno 2
 trabajador 4 trabaja en dia 1 turno 1
dia 2
 trabajador 0 no trabaja
 trabajador 1 no trabaja
 trabajador 2 trabaja en dia 2 turno 0
 trabajador 3 trabaja en dia 2 turno 1
 trabajador 4 trabaja en dia 2 turno 2
dia 3
 trabajador 0 trabaja en dia 3 turno 2
 trabajador 1 does not work
 trabajador 2 does not work
 trabajador 3 trabaja en dia 3 turno 1
 trabajador 4 trabaja en dia 3 turno 0
dia 4
 trabajador 0 trabaja en dia 4 turno 0
 trabajador 1 trabaja en dia 4 turno 2
 trabajador 2 trabaja en dia 4 turno 1
 trabajador 3 no trabaja
 trabajador 4 no trabaja
dia 5
 trabajador 0 trabaja en dia 5 turno 0
 trabajador 1 trabaja en dia 5 turno 1
 trabajador 2 trabaja en dia 5 turno 2
 trabajador 3 no trabaja
 trabajador 4 no trabaja
dia 6
 trabajador 0 trabaja en dia 6 turno 1
 trabajador 1 trabaja en dia 6 turno 2
 trabajador 2 trabaja en dia 6 turno 0
 trabajador 3 no trabaja
 trabajador 4 no trabaja

Leave a Reply

Deja una respuesta

Tu dirección de correo electrónico no será publicada.

Este sitio usa Akismet para reducir el spam. Aprende cómo se procesan los datos de tus comentarios.

Close

Meta