Las organizaciones que gestionan operaciones cada vez más robustas, requieren en cierto modo de la asignación de personas y recursos a tareas específicas. Desde hace algún tiempo se ha popularizado un planteamiento en torno al objetivo de la logística, generalmente aceptado como: «El objetivo de la logística consiste en llevar el producto correcto, en la cantidad correcta, en el lugar correcto, en el momento correcto» (acepta variaciones).
Ahora bien, tendencias de optimización abordan nuevos objetivos y plantean nuevos desafíos alrededor de la intralogística: optimización extrema. Es decir, optimización en la asignación de recursos internos, como por ejemplo: el recurso correcto, asignado a la tarea correcta, en el momento correcto.
Cuando aterrizamos el anterior planteamiento en términos prácticos, entendemos que se hace necesario resolver problemas de programación complejos de forma regular, que permitan la gestión de las operaciones de la organización. Un caso puntual consiste en la programación del recurso humano, sujeta a un conjunto complejo de restricciones y requisitos: número de empleados, días laborales, turnos, tiempos inactivos, permisos, políticas internas, etc.
El planteamiento de nuevos desafíos de optimización, guarda una estrecha relación con la posibilidad que nos brinda la tecnología de abordar estos retos. Si bien, la complejidad de las organizaciones es cada vez mayor, los algoritmos cada vez son más refinados, y los solucionadores cada vez más robustos e integrados.
El objetivo de este artículo consiste en utilizar las técnicas robustas del solucionador basado en restricciones OR-Tools de Google, para resolver un problema de programación de empleados sujeto a un conjunto complejo de restricciones.
Lakeside se había fusionado con una escuela femenil local, por lo tanto, el alumnado había crecido considerablemente, y nadie lograba descifrar cómo ajustar los horarios de clase en las nuevas condiciones. Las restricciones de la programación no eran pocas, por ejemplo:
La complejidad del problema hizo que Gates buscara la ayuda de Paul Allen, con quien lograría resolver el modelo. Este fue quizá, el algoritmo que les abrió un camino comercial, puesto que otras organizaciones que tenían problemas de programación, comenzarían a acudir a esta pareja de estudiantes.
Bill Gates y Paul Allen fundaron en 1975 la compañía Microsoft, el resto es historia.
La compañía Stark Lab ha adquirido un nuevo torno para su área de mecanizado. El volumen de trabajo que tiene el área, demanda que esta nueva máquina sea operada en los 3 turnos del día (mañana, tarde y noche).
La compañía ha contratado a 3 trabajadores para operar la nueva máquina, y planea emplear a un aprendiz (estudiante) como cuarto operario.
El supervisor debe diseñar una programación para los cuatro operarios para un periodo de 7 días (una semana), sujeto a las siguientes condiciones:
- Cada día se divide en tres turnos de 8 horas.
- Todos los días, cada turno se asigna a un solo operario, y ningún operario trabajará más de un turno por día.
- El último día de la programación se realizan actividades de mantenimiento y limpieza profunda en planta. Por tal razón, solo se trabaja el turno de la mañana.
- El operario aprendiz (estudiante), cuenta con la colaboración de la compañía para realizar sus estudios. Por tal razón, no puede trabajar el tercer día de la semana en el turno de la noche.
- Como mínimo deben trabajarse 19 turnos en total en la programación. Esta cantidad de turnos ya considera los turnos destinados a mantenimiento y limpieza del último día de la programación.
- En el caso en el que no se pueda realizar una distribución de turnos igualitaria, la distribución de los turnos debe realizarse de manera uniforme. Esto quiere decir que no puede existir una diferencia mayor a un turno entre las asignaciones para cada operario.
Se desea desarrollar una programación de empleados (asignación de empleados, turnos y días), que cumpla con las restricciones del planteamiento.
En el desarrollo de este ejercicio emplearemos:
Lo primero que vamos a hacer consiste en crear un entorno de trabajo en Google Colaboratory, así que vayamos allá: Abrir cuaderno nuevo.
Verán que tienen un lienzo para programar el modelo, así que en este cuaderno podemos ir generando las líneas de código que explicaremos en los pasos siguientes.
Es necesario instalar la librería de Google Or Tools en nuestro entorno de Colaboratory para poder utilizar nuestro modelo de programación entera.
!pip install ortoolsAl ejecutar esta instrucción instalaremos el software del solucionador de Google.
Este modelo empleará programación entera, y por lo tanto instalaremos las librerías dispuestas por Google OR Tools para ello. En este caso utilizaremos un solucionador de programación entera llamado CP-SAT.
#Importar la librería para utilizar CP-SAT
from ortools.sat.python import cp_modelDe esta manera, tenemos todo lo necesario para empezar a desarrollar nuestro código.
Los datos de entrada de un problema de programación de empleados suelen ser simples, la complejidad recae en el modelamiento de las restricciones. En este caso, los datos de entrada básicos son: número de empleados, número de turnos por día, número de días del plan de programación
#Datos de entrada del modelo
operarios = 4
turnos = 3
dias = 7
total_operarios = range(operarios)
total_turnos = range(turnos)
total_dias = range(dias)
turnos_no_laborales = 2
turnos_laborales = (turnos * dias) - turnos_no_laboralesAsí mismo, definimos el número de turnos no laborales, recordemos que el planteamiento del problema nos indicó que el último día se trabajaría tan solo un turno (por labores de mantenimiento y limpieza), por lo tanto, dos turnos pueden considerarse como no laborales.
¿Por qué utilizamos una variable llamada operarios y otra llamada total_operarios? Además, ¿Para qué se emplea la función range? Bueno, la variable operarios contendrá el valor entero de la cantidad de operarios del modelo; mientras tanto, la variable total_operarios dado que emplea la función range, contendrá la secuencia de números que nos ayudará a definir a cada operario, lo hace de esta manera: range(4) = 0, 1, 2, 3. Como podemos ver, inicia la secuencia en 0, y finaliza en el entero anterior al parámetro dado, en este caso el parámetro dado fue 4, por lo tanto, el entero anterior será 3.
#Crear el modelo
model = cp_model.CpModel()El problema de programación de empleados es un caso de asignación, y por lo tanto, empleamos variables de decisión de asignación. Veamos:
Necesitamos definir qué operario será asignado a qué turno en qué día en específico. Por lo tanto podemos utilizar variables de asignación binarias, que tomen un valor de 1, si esa asignación específica tiene lugar, y tomen valor de 0, en el caso en el que no.
Algebraicamente sería algo así:
En el caso en el que tuviésemos que definir manualmente cada una de las variables de asignación, requeriríamos un total de 84 variables (7 días * 3 turnos * 4 operarios).
Veamos cómo podemos utilizar los ciclos en Python para simplificar la definición de las variables – Eso sí, en lugar de X llamaremos a la variable asignacion, y en lugar de a, b y c, utilizaremos la primera letra de cada parámetro.
# Creamos las variables de asignación
# asignacion[(o, d, t)]: operario 'o' trabaja en el turno 't' el día 'd'.
asignacion = {}
for o in total_operarios:
for d in total_dias:
for t in total_turnos:
asignacion[(o, d, t)] = model.NewBoolVar('turno_n%id%is%i' % (o, d, t))De esta manera, haciendo uso de ciclos, creamos todas las variables de asignación del modelo; así mismo, definimos su naturaleza (NewBoolVar = Variable booleana). De manera que en el caso de que una asignación se efectúe su resultado será «verdadero / True».
La complejidad de un problema de programación de recursos se define por la naturaleza de sus restricciones. Si bien las restricciones acotan el conjunto solución, y por ende los tiempos de procesamiento, la dificultad subyace del modelamiento. Veamos cómo abordar cada una de las restricciones que nos plantea el caso de aplicación.
Cada turno se asigna a un solo operario
La sumatoria de todas las asignaciones efectuadas en un día d, en el turno t, deben ser menores o iguales a 1. Eso restringe la posibilidad de que un mismo turno, en un mismo día, sea asignado a dos operarios diferentes.
Por ejemplo:
X000 + X100 + X200 + X300 <= 1
Esta restricción nos diría que la sumatoria de todas las asignaciones del día 0, para el turno 0, de los operarios 0, 1, 2 y 3; debe ser menor o igual a 1. Es decir que el turno 0, del día 0 no puede ser asignado a más de un operario.
Veamos cómo Python nos puede simplificar esta formulación de restricciones:
# Cada turno es asignado a un operario en el periodo de programación, o no es asignado
for d in total_dias:
for t in total_turnos:
model.Add(sum(asignacion[(o, d, t)] for o in total_operarios) <= 1)Esta restricción bien podría formularse como que la sumatoria deba ser igual a 1. Sin embargo, recordemos que existen un par de turnos no laborales, y por lo tanto estos no deben ser asignados.
En el caso en el que tuviésemos que definir manualmente cada una de estas restricciones, requeriríamos un total de 21 restricciones (7 días * 3 turnos).
Cada operario trabaja como máximo un turno por día
La sumatoria de todas las asignaciones efectuadas en un día d, para el operario o, deben ser menores o iguales a 1. Eso restringe la posibilidad de que un operario, en un mismo día, sea asignado a dos turnos diferentes.
Por ejemplo:
X000 + X001 + X002 <= 1
Esta restricción nos diría que la sumatoria de todas las asignaciones del día 0, para el operario 0, de los turnos 0, 1, y 2; debe ser menor o igual a 1. Es decir que el operario 0, del día 0 no puede ser asignado a más de un turno.
Veamos cómo Python nos puede simplificar esta formulación de restricciones:
# Cada operario trabaja como máximo un turno por día
for o in total_operarios:
for d in total_dias:
model.Add(sum(asignacion[(o, d, t)] for t in total_turnos) <= 1)En el caso en el que tuviésemos que definir manualmente cada una de estas restricciones, requeriríamos un total de 28 restricciones (7 días * 4 operarios).
Restricción del operario aprendiz
De acuerdo al caso de aplicación, el operario aprendiz no pude trabajar el tercer día de la semana, en el turno de la noche. Esto nos permite abordar restricciones de requerimientos puntuales sobre el modelo.
Recordemos que el índice, tanto de operarios, turnos y días, comienza en 0. Por lo tanto, para efectos de la formulación de la restricción, el tercer día de la semana será el día 2 (los siete días de la semana son 0, 1, 2, 3, 4, 5 y 6); y el turno de la noche, será el turno 2 (turnos 0, 1 y 2 / mañana, tarde y noche).
Por otro lado, los operarios también son nombrados de acuerdo a sus índices: 0, 1, 2 y 3. Podemos arbitrariamente elegir el índice del operario aprendiz; en nuestro caso diremos que se trata del operario 0.
#Restricción del operario (o) 1 para trabajar el día (d) 2, en el turno (t) 2
model.Add(asignacion[(0, 2, 2)] != 1)El operador != se utiliza para denotar diferente de, por lo tanto, la restricción indica que la asignación del operario 0, el día 2, en el turno 2, deberá ser diferente de 1; es decir que, al tratarse de una variable booleana, deberá ser Falso = 0.
Restricciones de turnos no programados (mantenimiento y limpieza)
De acuerdo al caso de aplicación, el último día de la semana se programan actividades de mantenimiento y limpieza, y que por lo tanto, solo se trabaja en el turno de la mañana. Por esta razón, debemos excluir a los turnos de la tarde y la noche de la programación (turnos 1 y 2) del último día (día 6).
Siguiendo con nuestras denominaciones algebraicas de ejemplo, tendríamos algo así:
X061 + X161 + X261 + X361 == 0
X062 + X162 + X262 + X362 == 0
Veamos cómo Python nos puede simplificar esta formulación de restricciones:
# Restricción de turnos no programados
model.Add(sum(asignacion[(o, 6, 1)] for o in total_operarios) == 0)
model.Add(sum(asignacion[(o, 6, 2)] for o in total_operarios) == 0)Restricción de turnos mínimos programados
De acuerdo al caso de aplicación, debe programarse una cantidad de 19 turnos laborales. Es decir, la cantidad de turnos diarios (3) * la cantidad de días del programa (7); menos la cantidad de turnos no programados por mantenimiento y limpieza (2).
#Como mínimo deben trabajarse "turnos_laborales"
min_turnos_totales = []
for o in total_operarios:
for d in total_dias:
for t in total_turnos:
min_turnos_totales.append(asignacion[(o, d, t)])
model.Add(sum(min_turnos_totales) >= turnos_laborales)Esta restricción involucra a todas las variables de asignación del modelo, y por lo tanto el uso de ciclos es importante para simplificar el desarrollo de la formulación. Básicamente indica que la sumatoria de todas las variables de decisión (asignación) del modelo (que son booleanas, y para este efecto podemos decir que binarias), debe ser mayor o igual al mínimo de turnos laborales exigidos para programación.
La restricción es 1 sola, pero involucra las 84 variables de asignación.
Restricción de uniformidad en la distribución de turnos
El objetivo de estas restricciones es la de distribuir de la manera más uniforme posible los turnos asignados. En términos prácticos, el caso de aplicación indica que, no puede existir una diferencia mayor a un turno entre las asignaciones de los operarios. Es decir, ningún operario podrá tener asignados dos turnos más que otro operario, por ejemplo.
Para lograr esto es necesario realizar una serie de cálculos intermedios sencillos, con el objetivo de identificar: número de turnos asignables, cantidad mínima de turnos por operario, cantidad máxima de turnos por operario, entre otros.
min_turnos_por_operario = ((turnos * dias) - turnos_no_laborales) // operarios
if ((turnos * dias) - turnos_no_laborales) % operarios == 0:
max_turnos_por_operario = min_turnos_por_operario
else:
max_turnos_por_operario = min_turnos_por_operario + 1
for o in total_operarios:
num_turnos_trabajados = []
for d in total_dias:
for t in total_turnos:
num_turnos_trabajados.append(asignacion[(o, d, t)])
model.Add(min_turnos_por_operario <= sum(num_turnos_trabajados))
model.Add(sum(num_turnos_trabajados) <= max_turnos_por_operario)Lo primero que hicimos fue calcular la parte entera de la fracción entre el número de turnos asignables y los operarios; lo que nos indica la cantidad mínima de turnos por operario. Veamos con un ejemplo:
(turnos * días) – turnos no laborales // operarios
(3 turnos por día * 7 días) – 2 turnos // 4 operarios
(3 * 7) – 2 // 4
19 // 4 = 4 turnos por operario
Esto indica que existe la posibilidad de asignar al menos 4 turnos por cada operario. Lo siguiente que se debe considerar es la cantidad máxima de turnos por operario.
En el caso en el cual la cantidad que resulte de dividir el número de turnos asignables entre el número de operarios sea entera sin decimales, esto indicaría que la distribución de los turnos puede realizarse en partes iguales, y por lo tanto la cantidad máxima de turnos por operario será equivalente a la cantidad mínima de turnos por operario.
En los casos en los que esto no ocurra, la cantidad máxima de turnos por operario será equivalente a la cantidad mínima de turnos por operario más 1. Recordemos que la restricción nos indica que la diferencia entre asignaciones de turnos a operarios no puede ser mayor de un turno.
Por todo lo demás, las restricciones de este paso consisten en establecer que la cantidad de turnos asignados por operario deberá ser mayor que la cantidad mínima de turnos por operario y deberá ser menor que a cantidad máxima de turnos por operario.
# Creal (invocar) el solucionador y resolver
solver = cp_model.CpSolver()
solver.parameters.linearization_level = 0
# Enumerar las posibles soluciones
solver.parameters.enumerate_all_solutions = TrueEste paso consiste en configurar el formato de salida de las soluciones posibles. De forma arbitraria hemos determinado que se impriman las primeras 2 soluciones (solution_limit), de tal manera que el formato de salida tendrá la siguiente estructura:
class OperariosParcialesSolucion(cp_model.CpSolverSolutionCallback):
"""Print intermediate solutions."""
def __init__(self, asignacion, operarios, dias, turnos, limit):
cp_model.CpSolverSolutionCallback.__init__(self)
self._asignacion = asignacion
self._operarios = operarios
self._dias = dias
self._turnos = turnos
self._solution_count = 0
self._solution_limit = limit
def on_solution_callback(self):
self._solution_count += 1
print('Solución %i' % self._solution_count)
for d in range(self._dias):
print('Día %i' % d)
for o in range(self._operarios):
is_working = False
for t in range(self._turnos):
if self.Value(self._asignacion[(o, d, t)]):
is_working = True
print(' Operario %i trabaja en el turno %i' % (o, t))
if not is_working:
print(' Operario {} no trabaja'.format(o))
if self._solution_count >= self._solution_limit:
print('Detenga la búsqueda después de %i soluciones' % self._solution_limit)
self.StopSearch()
def solution_count(self):
return self._solution_count
# Muestra las primeras 2 soluciones.
solution_limit = 2
solution_printer = OperariosParcialesSolucion(asignacion, operarios, dias, turnos,
solution_limit)Por último, nos queda invocar al solucionador, y configurar algunos datos estadísticos para enriquecer las salidas del modelo.
solver.Solve(model, solution_printer)
# Estadísticas.
print('\nEstadísticas')
print(' - conflictos : %i' % solver.NumConflicts())
print(' - ramas de búsqueda : %i' % solver.NumBranches())
print(' - tiempo de solución : %f s' % solver.WallTime())
print(' - soluciones encontradas: %i' % solution_printer.solution_count())Al ejecutar el programa completo, tendremos la siguiente salida:
Detenga la búsqueda después de 2 soluciones
Estadísticas
– conflictos : 973
– ramas de búsqueda : 1730
– tiempo de búsqueda : 0.044052 s
– soluciones encontradas: 2
Hemos formulado un modelo con 84 variables de decisión, 55 restricciones y algunos cálculos intermedios. Podemos observar cómo el modelo ha logrado encontrar soluciones que satisfacen las restricciones planteadas (formuladas). Del mismo modo, podemos observar el tiempo en el cual ha logrado el solucionador hallar la cantidad de soluciones solicitadas (fracciones de segundo).
Es interesante percibir las bondades de este tipo desarrollos, y considerar las posibilidades de aplicación en otros campos diferentes a la programación de empleados; teniendo en cuenta la flexibilidad de la programación basada en restricciones, la potencia de los solucionadores y la capacidad de procesamiento de los equipos en la actualidad.
El código completo de este desarrollo lo puedes encontrar en nuestro cuaderno: Programación de empleados.
En una pequeña comunidad agrícola en Michoacán, México, un niño llamado José Hernández soñaba con…
Sábado por la mañana, Robert acaba de acompañar a su mujer a su clase de…