WinQSB - Programacin de trabajos (Job Scheduling) Este mdulo, Job Scheduling, resuelve problemas de programacin en job shops y flow shops. De acuerdo con los requisitos operativos de los trabajos, el programa aplica una heurstica apropiada para determinar las secuencias de trabajo. Las capacidades especficas del programa incluyen:

15 reglas populares de secuenciacin para problemas del tipo job shop, incluyendo la mejor secuencia de todas las reglas y la generacin aleatoria de un nmero determinado de secuencias.

7 heursticas populares para problemas del tipo flow shop, incluyendo la mejor secuencia de todos las heursticas, la generacin aleatoria de un nmero determinado de secuencias, y la enumeracin completa de las secuencias de permutacin.

Las entradas incluyen los trabajos y los tiempos de preparacin de mquina y los elementos de coste.

18 medidas de desempeo para el programa obtenido. Diagrama de Gantt para trabajos y mquinas. Visualizacin grfica del anlisis de rendimiento. Realizacin del anlisis de finalizacin. Ingreso de los problemas en formato de planilla de clculo.

Job shop En un job shop, hay n trabajos en espera de ser procesados en m mquinas o centros de trabajo. Cada uno de los n trabajos tiene su propia ruta o secuencia de mquinas, es decir, cada trabajo puede tener una ruta diferente. Una secuencia o programa factible para un job shop se define como la asignacin de las operaciones a las mquinas sin violar las restricciones de capacidad y rutas. Flow shop En un flow shop, hay n trabajos que esperan ser procesados en m mquinas o centros de trabajo. Cada uno de los n trabajos tiene la misma secuencia de mquinas, es decir, la misma ruta. Un programa factible para un conjunto de trabajos se define como una secuencia de todos los trabajos en cada mquina sin violar las capacidades de cada mquina. Se ha demostrado que encontrar todas las secuencias posibles es computacionalmente impracticable para problemas de cierta magnitud. Por lo tanto, la mayora de los mtodos algortmicos generan un subconjunto de soluciones que slo incluye los programas o secuencias de permutacin. Un programa o secuencia de permutacin es un programa con la misma secuencia de trabajos en todas las mquinas. Reglas de secuenciacin para problemas de programacin en job shops Se pueden utilizan reglas de secuenciacin conocidas para resolver problemas de programacin en job shops. En WinQSB, hay 14 reglas de secuenciacin disponibles. Cada regla puede ser seleccionada como la regla primaria o la regla de desempate para generar las secuencias de trabajo. Las reglas usadas en la seleccin de una operacin para la ejecucin en una mquina se describen a continuacin:

SPT (Tiempo de proceso ms corto): Seleccionar la operacin con el menor tiempo de procesamiento.

LPT (Tiempo de proceso ms largo): Seleccionar la operacin con el mayor tiempo de procesamiento.

RANDOM (Seleccin al azar): Seleccionar la operacin al azar. FCFS (primera llegada, primer servicio).

LCFS (ltima llegado, primer servicio). LWKR (Menos trabajo restante): Seleccionar la operacin asociada con el trabajo que

tenga menos trabajo por hacer en trminos de tiempo. MWKR (Ms trabajo restante): Seleccionar la operacin asociada con el trabajo que

tiene ms trabajo por hacer en trminos de tiempo. TWK (Trabajo total): Seleccionar la operacin asociada con el trabajo que requiere ms

esfuerzo en trminos de tiempo. LWK (Menor trabajo total): Seleccionar la operacin asociada con el trabajo que

requiere menos esfuerzo en trminos de tiempo. FOPR (Menor nmero de operaciones pendientes): Seleccionar la operacin asociada

con un trabajo que tiene el menor nmero de operaciones pendientes de ser completadas.

EDD (Fecha de entrega ms cercana): Seleccionar el trabajo con la primera fecha de entrega.

SLACK (Tiempo de holgura): Seleccionar el trabajo con el menor valor de la diferencia entre su fecha de entrega y el tiempo de procesamiento restante.

S / ROP (Holgura / N de operaciones restantes): Seleccionar el trabajo con el menor valor del cociente entre el tiempo de holgura y el nmero de operaciones restantes.

WINQ (Siguiente trabajo en cola): Seleccionar el trabajo que se unir a la cola con la menor carga de trabajo.

