Transformación de gráficos restringida en las aplicaciones de programación

Question

Estoy trabajando en una aplicación de programación de trabajos interactiva. Dado un conjunto de recursos con los perfiles de capacidad/disponibilidad correspondientes, un conjunto de trabajos para ejecutar sobre estos recursos y un conjunto de restricciones que determinan la secuencia de trabajos y los tiempos de inicio/finalización más tempranos/más recientes para los trabajos. Quiero permitir al usuario mover manualmente trabajos alrededor. Básicamente, quiero que el usuario pueda "agarrar" un nodo de la red de trabajo y arrastrarlo hacia delante/atrás en el tiempo sin violar ninguna de las restricciones.

La imagen muestra una configuración de ejemplo simple. El trabajo triangular al final denota el último tiempo de finalización para todos los trabajos, las líneas de conexión entre trabajos imponen un orden en los trabajos y las barras grises/verdes denotan disponibilidad de recursos y carga.

Puede arrastrar cualquiera de los trabajos para comprimir el programa. Tenga en cuenta que los trabajos cambiarán de longitud debido a los diferentes perfiles de capacidad.

He implementado un algoritmo de ad-hock que funciona. Sin embargo, todavía hay casos en los que fallará y violará algunas limitaciones. Sin embargo, dado que el horario de trabajo en taller es un campo bien investigado con muchos algoritmos y heurísticas para encontrar una solución óptima (o bastante buena) para el problema general NP-difícil, estoy pensando que las soluciones deberían existir para mi subconjunto más fácil. He analizado temas de programación de restricciones e incluso soluciones basadas en la física (cuerpos rígidos conectados mediante uniones estáticas) pero hasta ahora no he podido encontrar nada adecuado. ¿Alguna sugerencia/punteros/consejos/palabras clave de búsqueda para mí?

Answer 1

Probablemente podría alterar el algoritmo de propagación de restricciones de Waltz para hacer frente a las restricciones cambiantes y descubrir rápidamente si una solución dada es válida. Yo no tengo una referencia a mano, pero esto le podría apuntar en la dirección correcta: http://www.sciencedirect.com/science?_ob=ArticleURL&_udi=B6TYF-41C30BN-5&_user=809099&_rdoc=1&_fmt=&_orig=search&_sort=d&_docanchor=&view=c&_searchStrId=1102030809&_rerunOrigin=google&_acct=C000043939&_version=1&_urlVersion=0&_userid=809099&md5=696143716f0d363581a1805b34ae32d9

Answer 2

le recomiendo que eche un vistazo a Mozart Oz, si sus ofertas problema únicamente con números enteros. Oz tiene soporte excelente para la especificación, inferencia y optimización de restricción de dominio finito . En su caso normalmente tendría que hacer lo siguiente:

1. especificar sus restricciones de una manera declarativa. En esto, debería especificar todas las variables y sus dominios (digamos V1: 1 # 100, significa variable V1 puede tomar valores en el rango de 1-100). Algunas variables pueden tener valores directamente, digamos V1: 99. Además, debe especificar todas las restricciones en las variables.

2. Pida al sistema una solución: cualquier solución que satisfaga las restricciones o una solución óptima. Luego mostraría esta solución en la interfaz de usuario.

3. Digamos que el usuario cambia el valor de una variable, puede ser el inicio de una tarea. Ahora puede ir al paso 1 para publicar el problema en el Oz Solver. Esta vez, resolver el problema probablemente no tomará tanto tiempo como antes, ya que todas las variables ya están creadas.

   Puede ser que el usuario haya elegido un valor incoherente. En ese caso , el solucionador devuelve nulo. Luego, puede llevar la IU a la solución anterior .

Si Oz se adapte a su necesidad y te gusta el idioma, entonces es posible que desee escribir una restricción solucionador como un servidor que escucha en un socket. De esta manera, puede mantener el solucionador de restricciones separado del resto de su código, incluyendo la IU.

Espero que esto ayude.

Answer 3

¿Ha considerado utilizar un motor de programación lineal entera (como lp_solve)? Es una buena opción para programar aplicaciones.

Answer 4

votaría a favor de la programación con restricciones por varias razones:

1) CP rápidamente le dirá si no hay un horario que satifies sus limitaciones

2) Parecería que se quiere dar los usuarios son una solución factible para empezar, pero les permite manipular trabajos para mejorar la solución. CP también es bueno en esto.

3) Un enfoque MILP suele ser complejo y difícil de formular y tienes que crear artificialmente una función objetivo.

4) CP no es tan difícil de aprender, especialmente para programadores experimentados: realmente proviene más de la comunidad de la informática que los investigadores de operaciones (como yo).

Buena suerte.