Siguiente: Problemas Un nivel arriba: Problemas con un solo Anterior: Problemas con un solo

Nociones básicas

En un proceso de asignación de tareas con un solo procesador, utilizaremos los conceptos y la notación siguientes:

• Un conjunto finito de tareas: $A=\{a_1,\ldots,a_n\}$.
• Duración (de ejecución) de cada tarea, $\forall a\in A: d(a)\in \mbox{\bf Z}^+$.
• Momento de ``lanzamiento'' de cada tarea, $\forall a\in A: r(a)\in \mbox{\bf Z}^+$.
• Un instante de saturación (deadline) en la realización de cada tarea, $\forall a\in A: s(a)\in \mbox{\bf Z}^+$.
• Una asignación factible para A es una función $\sigma: A\rightarrow N$ tal que, para toda tarea $a\in A$:

  1.

  $r(a)\leq \sigma(a)$: el inicio de cada tarea no puede ser anterior a su momento de lanzamiento,

  2.

  $\sigma(a)+d(a)\leq s(a)$: el inicio más la duración no debe exceder el instante de saturación,

  3.

  $\forall b\in A: b\not=a\Rightarrow\left\{\begin{array}{rcl} \sigma(b)+d(b) &\l... ... \\ &\mbox{\rm\'o}& \\ \sigma(a)+d(a) &\leq& \sigma(b) \end{array}\right.$: Dos tareas distintas no pueden traslapar sus ejecuciones.

• Sea ``$\preceq$'' una relación de orden en el conjunto de tareas y $K\geq 0$. Una asignación con retraso acotado es una asignación
  
  $$\sigma:A\rightarrow [0,\mbox{\rm card}(A)-1]$$
  
  
  tal que

  1.

  $\sigma$ es inyectiva y monótona, i.e.: $a\preceq b\ \Rightarrow \ \sigma(a)\leq \sigma(b),$

  2.

  el conjunto de tareas que ``no se ajustan a sus tiempos'' no excede de K elementos, i.e.
  

  $$\mbox{\rm card}\{a\in A\vert\sigma(a)+d(a)>s(a)\}\leq K.$$