Priority Index: Seleccionar el trabajo con mayor ndice de prioridad. Mtodos heursticos para problemas flow shop Estn disponibles siete mtodos heursticos populares en WinQSB para resolver los problemas de programacin de tipo flow shop. Se pueden encontrar en las siguientes referencias:

1. Campbell, H. G., Dudek, R. A., and Smith, M. L., "A Heuristic Algorithm for the n-job, M-machine Sequencing Problem," Management Science, 16 (1970), pp. B630-637.

2. Dannenbring, D. G., "An Evaluation of Flow Shop Sequencing Heuristics," Management Science, 23 (1977), pp. 1174-1182.

3. Gupta, J. N. D., "A Functional Heuristic Algorithm for the Flow Shop Scheduling Problem," Operational Research Quarterly, 22 (1971), pp. 39-47.

4. Ho, Johnny, and Yih-Long Chang, "A New Heuristic for the n-Job, M-Machine Flow Shop," European Journal of Operations Research, 52 (1991), pp. 194-202.

5. Hundal, T. S., and Rajgopal, J., "An Extension of Palmer's Heuristic for the Flow Shop Scheduling Problem", International Journal of Production Research 26 (1988), pp. 1119-1124.

6. Johnson, S. M., "Optimal Two and Three-stage Production Schedules with Set Up Times Included," Naval Research Logistics Quarterly, 1 (1954), pp. 61-68.

7. Palmer, D. S., "Sequencing Jobs through a Multi-stage Process in the Minimum Total Time---A Quick Method of Obtaining a Near Optimum," Operational Research Quarterly, 16 (1965), pp. 101-107.

Medidas de rendimiento Se utilizan 18 medidas de rendimiento para evaluar una secuencia. Se describen a continuacin.

i: Subndice para los trabajos, i = 1 ,..., n j: Subndice para las mquinas, j = 1 ,..., m Pij: Tiempo de procesamiento del trabajo i en la mquina j. di: Fecha de entrega del trabajo i. ri: Tiempo de disponibilidad (o arribo al sistema) del trabajo i. Ci: Tiempo de realizacin del trabajo i.

Fi: Tiempo de flujo del trabajo i, es decir, Fi = Ci - ri. Wi: Tiempo total de espera de trabajo i, es decir, Wi = Fi - j Pij. Li: Impuntualidad del trabajo i, es decir, Li = Ci - di. Ei: Adelanto del trabajo i, es decir, Ei = maxi {-Li, 0}. Ti: Retraso del trabajo i, es decir, mxi Ti = {Li, 0}. Nt: Nmero de trabajos sin terminar en el sistema en el instante t. wi: Peso asignado de trabajo i.

Si los pesos no se indican, se supone que todos los pesos son iguales a 1. Las medidas de rendimiento se definen como sigue:

Cmax: Tiempo de finalizacin de todos los trabajos o makespan. MC: Tiempo de finalizacin medio ponderado, es decir, MC = (i wi Ci) / (iwi). Wmax: Tiempo mximo de espera, es decir, Wmax = mxi Wi. MW: Tiempo de espera medio ponderado, es decir, MW = (i wi Wi) / (iwi). Fmax: Tiempo de flujo mximo, es decir, Fmax = mxi Fi. MF: Tiempo de flujo medio ponderado, es decir, MF = (i wi Fi) / (i wi). Lmax: Mxima impuntualidad, es decir, Lmax = mxi Li. ML: Impuntualidad media ponderada, es decir, ML = (iwi Li) / (iwi). Emax: Adelanto mximo, es decir, Emax = mxi Ei. ME: Adelanto medio ponderado, es decir, ME = (iwi Ei) / (iwi). Tmax: Retraso mximo, es decir, Tmax = mxi Ti. MT: Retraso medio ponderado, es decir, MT = (iwi Ti) / (iwi). NT: Nmero de trabajos retrasados, es decir, NT = | {i | Ci> di} | . WIP: Trabajo medio en proceso, es decir, WIP = Promedio de Nt sobre Cmax. MU: Utilizacin media de las mquinas. TJC: Costos totales de los trabajos, incluidos los costos de inactividad, actividad,

