¿Qué algoritmo(s) puede(n) resolver este problema de programación con restricciones?

Question

Necesito resolver un problema de afectación laboral y me gustaría encontrar algoritmos preferentemente eficientes para solucionar este problema.

Digamos que hay algunos trabajadores que pueden realizar varios tipos de tareas.También tenemos un conjunto de tareas que deben realizarse cada semana.Cada tarea lleva algo de tiempo.Cada tarea debe ser realizada por alguien.Cada trabajador debe trabajar entre N y P horas semanales.

Esta primera parte del problema parece ser un buen candidato para un algoritmo de programación con restricciones.

Pero aquí está la complicación:Debido a que un trabajador puede realizar diferentes tareas, también puede tener preferencias (o deseos).Si se quieren satisfacer todos los deseos de todos, no hay solución al problema (demasiadas limitaciones).

Entonces necesito un algoritmo para resolver este problema.No quiero reinventar la rueda si ya existe la rueda perfecta.

El algoritmo debe ser justo (si se puede definir esta palabra), por lo que, por ejemplo, debería poder agregar una restricción como "intentar satisfacer al menos un deseo por persona".No estoy seguro de que este problema pueda resolverse mediante los métodos de jerarquías de restricciones que se describen aquí: Jerarquías de restricciones.De hecho, no estoy seguro de que la "justicia" y los deseos puedan expresarse mediante restricciones válidas para esta categoría de algoritmos.

¿Existe algún experto en programación de restricciones que pueda darme algunos consejos?¿Necesito desarrollar una nueva rueda con algunas heurísticas en lugar de utilizar algoritmos CP eficientes?

Gracias !

Answer 1

Su problema es lo suficientemente compleja que una solución general probablemente requerirá la formulación como un lineal entero problema. Si por el contrario usted es capaz de relajar ciertos requisitos, es posible que pueda utilizar un método más sencillo. Por ejemplo, bipartita juego le permitirá programar varios trabajadores para múltiples puestos de trabajo, e incluso puede manejar preferencias, pero no sería capaz de hacer cumplir las restricciones generales 'justicia'. Véase, por ejemplo este relacionados para cuestionar . Vertex coloración tiene algoritmos eficientes para hacer cumplir las restricciones de separación de trabajo.

Los otros críticos han mencionado simplex y taller de trabajo programación. Simplex es un algoritmo de optimización - que atraviesa un espacio de soluciones que buscan maximizar alguna función objetivo. La formulación de la función objetivo sin duda se puede hacer, pero no es trivial. Clásico taller de trabajo de programación, como coincidencia bipartita, puede modelar algunos aspectos de su problema, pero no todos. No hay restricciones de precedencia, por ejemplo. Hay versiones extendidas que pueden manejar algunas limitaciones, como por ejemplo la colocación de los límites de tiempo en las tareas.

Si está interesado en las implementaciones existentes, el NetworkX biblioteca de Python tiene una implementación de este juego algoritmo. Un ejemplo de un programa de horarios de código abierto que puede ser de interés es Tablix .

Answer 2

He hecho de horarios, que se puede considerar una forma de programación con restricciones. Usted tiene restricciones duras (inviolables) y restricciones blandas (como las preferencias de intervalo).

Lineal programación entera por lo general se vuelve inútil después de más de 30 variables, y esto también se puede decir de una cara.

Fue optimizaciones específicas de dominio mínimas de algoritmos heurísticos que se encontró una solución.

Los algoritmos heurísticos utilizados fueron simmulated recocido , algoritmos genéticos , metaheurístico algoritmos y similar, pero al final el mejor resultado fueron proporcionados por un dominio de "inteligente" personalizado codiciosos algoritmo de búsqueda .

Básicamente, es posible obtener algunos resultados decentes con una de las heurísticas aquí, pero el problema principal es ser capaz de discernir cuando se overconstrained un problema.

Una gran herramienta de código abierto para la investigación es el HeuristicLab .

Answer 3

Estoy de acuerdo con lo que se han propuesto aquí. Sin embargo, MIP (problemas de Programación Entera Mixta) de tamaño muy grande (mucho más allá de 30 variables!) Están prácticamente resueltos hoy en día gracias a los códigos comerciales (Xpress, CPLEX, Gurobi) o de código abierto (Coin-O / CBC). Por otra parte, lenguajes de modelado de fantasía tales como OPL Studio, GAMS, AMPL, Flop ... permiten escribir fácilmente modelos matemáticos en lugar de utilizar las API.

Puede tomar ventaja de servidor de NEOS ( http: //neos.mcs .anl.gov / neos / solucionadores / index.html ) a tratar muy diferentes esaily MIP disponibles. Usted envía su modelo en formato AMPL. Aunque AMPL viene como una versión limitada libre, NEOS puede manejar casos ilimitadas.

Existen lenguajes de modelado también para CP (COMET / OPL Studio) y la búsqueda local (COMET).

No dude en ponerse en contacto conmigo a través de mi página web www.rostudel.com ( 'contacto' página)

David

Answer 4

Esto suena como taller de trabajo de programación .