Programación de una sola máquina
La programación de una sola máquina o la programación de un solo recurso es un problema de optimización en la informática y la investigación de operaciones . Tenemos n trabajos J 1 , J 2 , ..., J n de tiempos de procesamiento variables, que deben programarse en una sola máquina, de manera que optimice un objetivo determinado, como el rendimiento .
La programación de una sola máquina es un caso especial de programación de máquinas idénticas , que en sí misma es un caso especial de programación óptima de trabajos . Muchos problemas, que son NP-difíciles en general, se pueden resolver en tiempo polinomial en el caso de una sola máquina. [1] : 10–20
En la notación estándar de tres campos para problemas de programación de trabajos óptimos , la variante de una sola máquina se indica con 1 en el primer campo. Por ejemplo, " 1|| " es un problema de programación de máquina idéntico sin restricciones, donde el objetivo es minimizar la suma de los tiempos de finalización.
El problema de minimización de makepan 1|| , que es un objetivo común con múltiples máquinas, es trivial con una sola máquina, ya que elmakespan siempre es idéntico. Por ello, se han estudiado otros objetivos: [2]
Se han aplicado muchas técnicas de solución para resolver problemas de programación de una sola máquina. Algunos de ellos se enumeran a continuación.