Problema de programación de la máquina

Question

tengo un problema combinatorio como tal:

Le dan N testers.

Cada comprobador es uno de M diferentes tipos.

Cada comprobador se puede configurar para usar una de las diferentes configuraciones de P. .

Tienes L lotes de productos para probar,

Cada producto sólo puede ser probado en el tipo de pruebas específicas,

Cada producto sólo puede ser probada por Tester configurado con Configs específicos. Algunas de las configuraciones se pueden aplicar a múltiples productos. Cualquier probador puede cambiar su configuración durante la producción, pero cada cambio en la configuración del probador incurrirá en tiempo adicional U. Cada lote tiene un tamaño de lote que determina su tiempo de prueba, Q.

Ahora tengo que sacar mucho algoritmo de programación de modo que el tiempo para finalizar la prueba de todos los lotes sea mínimo.

¿Cuáles son los mejores enfoques para hacer frente a este tipo de problema?

Answer 1

Puede ser modelado como un problema Job-Shop (JSP) con tiempos de preparación en el que el tamaño del trabajo es 1. Por desgracia se pone bastante difícil encontrar un óptimo cuando el número de empleos> 10.

Hay muchos gratuitos las implementaciones de solucionador que contienen Job-Shop como problema de muestra: Si está usando C++, Gecode es bueno. Si puede elegir libremente, ECLiPSe Prolog contiene el código fuente del JSP.

Si se puede hacer con una buena solución (en lugar de una óptima), se sugiere emplear un algoritmo voraz (para el JSP, algoritmos codiciosos dan soluciones típicamente dentro del 10% de la óptima - que tenía alguna experiencia con esta). Voy a pensar en uno y volver aquí (el problema es lo que se llama 'restricciones de tiempo de configuración', es decir, las restricciones que provienen de cambiar la configuración del probador).