Secuenciación de trabajos sobre una máquina con restricciones de precedencia

              •Rev.Acad.Canar.Cienc., I, 217-226 (1990)
SECUENCIACION DE TRABAJOS SOBRE UNA MAOUINA
CON RESTRICCIONF.S DE PRECEDENCIA
0. Alcaide2 y J. Sicilia 1
1Departamento de Estadistica e I.O.
Universidad de La Laguna
38204-La Laguna, Espana
2Departamento de Informatica y Sistemas
Universidad de Las Palmas de Gran Canaria
38200-La Laguna, Espana
ABSTRACT
Suppose n jobs are to be processed on a single
machine. These jobs can not be performed in any order,
because a . precedence relation between the jobs is
specified. This paper develops an heuristic method to
find a schedule which minimizes the total tardiness.
Keywords: Scheduling, Tardiness, Precedence Constraints.
INTROOUCC ION
Al amparo de la Investigaci6n Q:>erativa, y en los ultimos anos, se han
desarrollado diversas disciplinas dirigidas a optimizar la utilizaci6n de los
escasos recursos disponibles, para lograr la maxima eficacia en la aplicaci6n
de los mismos.
Una de esas disciplinas, conocida como Planificacion y Secu~nciaci6n,
estudia la asignaci6n entre actividades o tareas a realizar y maquinas
disponibles para realizarlas, buscando la ordenaci6n de trabajos que optimice
alguna medida o criterio considerado.
Entre dichas medidas podemos citar el tiempo total de completaci6n de
los trabajos, el numero de trabajos que exceden de unas fechas limite, la
tardanza total de todos los trabajos, etc.; siendo esta ultima la considerada
en el presente articulo.
Si los trabajos pueden secuenciarse en cualquier orden, se di ce que los
mismos son independientes entre si. No obstante, en la practi ca , ee.te no es
el caso mas comun, debi.do tal vez a consider·aciones de tipo tec nol6gico o
humano que obligan a realizar un trabajo despues de haber· fina lizado otros
que le preceden. Tales restricci.ones de precedencia imponen un orden parcial
sobre l os t rabajos e i nc rementan la comple jjdad comput acionri.1 oel
217
© Del documento, de los autores. Digitalización realizada por ULPGC. Biblioteca Universitaria, 2017
correspondiente problema de secuenciaci6n.
La teoria de la Complejidad Computacional ofrece un soporte te6rico para
distinguir formalmente entre problemas bien resueltos, aquellos para los
cuales se ha encontrado un algoritmo cuyo tie11PO de computaci6n esta acotado
por una funci6n polinomial del tamano del problema, y los llamados NP-duros,
para los cuales nose encuentran algoritmos en tiempo polinomial y, al mismo
tiempo, la busqueda de dicho algoritmo es altamente dificultosa .
Dentro de este ultimo grupo, se encuentra el problema que nos ocupa.
Tanto Baker (1) como French (3) comentan en sus respectivos libros la
necesidad de abordar el problema de la tardanza total mediante metodos
heuristicos, debido a que la complej idad del problema requiere un tiempo
exponencial. Has concretamente, Lenstra y Rinn<X>y Kan (7) demuestran que el
problema de minimizar ~a tardanza total en una maquina con restricciones de
precedencia es NP- duro.
En tales circunstancias, es ampliamente justificada la consideraci6n de
metodos heuristicos que ofrezcan soluciones aproximadas al problema
planteado. En ese contexto ~e enmarca el presente trabajo.
PLANTEAHIENTO DEL PROBLEHA
Sean n trabajos que se desean procesar sob re una maquina, los cuales
cumplen las siguientes caracteristicas: todos estan disponibles para ser
procesados en cualquier memento y una vez iniciada la realizaci6n de un
trabajo este no puede interru•pirse para comenzar ningun otro. La
secuenciaci6n de los trabajos debe adecuarse a unas relaciones de precedencia
entre trabajos fijada a priori. Dicha relaci6n es recogida en un grafo
aciclico G cuyos nodos sean los trabajos nu•erados de tal forma que si (i,j)
es una arista del grafo, se entendera que i debe ir siempre antes que j.
Denotaremos por f(j) al conjunto de trabajos que deben realizarse
posteriormente a la co111pletaci6n del trabajo j, esto es, el conjunto de
vertices siguientes a j en el grafo G. Oar una estructura de precedencia R
sobre los trabajos, equivaldra a especificar los correspondientes conjuntos
f(j), 't'j.
Una secuencia S se dice que es compatible con la estructura de
precedencia R, si no vulnera ninguna de las restricciones de precedencia
tijadas en R, es decir, no podran existir dos trabajos con la ordenaci6n
"i anterior a j " en la secuencia S, si i E f(j).
Cada trabajo j lleva asignado un tiempo de procesamiento pJ conocido y
218
© Del documento, de los autores. Digitalización realizada por ULPGC. Biblioteca Universitaria, 2017
una fecha limite dj dada. Si no se ha completado el procesamiento de un
trabajo antes de su fecha limite, se incurre en una tardanza la cual es
medida por el numero de unidades de tiempo en que se ha superado dicha fecha.
El instante en el cual el trabajo j se termina de procesar se denomina
el tiempo de completaci6n del trabajo j y se denota por c;. L6gica mente este
tiempo varia en relaci6n con la posici6n que ocupa el trabajo j en la
secuencia correspondiente de trabajos. Asi, si dicho trabajo c._: upase el lugar
k
k, entonces C.= l plCil' siendo l(i) el trabajo que estaria en la posici6n i.
J i • 1
Se define la Tardanza de un trabajo j por la expresi6n
T/ max{ o, L;= cj-d)
El problema de la Tardanza Total consiste en encontrar una ordenaci6n o
secuencia (1(1), ... ,l(n)) de trabajos que minimice la tardanza total
n
L T l ( . ).
J•1 J
Hetodos exactos que permiten encontrar una soluci6n 6ptima para el
problema pueden verse en Baker (1), Bakery Hartin (2), Lawler (4) yen Potts
y Van Wassenhove (8). Estos tHtimos autores hacen un estudio exhaustivo de
varios de estos metodos. El problema es que tales procedimientos requieren un
gran esfuerzo computacional cuando el numero de trabajos es de varias
decenas. En tales circunstancias los metodos heuristicos pueden of rece r
soluciones aceptables, ya que la perdida de bondad de la soluci6n obtenida
queda contrarrestada por la notable mejora del tiempo invertido en su
busqueda.
En anteriores trabajos, referencias (9) y (10), abordamos el estudio de
la tardanza total sin considerar restricciones de . precedencia; con el
presente, vemos como incide sobre el problema considerado, la incorporaci6n
de dichas restricciones.
Describimos a continuaci6n un metodo heuristico que guie la busqueda de
una soluci6n aproximada para el problema comentado.
ALGORITHO
Antes de describir paso a paso el algoritmo propuesto, comentemos
brevemente las ideas generales del mismo.
La estructura de precedencias entre los trabajos, permite clasificar los
mi s mos en k niveles de forma que, la ejecuci6n de cualquier trabajo del nivel
i-esimo, requiere haber realizado previamente al menos un trabajo del nivel
i-1.
219
© Del documento, de los autores. Digitalización realizada por ULPGC. Biblioteca Universitaria, 2017
Dentro de cada nivel se considera la correspondiente secuencia EDD
(ordenaci6n de menor a mayor de los diversos trabajos de acuerdo con las
fechas limites) y posteriormente se agrupan las diferentes ordenadones en un
solo vector, poniendo en primer lugar las de menor nivel. Dicho vector sera
nuestra secuencia semilla.
Si en dicha secuencia hubiesen dos o mas trabajos de un mismo nivel con
fechas limites iguales, se ordenan estos trabajos de acuerdo con sus tiempos
de prcx::esamiento de menor a mayor .
El organigrama del algoritmo puede verse en la figura 1. Tras determinar
la secuencia inicial, se calculan las tardanzas de los trabajos y se
selecciona el trabajo candidato a cambiar de lugar (paso 3). Posteriormente
se decide cual debe ser el cambio mas favorable, es decir, si el trabajo
elegido debe adelantarse 6 retrasarse, teniendo siempre presente que el
cambio seleccionado debe ser compatible con la estructura de precedencia
establecida inicialmente.
La posible ganancia en la reducci6n de la tardanza, si adelantaramos el
trabajo, viene dada en los pasos 5 y 6; mientras que si se retrasara, la
bondad de tal medida es cuantificada por los pasos 8 y 9 del algoritmo.
La decision de efectuar el cambio (siempre al lugar que ofrece una mayor
reducci6n) se aborda en el paso 10. Si desistimos de hacerlo, sera debido a
que no decrece la tardanza total y, en consecuencia, elegiremos un nuevo
trabajo candidato a cambiar de lugar. El proceso finaliza cuando ningun
trabajo proporcione un cambio que permita reducir la tardanza total.
220
© Del documento, de los autores. Digitalización realizada por ULPGC. Biblioteca Universitaria, 2017
Oeterminar la secuencia semilla
Calcular Ll(j) y Tl(j)
Oeterminar el candidato l(j
0
)
Elegir el cambio mas f avorable que cumpla
las restricciones de precedencias
Si
lExiste tal cambio?
No
Elegir nuevo candidato l(j 1)
Si
lExiste tal candidato?
No
Parar
Nueva secuencia
Cambiar
Figura 1: Organigrama del algoritmo heuristico.
221
© Del documento, de los autores. Digitalización realizada por ULPGC. Biblioteca Universitaria, 2017
~19<:?E:t!:!!l<:?
Paso 1:
Paso 2:
Paso 3:
Paso 4:
Paso 5:
Paso 6:
Paso 7:
Establecer la ordenaci6n de trabajos por niveles de acuerdo con el
grafo aciclico que fija las relaciones de precedencia. Sea ni el
numero de trabajos del nivel i-esimo y consideremos que k rep 1~esenta
el numero de niveles que hay en el grafo aciclico.
Ordenar los trabajos de cada nivel en orden EDD y tomar como
secuencia semil la a la ordenaci6n r·esul tante, la cual denotamos por
[1(1),1(2), ... ,l(n
1
);l(n 1+1), ... ,l(n 1+n 2); ... ;l(n-nk+l), .. . ,l(n)]
j
Calcular L1 <J>= L pl(i)- dl(j) y T1 <j>= max{O, L1<j» VJ =l, ... ,n.
i•1
n
Hallar T = L T1 <J>" Poner P = 0 (representa los trabajos que han sido
J•1
probados).
Elegir el jo tal que L1 (jo)= max{L 1 (j)/ lSjsn}. Dicho trabajo
l(jo) es el candidato a cambiar de lugar.
o Si jo = 1, ir al paso 7.
o Si jo~l, pero Tl(jo)= 0, ir al paso 7.
o En otro caso, poner m=l, G=O, q=O, A0 =0 y B. =O. Calcular m1
JO
el indice minimo para el cual l(jo) E f(l(jo-m1)); si no existe dicho
valor, colocar mt=jo.
( Adelanta r).
v. JO-a
Hacer m
paso 5.
o Sim= jo 6 m = m1, ir al paso 7.
o En otro caso, calcular los valores siguientes:
r(Jo)
,si Ll(Jo-•)> 0
~l(Jo-•)' pl(Jo)
,si L1(;o-•)so y P1(;o)s Ll(Jo-•)
,si L1(;o-•)so y Pl(jo) > L1(;0-•)
A•-l + V B. = 8 +
jo-• JO-• jo-a+1 pl(jo-•)
JO-a 0 min{B . ,Tl(J )} - A•.
D Si o•= Tl(Jo)'entonces poner q = jo-m, G=O• e ir al paso 7.
o Si o·~ T
1
(jo) y o• > G, entonces poner q = jo-m y G = o•.
= m+l y volver al paso 5.
o Si o·~ T
1
(Jo) y o• ;s; G, entonces hacer m=m+l y volver al
o Si jo = n, ir al paso 10.
o Si j o ~ n, pone r m = 1, F o O y Z0 = 0. Sea m2 el indice
minimo para el cual l(jo+m2) E f(l(jo)); si no existe tal valor, poner
m2 = n-jo+l.
222
© Del documento, de los autores. Digitalización realizada por ULPGC. Biblioteca Universitaria, 2017
Paso 8: (Retrasar).
o Si m = n - jo + 1 6 m = m2, ir al paso 10.
o En otro caso, calcular los valores siguientes:
::: {:~~~~.p~::~~~: F.}. :: ~:::::~:
{
o ,
X.
JO+M { }
min Ll(jo+.)' pl(Jo) '
si ll(jou/; 0
si Ll(jo+.)> 0
z• = z•- 1 + x o• =
jo+•
z• - y•.
Paso 9: o Si o• > G, poner q = jo + m y G = o•. Hacer m = m + 1 y
volver al paso 8.
o Si o• s G, hacer m = m + 1 y volver al paso 8.
Paso 10: (Cambiar)
o Si q = 0, no hacer ningun cambio. Colocar P = P u {jo} e ir
al paso 11 (busqueda de un nuevo candidato).
o Si q>O, cambiar el trabajo l(jo) al lugar q y rodar los
trabajos que sean necesarios, esto es: Sea HIN= min(q,jo) y
HAX=max(q,jo).
- Si HIN= q, entonces s(q) = l(jo), s(q+l) = l(q), ... , s(qtk)
l(q+k-1), ... , s(jo) = l(jo-1).
Si HIN= jo, entonces s(jo) = l(jo+l), .... , s(jo+k) =
1 ( j 0 + k +l) ' ... ' s ( q-1) = 1 ( q) ' s ( q) = 1 ( j 0) .
Antes de salir de este paso, renombrar los subindices haciendo
l(i) = s(i), V1E (MIN,HAX) y l(i) = l(i), Vi' (MIN,HAX).
Volver a calcular L1(j) y T1(j) para j E [HIN,HAX) segun las
formulas del paso 2. Poner T = T-G, P = 0 e ir al paso 3.
Paso 11: o Si Card(P) = n, parar. La secuencia (1 (1),1(2), ... ,l(n)] nos
da la soluci6n, siendo T el valor de la tardanza total para dicha
secuencia.
o Si Card(P) ~ n, entonces calcular el j1 tal que Ll(jt)
max{Ll(k)/k t P}. Hacer jo = j1 y volver al paso 4.
223
© Del documento, de los autores. Digitalización realizada por ULPGC. Biblioteca Universitaria, 2017
COHPLEJIDAD DEL ALGORITHO
El algoritmo tiene una complejidad o{n 2 f pi), desglosada de la forma
i•1
siguiente:
El paso requiere O(n 2
) operacione5, rnientras que el paso 2 cons ume a
lo s umo O(n log n).
Los pasos del 3 al 11 requieren O(n) por cada :iteraci6n.
i teraciones para estos pasos es a lo sumo de L T J (Sernilla)
j
siendo TJ(Sernilla) la tardanza del trabajo j correspondiente a
inicial y r ... x(EDD) la tardanza maxima para la secuencia EDD.
El numero de
- T (EDD),
•ax
la secuencia
La cuesti6n
sera determinar que valor puede tomar dicha expresi6n. La variabilidad de la
n
misrna es grande pero siernpre estara acotada por n.E pi.
i • 1
Por tanto, la recursividad de los pasos tercero al decimo prirnero nos
n
lleva a una complejidad O(n2 .E pi) que supera ampliarnente la de los pasos 1 y
i •1
2; en consecuencia, dicha expresi6n sera la complejidad del algoritmo.
Comentemos por ultimo que el algoritmo se ha probado en varios casos
particulares. Exponemos a continuaci6n uno de los casos estudiados.
EJEHPLO
Consideramos el proble111a de secuenciar ocho trabajos, cuyos tiempos de
procesamiento y fechas limites se recogen en la siguiente tabla
j 1 2 3 4 5 6 7 8
pj 121 147 102 79 130 83 96 88
d. 260 269 400 266 337 336 683 719
J
224
© Del documento, de los autores. Digitalización realizada por ULPGC. Biblioteca Universitaria, 2017
Las relaciones de precedenc:i.a vienen dadas por el grafo aciclico
Siguiendo el algoritmo propuesto, la secuencia semilla sera
8 4 6 3 2
a la que corresponden los Lj
(-207, -457, -405, 127, 140, 178, 439, 577)
y una tardanza total de 1461.
Inicialmente el candidate a cambiar es el trabajo 2 pero el mismo no
ofrece cambio favorable; lo mismo ocurre para la3 trabajos 1 y 3. La elecci6n
del trabajo 6 nos proporciona una reducci6n de la tardanza en 57 unidades, si
instalamos dicho trabajo en la posici6n 3 de la secuencia, obteniendo
asi la nueva secuencia
5 7 6 8 3 2
De la misma forma se descartan los candiatos 2 y 1, y se elige cono
nuevo candidate el trabajo numero 4. Dicho trabajo se coloca en la tercera
posici6n por ser el lugar que otorga mayor descenso en la tardanza total,
quedando esta en 1285. La nueva secuencia sera
Repitiendo el proceso, el algoritmo finaliza con la secuencia
5 4 6 8 3 2
con tardanza 1216.
N6tese que a lo largo del desarrollo del ejemplo, las divers as
sol uciones parciales que se van obteniendo veri fi e.an las restr icc iones de
precedencia establecidas en el grafo de partida.
225
© Del documento, de los autores. Digitalización realizada por ULPGC. Biblioteca Universitaria, 2017
B IBLIOORAFI A
(1) K.R. Baker: "Introduction to Sequencing and Scheduling". J. Wiley.
(1974).
(2) K.R.Baker y J.B. Martin: "An Experimental Comparison of Solution
Al9orithms the single-machine Tardiness Problem". Naval Res. Log. Quar-.
21, n~ 1. (1974).
(3) S. French: "Sequencing and Scheduling: An Introduction to the Mathematics
of the Job-Shop". Ellis Horwood limited. (1982).
(4) E.L. Lawler: "An Pseudopolynomial Algorithm for Sequencing Jobs to
Minimize Total Tardiness". Ann. Disc. Math. 1, 331 - 342. (1977).
(5) f.L. Lawler; J.K. Lenstra y A.H.G. Rinnooy Kan: "Recent Developments in
deterministic sequencing and Scheduling: a survey", en Deterministic and
Stochastic Scheduling editado por Dempster, et al. Reidel Publishing
Company. ( 1982).
(6) J.K. Lenstra, A.H.G. Rinnooy Kan y P. Brucker: "Complexity of Machine
Scheduling Problems". Ann. Disc. Math. 1, 343 362. (1977).
(7) J.K. Lenstra, A.H.G. Rinnooy Kan: "Complexity of scheduling under
Precedence Constraints". Q:>er. Res . 26, n. l, 22 - 35. ( 1978).
(8) C.N. Potts y L.N. Van Wassenhove: "Dynamic Programming and Decomposition
Approaches for the Single Machine Total Tardiness Problem". European
Journal of Q:>er. Research, 32, 405 - 414. (1987).
(9) J. Sicilia y D. Alcaide: "Algoritmo aproximado para la minimizaci6n de la
tardanza total sobre una maquina XIV Jornadas Hispano-Lusas de
Matematicas. Tenerife. (1989).
(10) J. Sicilia y D. Alcaide: "Minimizaci6n de la tardanza total considerando
diferente disponibilidad de los trabajos". Actas de la XVIII Reunion
Nacional de Estadistica e I nvestigaci6n Q:>erati va. Santiago de
Compostela. (1989).
226
© Del documento, de los autores. Digitalización realizada por ULPGC. Biblioteca Universitaria, 2017