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
Ingeniero industrial especializado en optimización y simulación (R, Python, SQL, VBA)
Leave a Reply