utilizas turnos transporte trabajo son simplex qué programar problema para optimización optimizacion necesarias modelo metodo librerías función declarar asignacion algoritmo algorithm discrete-mathematics mathematical-optimization linear-programming

algorithm - turnos - qué función utilizas para declarar un problema de optimización en python



Qué algoritmo para asignar turnos(problema de optimización discreta) (9)

Estoy desarrollando una aplicación que asigna cambios de manera óptima a las enfermeras en un hospital. Creo que este es un problema de programación lineal con variables discretas y, por lo tanto, probablemente NP-hard:

  • Para cada día, a cada enfermera (alrededor de 15-20) se le asigna un turno
  • Hay un pequeño número (alrededor de 6) de diferentes turnos
  • Existe un número considerable de restricciones y criterios de optimización, ya sea con respecto a un día o con respecto a un emplyoee, por ejemplo:
    • Debe haber un número mínimo de personas asignadas a cada turno todos los días
    • Algunos turnos se superponen para que esté bien tener una persona menos en el turno temprano si hay alguien haciendo turno intermedio
    • Algunas personas prefieren el turno temprano, algunas prefieren el turno de tarde, pero se requiere un mínimo de cambios de turno para obtener el salario por turno más alto.
    • No está permitido que una persona trabaje tarde un turno y un turno temprano al día siguiente (debido a las regulaciones mínimas de tiempo de descanso)
    • Cumplir con la duración de la semana laboral asignada (diferente para diferentes personas)
    • ...

Entonces, básicamente, hay un gran número (aout 20 * 30 = 600) variables que cada uno puede tomar un pequeño número de valores discretos.

Actualmente, mi plan es usar un algoritmo Min-conflict modificado

  • comenzar con asignaciones aleatorias
  • tener una función de acondicionamiento físico para cada persona y cada día
  • seleccione la persona o día con el peor valor de aptitud
  • seleccione al azar una de las asignaciones para ese día / persona y ajústelo al valor que dé como resultado el valor de aptitud óptimo
  • repita hasta que se alcance un número máximo de iteraciones o no se encuentre ninguna mejora para el día / persona seleccionado

Alguna mejor idea? Estoy algo preocupado de que se quede estancado en un óptimo local. ¿Debo usar alguna forma de recocido simulado ? O considere no solo los cambios en una variable a la vez, sino específicamente los cambios de turnos entre dos personas (el componente principal en el algoritmo manual actual). Quiero evitar adaptar el algoritmo a las restricciones actuales ya que esas pueden cambiar.

Editar: no es necesario encontrar una solución estrictamente óptima; la lista actualmente se hace de forma manual, y estoy bastante seguro de que el resultado es considerablemente subóptimo la mayor parte del tiempo; no debería ser difícil de superar. Los ajustes a corto plazo y las anulaciones manuales también serán definitivamente necesarios, pero no creo que esto sea un problema; Marcar las asignaciones pasadas y manuales como "arregladas" debería simplificar la tarea reduciendo el espacio de la solución.

Este es un problema difícil de resolver bien. Ha habido muchos trabajos académicos sobre este tema, particularmente en el campo de Investigación de Operaciones - vea, por ejemplo , los documentos de calificaciones de las enfermeras 2007-2008 o simplemente google "investigación de operaciones de búsqueda de enfermeras". La complejidad también depende de aspectos tales como: cuántos días resolver; qué tipo de "solicitudes" puede hacer la enfermera; es la lista "cíclica"; ¿es un plan a largo plazo o necesita manejar una "reparación" de asignación a corto plazo, como enfermedades, permutas, etc., etc.

El algoritmo que describes es un enfoque heurístico . Puede encontrar que puede ajustarlo para que funcione bien para una instancia particular del problema, pero tan pronto como se modifique "algo" puede que no funcione tan bien (por ejemplo, optima local, mala convergencia).

Sin embargo, dicho enfoque puede ser adecuado dependiendo de las necesidades particulares de su negocio, por ejemplo, qué tan importante es obtener la solución óptima , si el esquema del problema que describe espera permanecer igual, cuál es el ahorro potencial (dinero y recursos), qué tan importante es la percepción de la enfermera sobre la calidad de sus listas, cuál es el presupuesto para este trabajo, etc.

Una cosa que puedes hacer es tratar de buscar simetrías en el problema. Por ejemplo, ¿puede tratar a todas las enfermeras como equivalentes para los fines del problema? Si es así, solo necesita considerar a las enfermeras en un orden arbitrario: puede evitar considerar soluciones como que cualquier enfermera i se programe antes que cualquier enfermera j donde i > j . (¿Dijo que las enfermeras individuales prefieren los turnos de trabajo, lo que contradice este ejemplo, aunque tal vez ese sea un objetivo menos importante?)

