Siguiente: Problemas en teoría de Un nivel arriba: Problemas con un solo Anterior: Nociones básicas

Problemas

Secuenciación en intervalos (Sequencing within intervals):


Instancia:

Solución:




Proposición: ``Sequencing within intervals'' es completo-NP. Demostración: Es evidentemente un problema en NP. Para ver que es difícil-NP, reduzcamos PARTITION a él. Sea $T=\{t_1,\ldots, t_n\}$ una instancia de PARTITION. Se trata de encontrar $J\subset[1,n]$ tal que $\sum_{j\in J}t_j=\sum_{j\in J^c}t_j$. Sea $B=\sum_{j=1}^n t_j$. Construyamos la siguiente instancia de ``Sequencing within intervals'':

• Por cada sumando t_j, definimos,
  • una tarea a_j, con
  • lanzamiento planeado r(a_j)=0,
  • instante de saturación s(a_j)=B+1, y
  • duración d(a_j)=t_j.
• Ponemos una tarea ``extra'' a₀ con parámetros
  
  $$\begin{array}{ccccc} r(a_0)=\left\lceil\frac{B}{2}\right\rcei... ...=\left\lceil\frac{B+1}{2}\right\rceil & ,& d(a_0)=1 \end{array}$$
  
  
  Observamos que
  
  $$s(a_0)-r(a_0)=\left\{\begin{array}{ll} 1 &\mbox{\rm si $B$ es par, } \\ 0 &\mbox{\rm si $B$ es impar. } \end{array}\right.$$
  
  

Vemos pues que si B es impar entonces ni PARTITION ni ``Sequencing within intervals'' tienen solución. Ahora, si B es par, toda asignación factible $\sigma$ necesariamente hará $\sigma(a_0)=\frac{B}{2}$, y consecuentemente las tareas restantes se dividen en dos conjuntos:

• las que se realizan antes de a₀, las cuales disponen, en total, de $\frac{B}{2}$ unidades de tiempo para ejecutarse, y
• las que se realizan después de a₀, las cuales disponen, en total, también, de $\frac{B}{2}$ unidades de tiempo para ejecutarse.

Tenemos así una solución de PARTITION. Recíprocamente, de acuerdo con lo anterior, una solución de PARTITION da una asignación factible.


Mínimos retrasos (Minimum tardiness sequencing):


Instancia:

Solución:




Proposición: ``Minimum tardiness sequencing'' es completo-NP. Demostración: Para verlo como un problema difícil-NP reduciremos CLIQUE a él. Sea pues $[G=(V,E), J\leq \mbox{\rm card}(V)]$ una instancia de CLIQUE. Construiremos una instancia de ``Minimum tardiness sequencing'' tal que ésta tendrá una asignación con retrasos acotados por una cota construída si y sólo si la gráfica G contiene a K_J como una subgráfica. Definamos:

• Tareas: $A=V\cup E$.
• Cota: $K=\mbox{\rm card}(E)-\frac{1}{2}J(J-1)$.
• Orden de A: $\forall a,b\in A:$
  
  $$a\preceq b\ \Leftrightarrow\ (a\in V)\land(b\in E)\land(a\in b),$$
  
  
  es decir, $a\preceq b$ si a es un vértice, b es una arista y a es un vértice extremo de b. Con esto tendremos que en toda asignación monótona, cada arista ha de ``ejecutarse'' después que cualquiera de sus vértices.
• Saturaciones:
  
  $$s:a\mapsto\left\{\begin{array}{ll} \frac{1}{2}J(J+1) &\mbox{... ...box{\rm card}(A) &\mbox{\rm si $a\in V$. } \end{array}\right.$$
  
  
  Así pues las únicas tareas que pueden incurrir en retrasos son las correspondientes a las aristas.

Para una asignación $\sigma$, dividamos al conjunto de aristas en dos clases

• las que se realizan a tiempo:
  
  $$\begin{eqnarray*}E_{1\sigma} &=& \{a\in E\vert\sigma(a)+1\leq s(a)\} \\ e_{1\sigma} &=& \mbox{\rm card}(E_{1\sigma})< \frac{1}{2}J(J+1), \end{eqnarray*}$$
  
  
• las que no se realizan a tiempo:
  
  $$\begin{eqnarray*}E_{2\sigma} &=& \{a\in E\vert\sigma(a)+1> s(a)\} \\ e_{2\sigma} &=& \mbox{\rm card}(E)-e_{1\sigma}% \end{eqnarray*}$$
  
  

Pues bien, si $\sigma$ fuese una solución de ``Minimum tardiness sequencing'' entonces $e_{2\sigma}\leq K$ y consecuentemente $e_{1\sigma}\geq\frac{1}{2}J(J-1)$. Así pues, el entero $e_{1\sigma}$ debe estar en el intervalo $[\frac{1}{2}J(J-1),\frac{1}{2}J(J+1)[$, el cual contiene precisamente J enteros. Si $e_{1\sigma}=\frac{1}{2}J(J-1)$ entonces el conjunto de vértices de la gráfica que son extremos de aristas en $E_{1\sigma}$, llamémoslo V<sub>1</sub>, por lo menos tiene J vértices. Esta cota mínima se alcanza cuando $E_{1\sigma}$ es una gráfica completa K<sub>J</sub>. Por otro lado, como $\sigma$ ha de ser monótona, si toda ``tarea'' de $E_{1\sigma}$ se realiza ``antes'' de $\frac{1}{2}J(J+1)$ entonces toda ``tarea'' en V₁ también ha de realizarse antes de ese tiempo. Así, se tiene que ambos números $e_{1\sigma}$ y $e_{1\sigma}+\mbox{\rm card}(V_1)$ están en el intervalo $[\frac{1}{2}J(J-1),\frac{1}{2}J(J+1)]$. Esto obliga a que $\mbox{\rm card}(V_1)=J$ y por tanto los vértices en V₁ forman un clan en G con J elementos. Recíprocamente, si V₁ es un conjunto de J vértices que forman un clan en G entonces a ellos y a sus aristas les podemos asociar un ``tiempo'' de ejecución anterior a $\frac{1}{2}J(J+1)$. La asignación así construída provee una solución de ``Minimum tardiness sequencing''.
Siguiente: Problemas en teoría de Un nivel arriba: Problemas con un solo Anterior: Nociones básicas