Secuenciación de Tareas F2 pre Cmax

Hola de nuevo.

En esta ocasión os hablaré de la secuenciación de Tareas; En una próxima entrada me gustaría resumir  los casos más básicos estudiados en secuenciación. No obstante en esta entrada popondré la solución a un caso práctico que se define como dice el titulo así F2 pre Cmax :

De acuerdo a la nomenclatura se trata de encontrar el algoritmo que minimice el tiempo máximo de finalización de las tareas para un proceso donde existen orden de preferencias de los trabajos y 2 máquinas en serie. El algoritmo estará basado en dos partes: En primer lugar usaremos el algoritmo de Johnson (estudiado para el caso F₂//C_max.)
 Actuaremos Así -          Respecto a la máquina 1, como me interesa que los trabajos vayan quedando disponibles lo antes posibles para ser procesados en la segunda máquina, podría ordenar los trabajos de menor a mayor tiempo de proceso (en M1). Pero respetando el orden de precedencia
 -           Por otro lado, como van a existir huecos en la máquina 2, me interesaría introducir los trabajos con mayor tiempo de proceso (en M2) antes, puesto que disminuiré el tamaño de los huecos, lo cual significa que finalizaría antes.
  Iremos elaborando el algoritmo con 10 tareas con dos máquinas. Por ejemplo
 

	TAREAS
TAREAS	J1	J2	J3	J4	J5	J6	J7	J8	J9	J10
PRECEDE			J1	J2	J2	J3	J4,J5	J6,J3	J7	J8
DURACION MAQUINA 1 (CORTE)	2	4	3	8	3	4	5	1	2	6
DURACION MAQUINA 2 (ESMERILADO)	4	3	5	6	1	6	2	3	6	2

 1.       Se dividen los trabajos en 2 secuencias:
        SI1= {Ji: p_i1 £ p_i2}: Trabajos con tiempo en máquina 1 igual o inferior al tiempo en máquina 2
        SI1= J1, J3, J6, J8, J9
         SI2= {Ji: p_i1 > p_i2}: Trabajos con tiempo en máquina 1 superior al tiempo en máquina 2
        SI2= J2; J4; J5; J7; 10
 2.       Ordenación de secuencias:
       S1 = {SI1 en orden no decreciente de p_i1}
      SI1= J8, J9, J1; J3, J6
       S2 = {SI2 en orden no creciente de p_i2}       SI2= J4, J2, J7, J10, J5
3.       La secuencia final si tener en cuenta las necesidades de precedencia es:
S= {S1, S2}= J8, J9, J1; J3, J6, J4, J2, J7, J10, J5. 4.       No obstante las tareas tiene un orden de preferencia por lo que esta secuencia debe modificarse.
  2da parte del problema  cumplir con la precedencia. Lo que haremos será ir de izquierda a derecha anteponiendo los precedentes.  5.       1era llamada a ORDENACIÓN. Antecedentes del primer elemento actual: J8à (J3 Y J6)
        S= J3, J6, J8, J9, J1, J4, J2, J7, J10, J5.
        y volvemos al inicio del bucle ordenación por tareas precedentes.
         2da llamada a ORDENACIÓN Antecedentes del primer elemento actual: J3 à(J1)
        S= J1, J3, J6, J8, J9, J4, J2, J7, J10, J5.
        Y volvemos al inicio del bucle ordenación por tareas precedentes.
         3era llamada a ORDENACIÓN. Antecedentes del primer elemento actual: J1àno tieneà siguiente elemento J3à(J1)àYa lo precede luego siguiente elementoà J6 à (J3)à ya le precede luego siguiente elementoàJ8 (J6 y J3)à ya le preceden luego siguiente elementoàJ9 (J7)
             S= J1, J3, J6, J8, J7, J9, J4, J2, J10, J5
         Y volvemos al inicio del bucle ordenación por tareas precedentes.
           4ta llamada a ORDENACIÓN. Se vuelve a comprobar cada elemento donde ya nada cambia hasta llegar a J7à (J4;J5)
             S= J1, J3, J6, J8, J4, J5, J7, J9, J2, J10
        Y volvemos al inicio del bucle ordenación por tareas precedentes
        5ta llamada a ORDENACIÓN. Se vuelve a comprobar cada elemento donde ya nada cambia hasta llegar a J4à (J2)
             S= J1, J3, J6, J8, J2, J4, J5, J7, J9, J10
        Y volvemos al inicio del bucle ordenación por tareas precedentes
       6ta llamada a ORDENACIÓN. Se vuelve a comprobar cada elemento donde ya nada cambia. En este momento las tareas están también ordenadas por orden de precedencia.
 Luego la secuenciación que minimiza el tiempo de finalización  es:              S= J1, J3, J6, J8, J2, J4, J5, J7, J9, J10

6.       La asignación se realiza sin dejar innecesariamente una máquina ociosa y teniendo en cuenta que debe terminar el proceso en una máquina para comenzar en la siguiente. Ojo en este punto aunque por lo general no va a ser necesario sería interesante a la hora de implementar un algoritmo tener en cuenta que los trabajos en la maquina 2 tendrán que cumplir dos requisitos. El orden de ejecución de los trabajos por supuesto no cambia, no obstante tal vez no sea suficiente con mantener dicho orden y el algoritmo debe garantizar que no se empieza ningún trabajo en la máquina 2 sin que haya terminado su correspondiente tarea en la máquina 1,

El algoritmo lo he implementado mediante Visual Basic en una macro de excel. En teoría debe funcionar para tareas indefinidas,aunque al abrir el archivo veréis tan solo el caso práctico que cito en esta entrada. Escribid las tareas y sus duraciones así como los ordenes de precedencia en las casillas correspondientes y pulsad el botón

AL ejecutad la macro se os abre la hoja dos donde podréis ver un gráfico gantt con  la secuenciación resultante. Si volvéis a la hoja1 tenéis en primer lugar la secuenciación según el algoritmo de Johnson y mas abajo la secuenciación teniendo en cuenta el orden de precedencia de las tareas (Esta es la representada en el gantt).

Recordad que para poder ejecutar la macro debéis tenerlas habilitadas. (Normalmente aparece un mensaje de advertencia, le dais a habilitar y ya está).

F2 pre Cmax.xls