Programación de trabajos con un problema de cuello de botella

11

Dada n empleos J1,J2,...,Jn , cada trabajo requiere Ti>0,TiN tiempo para completarse.

Cada trabajo debe ser preprocesado y procesado posteriormente por una sola máquina M que puede manejar solo 1 trabajo a la vez y ambas fases requieren 1 unidad de tiempo. Después de ser preprocesado, el trabajo Ji se envía a una máquina con potencia ilimitada (que puede manejar en paralelo un número ilimitado de trabajos) y estará listo a tiempo Ti , luego se debe enviar ( inmediatamente ) a la máquina M de nuevo para el procesamiento posterior.

ingrese la descripción de la imagen aquí

El problema de decisión asociado es:

Entrada: los tiempos de procesamiento Ti>0,TiN de N trabajos, un entero K2N
Pregunta: ¿podemos procesar todos los trabajos a tiempo K utilizando el modelo de "cuello de botella" anterior?

¿Tiene este problema un nombre?
¿Cuál es su complejidad? (¿está en P o es NP -completo?)


NP

  • el tiempo de procesamiento previo / posterior es constante (1 unidad de tiempo)
  • Tan pronto como se complete el trabajo, debe ser procesado inmediatamente (el modelo UMFT permite retrasos)

No encontré la prueba de Kern y Nawijn en línea, por lo que todavía no sé si las restricciones anteriores cambian la dificultad del problema.

Finalmente, puede pensar todo el proceso como un robot de cocción único con un gran horno; el robot puede preparar diferentes tipos de alimentos de uno en uno (todos requieren el mismo tiempo de preparación), ponerlos en el horno y, tan pronto como se cocinen, debe sacarlos del horno y agregar algunos ingredientes fríos ... el " problema del robot cocinero " :-)

Vor
fuente
Agradable. Tengo la sensación de que el cuello de botella debería simplificar las cosas.
Raphael
k2nn
kk
kk2nk<2n
1
Su pregunta es NP-complete en "Minimizar Makespan en un taller de flujo de dos máquinas con retrasos y operaciones de unidad de tiempo es NP-Hard" por W. Yu, H. Hoogeveen y JK Lenstra (2004), quienes también dicen que Kern y Nawijn no lo resolvieron. Cito: "El estado de complejidad del caso especial con tareas de tiempo de procesamiento de la unidad ha estado abierto para retrasos mínimos y exactos. El estado de complejidad del que tiene retrasos mínimos se plantea como una pregunta abierta por Kern y Nawijn (1991)".
Peter Shor

Respuestas:

5

Esto se parece al llamado modelo de programación maestro-esclavo introducido por Sahni . En particular, su problema se enmarca en los sistemas Single-Master Master-Slave. Puedes distinguir varios casos:

1) Si no agrega ninguna restricción adicional en el orden de ejecución del trabajo (como en su caso), el problema se llama problema de tiempo mínimo de finalización sin restricciones (UMFT) y se ha demostrado que es NP-hard;

O(nlogn)

NPP

Los problemas relacionados adicionales son:

3) Postproceso de orden inverso: para cualquier permutación de preprocesamiento dada, , es posible construir un programa de orden inverso, denominado programa de orden inverso canónico (CROS). Dada una permutación de preprocesamiento , el CROS correspondiente es único. Es fácil establecer que cada horario mínimo de orden inverso de tiempo de finalización (ROMFT) es un CROS.σσ

4) restricción de no esperar en el proceso:

a) [MFTNW] Minimice el tiempo de finalización sujeto a la restricción de no esperar en el proceso; b) [OP-MFTNW] Esta es la versión de MFTNW para preservar el orden. Es decir, minimizar el tiempo de finalización sujeto a las restricciones de no esperar en el proceso y preservar el orden; c) [RO-MFTNW] Minimice el tiempo de finalización sujeto a las restricciones sin orden de espera y de orden inverso.

Los problemas y son NP-duros, mientras que admite una solución de tiempo polinomial.abc

Detalles adicionales en el Manual de programación , capítulo 17.

Massimo Cafaro
fuente
Gracias, es similar (no tengo el libro pero encontré este documento ). Lo leeré detenidamente más tarde. Solo una pregunta después de leer su introducción, parece que usa esclavos (después del preprocesamiento), pero en mi modelo hay un número ilimitado de esclavos; ¿es correcto?. Leeré la prueba de la dureza NP de UMFT y veré si usa la hipótesis de que el número de esclavos es limitado. n
Vor
Sahni demostró que siempre puede usar exactamente esclavos: "Los procesadores disponibles se dividen en dos categorías: maestro y esclavo. Si denota el número de trabajos, entonces ningún programa puede usar más que esclavos. Por lo tanto, podemos suponer que hay son exactamente esclavos ". Por lo tanto, su problema se traduce fácilmente a esta configuración: simplemente descarta y no utiliza los esclavos adicionales disponibles en la máquina con esclavos ilimitados. nnnn
Massimo Cafaro
2
Me parece que la prueba de dureza NP de Sahni utiliza críticamente el hecho de que los tiempos de preprocesamiento y posprocesamiento pueden ser arbitrarios. El problema del OP tiene todos estos tiempos iguales a 1. ¿Funciona la prueba en este caso?
Peter Shor
Vor, el documento al que se refiere es solo un extracto con muchas partes faltantes del capítulo 17 del libro. Sin embargo, la parte faltante le impedirá comprender correctamente (notación faltante, etc.).
Massimo Cafaro
Peter, no estoy seguro y necesito verificar la prueba; si solo requiere tiempos previos y posteriores al procesamiento> 0, debe incluir el problema del OP cuando se considera el problema del tiempo mínimo de finalización sin restricciones. Por el mismo razonamiento, esto debería conducir al algoritmo de tiempo polinomial para el problema del tiempo mínimo de finalización de la orden que preserva. O(nlogn)
Massimo Cafaro