Se nos dan pilas que contienen "elementos" de diferente color y una máquina que puede procesar múltiples elementos del mismo color de una sola vez. En cada paso, podemos eliminar un elemento de la parte superior de cada pila y ponerlo en nuestra máquina (de manera efectiva, la máquina puede procesar como máximo elementos en un solo paso; para que eso suceda, todas las pilas deben tener elementos del mismo color encima). El objetivo es procesar todos los artículos en un tiempo mínimo.
Entrada de ejemplo:
Una posible solución es un algoritmo codicioso: en cada paso, simplemente tome tantos elementos como sea posible y mételos todos en la máquina. Desafortunadamente, el algoritmo codicioso no es óptimo: produce el siguiente programa para la entrada de ejemplo:
El horario óptimo es el siguiente:
Planeo ir con alguna forma de búsqueda de espacio de estado, pero ¿tal vez haya un enfoque más eficiente y específico para cada problema? Se aprecian enlaces a literatura relevante.
fuente
Respuestas:
Su problema es equivalente a la Supersecuencia común más corta (SCS) y fue considerado en por el nombre Programación en máquinas por lotes con restricciones de precedencia como cadenas y compatibilidades . Si los elementos del problema son del mismo color, dicho problema está en P y puede resolverse en .O ( n 2 ) [ 2 ][ 1 ] O ( n2) [ 2 ]
Lo que concierne a la aproximabilidad de una buena fuente es Un compendio de problemas de optimización de NP .
Los últimos resultados en SCS se pueden encontrar en .[ 3 , 4 ]
Para ver algoritmos prácticos, consulte cuyo autor declara que "el híbrido MA-BS es una técnica actual de vanguardia para el SCSP ".[ 6 ][ 5 ] [6]
fuente
fuente