adelantos y retrasos. TMC: Costos totales de las mquinas, incluyendo los costos de inactividad y los costos

de actividad. TC: Costo total = TJC + TMC.

Salvo en el caso de MU, se desea minimizar las medidas de desempeo. Diagramas de Gantt El diagrama de Gantt fue creado por H. L. Gantt en 1918. Se trata de una herramienta grfica para mostrar el inicio y fin de cada actividad. Un diagrama de Gantt tpico incluye una lnea de tiempo horizontal y una lnea vertical de las actividades. En WinQSB, se muestran los programas asociados a los trabajos o a las mquinas para el problema considerado.

PROBLEMAS 1. Cinco trabajos deben ser programados para su procesamiento por lotes realizado en un

sistema de supercomputadoras. Los tiempos de procesamiento y la hora de entrega para cada trabajo se muestra en la tabla siguiente:

Trabajo 1 2 3 4 5

Tiempo de procesamiento

40 min 2,5 h 20 min 4 h 1,5 h

Hora de entrega

11:00 a.m. 2:00 p.m. 2:00 p.m. 1:00 p.m. 4:00 p.m.

a) Si los trabajos son ordenados de acuerdo a la regla de Tiempo de Procesamiento

ms Corto, (SPT) encontrar la tardanza (el tiempo de retraso) de cada trabajo y la tardanza media (el retraso medio del trabajo) de todos los trabajos. Cul es tiempo promedio de espera de los trabajos?

b) Repita los clculos anteriores para una programacin segn la regla Fecha de Entrega ms Temprana. (EDD). Calcule tiempo promedio de espera de los trabajos.

c) Compare y recomiende la programacin adecuada para procesar los trabajos, fundamentando su respuesta con los valores de las medidas de desempeo obtenidas en cada caso.

d) Qu secuencia sugerira si la gerencia exige minimizar el nmero de trabajos retrasados?

2. Cuatro camiones estn esperando para ser descargados en la compaa XYZ que tiene

solamente una baha de descarga. Los camiones son etiquetados segn su orden de arribo a la zona de descarga. Asumiendo que al momento es la 1:00 p.m. y que son conocidos los tiempos de descarga de cada camin y el momento en el cual el material descargado debe ser entregado:

Camin Tiempo de descarga

(minutos) Entrega material

1 20 1:25 p.m. 2 14 1:45 p.m. 3 35 1:50 e.m. 4 10 1:30 p.m.

a) Determinar la programacin que resulta de aplicar las reglas PEPS (FCFS), TPC

(SPT), TEC (EDD), y RC (CR). En cada caso calcular el tiempo de flujo promedio. tardanza promedio (retraso medio del trabajo), y el nmero de trabajos retrasados.

b) Suponga que el costo total de inactividad es proporcional al tiempo de espera total de las descarga en la baha. Qu secuencia es la qu genera el mnimo costo total de mquina? Es nica dicha secuencia?

Camin Costo de inactividad

por minuto ($ /minuto) 1 1 2 4 3 1 4 2

3. Mara y Marta son dos hermanas que asisten juntas a clases. Durante el primer cuatrimestre se organizan para aprovechar las horas de consulta de las materias que estn cursando. En virtud de que los exmenes comienzan la semana prxima, piensan dedicar el da de maana para las consultas. Estiman que el tiempo (minutos) que tienen que emplear en asistir a las mismas es:

Profesores Mara Marta Matemtica 40 20

Historia 15 30 Ingls 25 10

Ciencias 15 35 Msica 20 25

Asumen que los profesores que dan las consultas estarn disponibles todo el da de maana. A Mara le gustara visitar a los profesores en el orden dado anteriormente pero Marta preferira hacer sus consultas en el siguiente orden: Matemticas, Msica, Ingls, Ciencias e Historia. Cmo deben programar las consultas a los profesores para minimizar el tiempo total destinado a consulta?

4. Los siguientes trabajos deben ser procesados a travs de tres mquinas con secuencia fija:

Trabajo A B C 1 4 2 6 2 2 3 7 3 6 5 6 4 3 4 8

Obtenga la secuencia ptima de los trabajos para minimizar el tiempo total de ejecucin de los trabajos (makespan). Cul es dicho valor en la solucin ptima? Elabore diagrama de Gantt de la solucin ptima.