Programación dinámica a la Bell? Parece que hay un lugar para eso: superposiciones de subproblemas, subestructuras óptimas.

Resolví recientemente un problema de asignación de turno para una gran planta de fabricación. Primero tratamos de generar cronogramas puramente aleatorios y devolver cualquiera que haya pasado la prueba is_schedule_valid - el algoritmo de is_schedule_valid . Esto fue, por supuesto, lento e indeterminado.

A continuación probamos los algoritmos genéticos (como sugirió), pero no pudimos encontrar una buena función de aptitud que se cerrara sobre cualquier solución viable (porque el cambio más pequeño puede hacer que todo el programa sea CORRECTO o INCORRECTO, sin puntos para casi).

Finalmente elegimos el siguiente método (¡que funcionó muy bien!):

  1. Aleatorice el conjunto de entrada (es decir, trabajos, turno, personal, etc.).
  2. Crea una tupla válida y agrégala a tu calendario provisional.
  3. Si no se puede crear una tupla válida, revertir (e incrementar) la última tupla añadida.
  4. Pase el cronograma parcial a una función que pruebe could_schedule_be_valid , es decir, ¿podría este cronograma ser válido si las tuplas restantes se llenaran de una manera posible?
  5. Si !could_schedule_be_valid , simplemente retrotrae (e incremente) la tupla agregada en (2).
  6. Si schedule_is_complete , return schedule
  7. Ir a (2)

Incrementalmente construyes un cambio parcial de esta manera. El beneficio es que algunas pruebas para un horario válido se pueden hacer fácilmente en el Paso 2 (pruebas previas), y otras deben permanecer en el Paso 5 (pruebas posteriores).

Buena suerte. Perdimos días probando los primeros dos algoritmos, pero obtuvimos el algoritmo recomendado que genera programaciones válidas al instante en menos de 5 horas de desarrollo.

Además, admitimos la fijación previa y la fijación posterior de asignaciones que el algoritmo respetaría. Simplemente no aleatoriza esas ranuras en el Paso 1. Descubrirá que las soluciones no tienen que ser ni cerca de lo óptimo. Nuestra solución es O (N * M) como mínimo, pero se ejecuta en PHP (!) En menos de medio segundo para toda una planta de fabricación. La belleza está en descartar rápidamente los malos horarios utilizando una buena prueba de could_schedule_be_valid .

A las personas que están acostumbradas a hacerlo manualmente no les importa si lleva una hora; simplemente saben que ya no tienen que hacerlo manualmente.

Umm, ¿sabías que algunos solucionadores de ILP hacen un buen trabajo? Pruebe AIMMS, Mathematica o el kit de programación de GNU. 600 Variables es, por supuesto, mucho más de lo que el teorema de Lenstra resolverá fácilmente, pero a veces estos solucionadores de ILP tienen un buen manejo y en AIMMS, puede modificar un poco la estrategia de ramificación. Además, hay una aproximación 100% realmente rápida para los ILP.

Micro,

No sé si alguna vez obtuve una buena respuesta a esto, pero estoy bastante seguro de que la programación restrictiva es el boleto. Mientras que una AG podría darle una respuesta, CP está diseñado para darle muchas respuestas o decirle si no hay una solución factible. Una búsqueda en "programación de restricciones" y programación debería traer mucha información. Es un área relativamente nueva y los métodos de CP funcionan bien en muchos tipos de problemas donde los métodos de optimización tradicionales se atascan.

Utilizando la programación de CSP, hice los programas para la asignación automática de shits. p.ej:

  1. Sistema de 2 turnos: probado para más de 100 enfermeras, horizonte temporal de 30 días, más de 10 reglas
  2. Sistema de 3 turnos: probado para más de 80 enfermeras, horizonte de tiempo de 30 días, más de 10 reglas
  3. Sistema de 3 turnos, 4 equipos: probado para 365 días de horizonte, más de 10 reglas,

y un par de sistemas similares. Todos ellos fueron probados en mi PC de casa (1.8GHz, dual-core). Los tiempos de ejecución siempre fueron aceptables, es decir. para 3 / tomó alrededor de 5 minutos y 300MB de RAM.

La parte más difícil de este problema fue seleccionar un solucionador apropiado y una estrategia de resolución adecuada.

Creo que deberías usar un algoritmo genético porque:

También eche un vistazo a: una pregunta similar y otra