DAA: secuenciación de trabajos con fecha límite

Planteamiento del problema

En el problema de secuenciación de trabajos, el objetivo es encontrar una secuencia de trabajos, que se complete dentro de sus plazos y dé el máximo beneficio.

Solución

Consideremos, un conjunto de ndeterminados trabajos que están asociados con fechas límite y se obtienen ganancias, si un trabajo se completa antes de su fecha límite. Estos trabajos deben ordenarse de tal manera que se obtenga el máximo beneficio.

Puede suceder que todos los trabajos dados no se completen dentro de sus plazos.

Supongamos, fecha límite de i^th trabajo J_i es d_i y la ganancia recibida de este trabajo es p_i. Por tanto, la solución óptima de este algoritmo es una solución factible con el máximo beneficio.

Por lo tanto, $ D (i)> 0 $ para $ 1 \ leqslant i \ leqslant n $.

Inicialmente, estos trabajos se ordenan según la ganancia, es decir, $ p_ {1} \ geqslant p_ {2} \ geqslant p_ {3} \ geqslant \: ... \: \ geqslant p_ {n} $.

Algorithm: Job-Sequencing-With-Deadline (D, J, n, k) 
D(0) := J(0) := 0 
k := 1 
J(1) := 1   // means first job is selected 
for i = 2 … n do 
   r := k 
   while D(J(r)) > D(i) and D(J(r)) ≠ r do 
      r := r – 1 
   if D(J(r)) ≤ D(i) and D(i) > r then 
      for l = k … r + 1 by -1 do 
         J(l + 1) := J(l) 
         J(r + 1) := i 
         k := k + 1

Análisis

En este algoritmo, estamos usando dos bucles, uno dentro del otro. Por tanto, la complejidad de este algoritmo es $ O (n ^ 2) $.

Ejemplo

Consideremos un conjunto de trabajos dados como se muestra en la siguiente tabla. Tenemos que encontrar una secuencia de trabajos, que se completarán dentro de sus plazos y darán el máximo beneficio. Cada trabajo está asociado con una fecha límite y una ganancia.

Trabajo	J₁	J₂	J₃	J₄	J₅
Fecha límite	2	1	3	2	1
Lucro	60	100	20	40	20

Solución

Para resolver este problema, los trabajos dados se ordenan de acuerdo con su beneficio en orden descendente. Por lo tanto, después de la clasificación, los trabajos se ordenan como se muestra en la siguiente tabla.

Trabajo	J₂	J₁	J₄	J₃	J₅
Fecha límite	1	2	2	3	1
Lucro	100	60	40	20	20

De este conjunto de trabajos, primero seleccionamos J₂, ya que se puede completar dentro de su plazo y aporta el máximo beneficio.

Próximo, J₁ se selecciona porque da más beneficios en comparación con J₄.
En el próximo reloj J₄ no se puede seleccionar porque su fecha límite ha terminado, por lo tanto J₃ se selecciona ya que se ejecuta dentro de su fecha límite.
El trabajo J₅ se descarta porque no se puede ejecutar dentro de su fecha límite.

Por tanto, la solución es la secuencia de trabajos (J₂, J₁, J₃), que se ejecutan dentro de su plazo y dan el máximo beneficio.

El beneficio total de esta secuencia es 100 + 60 + 20 = 180.

↰ Previous page Next page ↱