Soluciones de programación de personal algorítmico

Question

En un nivel bruto, el problema es simple: programar un ejército de personal para cobertura de una persona por día, en cualquier día el personal se divide en 3 grupos, cada personal tiene un requisito de vacaciones , cada personal tiene como máximo 2 turnos por semana, etc.

Odio hacer esto manualmente, como se ha hecho en mi organización durante siglos. Me encantaría hacer algo genial como los algoritmos genéticos (por ejemplo, [1] http://www.sersc.org/journals/IJAST/vol14/1.pdf).

¿Hay alguna alternativa de código abierto/libre confiable por ahí? Esto también suena como un problema de optimización, ¿puedo arrancar C++, R, etc. para conectarlo a alguna biblioteca de optimización para esto?

gracias

Answer 1

Puede probar OptaPlanner (anteriormente se llamaba Drools Planner), está basado en Java y código abierto.

Answer 2

Esto es un problema de optimización. Se conoce como un problema de Programación, extrañamente. :-D Dependiendo del tamaño de los datos, puede que tenga que recurrir a la Metaheurística, como algoritmos genéticos, optimización de enjambre de hormigas, etc., pero yo comenzaría aquí elaborando su propia heurística basada en reglas.

Básicamente, defina reglas como asociaciones entre cosas (la persona A no puede estar simultáneamente de vacaciones y en el trabajo), o condiciones en el programa (solo tres personas en un momento determinado). Luego, cree un cronograma e inserte todo su personal uno por uno. Si en la inserción se rompe una regla, entonces no inserte y elija otro personal.

Esto debería, si lo haces bien, proponer un horario válido, pero menos que óptimo, y entonces puedes hacer cosas geniales como definir operadores (intercambio, movimiento, 3-intercambio), lo que dará usted un barrio (todos los horarios válidos que se pueden alcanzar mediante la aplicación de un operador). A continuación, puede elegir el mejor horario en el vecindario y repetir. Este es el descenso del vecindario. Pero hay muchos métodos basados ​​en vecindarios para elegir. Creo que el recocido simulado es bueno cuando se aplica a problemas de programación.

Answer 3

Como solo hay una persona por día, esto parece que podría configurarse como un problema de programación binario/entero. Hay muchos paquetes que hacen programación entera. La parte difícil de estos problemas, independientemente del método que decida utilizar para resolverlos, es encontrar una forma concisa de especificar las limitaciones del problema. En este caso, cuáles son exactamente los requisitos de vacaciones, etc.

Answer 4

Puede que también esté interesado en frameworks de programación de restricciones, muchos de los cuales son de código abierto como Choco (Java), Gecode (C++) y otros que también se han usado para este tipo de problemas, aunque estoy de acuerdo con ravloony podría valer la pena verificar si un algoritmo en el estilo que mencionó podría ser el truco para el problema que describió.