next up previous contents
Siguiente: Problemas con un solo Un nivel arriba: Problemas con varios procesadores Anterior: Nociones básicas

Problemas

Asignación a varios procesadores (Multiprocessor scheduling):


Instancia:
\begin{pagi}{34}Un conjunto $A$\space finito de tareas, un vector de duraciones ... ...un n\'umero $m$\space de procesadores y un punto de saturaci\'on $S$ .\end{pagi}
Solución:
\begin{pagi}{34}$\left\{\begin{array}{ll} 1 &\mbox{\rm si existe una asignaci\'... ...ace de $A$ , } \\ 0 &\mbox{\rm en otro caso. } \end{array}\right.$\end{pagi}



Es completo-NP pues PARTITION se reduce a él. En efecto, una instancia de PARTITION corresponde a una de ``Multiprocessor scheduling'' con m=2 y $D=\frac{1}{2}\sum_{a\in A}d(a)$.


Otro problema completos-NP es el siguiente: Asignación con restricción en las precedencias (Precedence constrained scheduling):


Instancia:
\begin{pagi}{34}Un conjunto $A$\space finito de tareas, cada una con una duraci\... ...turaci\'on $S$\space y una relaci\'on de orden \lq\lq $\preceq$ '' en $A$ .\end{pagi}
Solución:
\begin{pagi}{34}$\left\{\begin{array}{ll} 1 &\mbox{\rm si hay asignaci\'on con ... ...recedencias, } \\ 0 &\mbox{\rm en otro caso. } \end{array}\right.$\end{pagi}




Guillermo Morales-Luna
2000-07-10