ANÁLISIS DE ANÁLISIS DE EMPAQUETAMIENTO Y EMPAQUETAMIENTO Y

PROBLEMAS DE PROBLEMAS DE PARTICIÓN PARTICIÓN

RELACIONADOSRELACIONADOS

E.G. CoffmanE.G. CoffmanD.S. JohnsonD.S. Johnson

P.W. ShorP.W. ShorG.S. LuekerG.S. Lueker JOHANA JOHANA

ROMEROROMEROLEON F. GOMEZ LEON F. GOMEZ C.C.

PPROBLEMAS ROBLEMAS CCONSIDERADOSONSIDERADOS

Empaquetamiento en casillas Empaquetamiento en casillas (BP)(BP)

Dados c>0 y el conjunto S={XDados c>0 y el conjunto S={X11…X…Xnn} con } con 0<X0<Xiic, 1c, 1 i i n, particione S en el n, particione S en el minimo numero de subconjuntos tales minimo numero de subconjuntos tales que la suma de los Xi en cada que la suma de los Xi en cada subconjunto no sea mayor que c.subconjunto no sea mayor que c.

PPROBLEMAS ROBLEMAS CCONSIDERADOSONSIDERADOS

Programación de un Multiprocesador (MS)Programación de un Multiprocesador (MS)

Dado un entero m Dado un entero m 1 y un conjunto S={X1 y un conjunto S={X11……XXnn}, particione S en m subconjuntos tales que }, particione S en m subconjuntos tales que entre todas las particiones, la maxima suma de entre todas las particiones, la maxima suma de los Xi en un subconjunto este minimizada.los Xi en un subconjunto este minimizada.

Makespan:Makespan: Tiempo de terminación de la Tiempo de terminación de la última tarea en finalizar.última tarea en finalizar.

NNOTACIÓNOTACIÓN• Conjunto a particionar se denota por la lista Conjunto a particionar se denota por la lista

Ln=(X1,…Xn).Ln=(X1,…Xn).

• Si H es una heurística Si H es una heurística MSMS entonces entonces H(Ln, m)H(Ln, m) denota el makespan generado. (m es el denota el makespan generado. (m es el número de procesadores).número de procesadores).

• Si H es una heurística Si H es una heurística BPBP entonces entonces H(Ln)H(Ln) denota el número de casillas con capacidad denota el número de casillas con capacidad unitaria en las que H empaqueta los items de unitaria en las que H empaqueta los items de Ln.Ln.

ANÁLISIS ANÁLISIS PROBABILÍSTICOPROBABILÍSTICO

• Los Xi son tomados como muestras Los Xi son tomados como muestras independientes de una variable aleatoria X independientes de una variable aleatoria X con una distribución F(x) dada. con una distribución F(x) dada.

• El El propósito es lograr una estimación de propósito es lograr una estimación de distribuciones tales como P[H(Ln) distribuciones tales como P[H(Ln) x] u x] u obtener valores esperados tales como obtener valores esperados tales como E[H(Ln,m)], donde las esperanzas estan sobre E[H(Ln,m)], donde las esperanzas estan sobre todas las muestras de n items Ln=(X1 ,…, Xn).todas las muestras de n items Ln=(X1 ,…, Xn).

ALGORITMOS BPALGORITMOS BPAlgoritmo Next Fit (NF):Algoritmo Next Fit (NF): próximo en ser próximo en ser encajado.encajado.

1. Empaquetar X1 en B1(primer casilla)1. Empaquetar X1 en B1(primer casilla)

2. Para i=2 hasta n2. Para i=2 hasta n•Chequear la última casilla no vacia Bj. Si Chequear la última casilla no vacia Bj. Si Xi encaja en ésta, guardar Xi en Bj. De lo Xi encaja en ésta, guardar Xi en Bj. De lo contrario, guardar Xi en la casilla vacia contrario, guardar Xi en la casilla vacia Bj+1. Esta se convertira en la nueva casilla Bj+1. Esta se convertira en la nueva casilla no vacia con más alto subindice.no vacia con más alto subindice.

ALGORITMOS BPALGORITMOS BPAlgoritmo First Fit (NF):Algoritmo First Fit (NF): primero en primero en

encajar.encajar.

1. 1. Empaquetar X1 en B1.Empaquetar X1 en B1.

2. Para i= 2 hasta n2. Para i= 2 hasta n• Guardar Xi en la primera casilla no Guardar Xi en la primera casilla no

vacia con menor subindice en la que vacia con menor subindice en la que encaje. Si no encaja en ninguna, encaje. Si no encaja en ninguna, guardar Xi una casilla vacia. guardar Xi una casilla vacia.

ALGORITMOS BPALGORITMOS BPAlgoritmo Best Fit (NF):Algoritmo Best Fit (NF): mejor mejor

encajado.encajado.

1. 1. Empaquetar X1 en B1.Empaquetar X1 en B1.

2. Para i= 2 hasta n2. Para i= 2 hasta n• Guardar Xi en la casilla no vacia en Guardar Xi en la casilla no vacia en

la que encaje mejor, es decir, en la la que encaje mejor, es decir, en la que tenga la menor capacidad sin que tenga la menor capacidad sin usar. Si no encaja en ninguna, usar. Si no encaja en ninguna, guardar Xi una casilla vacia. guardar Xi una casilla vacia.

ALGORITMOS BPALGORITMOS BPVesiones mejoradas:Vesiones mejoradas:

•Algoritmo NFDAlgoritmo NFD•Algoritmo FFDAlgoritmo FFD•Algoritmo BFDAlgoritmo BFD

Estos se aplican a la lista (XEstos se aplican a la lista (X(n)(n),…, X,…, X(1)(1)) ) donde Xdonde X(i)(i) es el i-ésimo items mas es el i-ésimo items mas pequeño.pequeño.

ANÁLISIS DE LOS ANÁLISIS DE LOS ALGORITMOS BPALGORITMOS BP

Con X Con X U(0,1) U(0,1)NFNF: E[W: E[WNFNF(Ln)] (Ln)] n/6 n/6

FFFF: E[W: E[WFFFF(Ln)]=(Ln)]=(n(n2/32/3))

BFBF: E[W: E[WBFBF(Ln)]=(Ln)]=((((n)logn)log3/43/4n)n)

NFDNFD: E[W: E[WNFDNFD(Ln)]=(.145...)n(Ln)]=(.145...)n

FFD,BFD,OPTFFD,BFD,OPT: E[W: E[WHH(Ln)]=(Ln)]=((n))n))

(E[W(E[WHH(Ln)]=E[H(Ln)-(Ln)]=E[H(Ln)-(Ln)] = E[H(Ln)]-(Ln)] = E[H(Ln)]-n/2)n/2)

ALGORITMOS MSALGORITMOS MSList Scheduling(LS):List Scheduling(LS): programación programación de una listade una lista1. Programar X1 en P11. Programar X1 en P12. Para i =2 hasta n2. Para i =2 hasta n• Se programa Xi en el procesador que Se programa Xi en el procesador que tenga la menor carga de trabajo.tenga la menor carga de trabajo.

Largest processing time(LPT):Largest processing time(LPT): Tiempo más largo de procesamiento. Tiempo más largo de procesamiento. Algoritomo LS, más ordenamiento Algoritomo LS, más ordenamiento decreciente inicial de la lista de tareas.decreciente inicial de la lista de tareas.

ALGORITMOS MSALGORITMOS MSLargest-fist differencing(LFD):Largest-fist differencing(LFD): La La diferencia más grande primero. (m=2)diferencia más grande primero. (m=2)

Para i=1 hasta nPara i=1 hasta nSe escogen las tareas X y Y más largas en Se escogen las tareas X y Y más largas en lista Lnlista Ln(i) (i) Estas tareas se diferencias en la Estas tareas se diferencias en la lista Lnlista Ln(i+1) (i+1) que va a ser igual a Ln que va a ser igual a Ln(i)(i), , reemplazando las tareas X y Y por la tarea|reemplazando las tareas X y Y por la tarea|X-Y|. (Ln= LnX-Y|. (Ln= Ln(1) (1) ).).

ALGORITMOS MSALGORITMOS MSLargest-fist differencing(LFD):Largest-fist differencing(LFD): La La diferencia más grande primero. (m=2)diferencia más grande primero. (m=2)

LnLn(n)(n) será una lista con un único elemento. será una lista con un único elemento. Las tareas diferenciadas en cada lista se Las tareas diferenciadas en cada lista se van a programar en procesadores distintos, van a programar en procesadores distintos, buscando que la diferencia entre las cargas buscando que la diferencia entre las cargas de trabajo de estos sea el valor de Lnde trabajo de estos sea el valor de Ln(n).(n).

ANÁLISIS DE LOS ANÁLISIS DE LOS ALGORITMOS MSALGORITMOS MS

Con X Con X U(0,1) U(0,1)

LSLS: E[A: E[ALSLS(Ln,2)] = 1/6(Ln,2)] = 1/6

LPTLPT: E[A: E[ALPTLPT(Ln,2)] (Ln,2)] c/[2(n+1)] c/[2(n+1)]

LFD*LFD*: E[A: E[ALFD*LFD*(Ln,2)]=O(n(Ln,2)]=O(n-c*log n-c*log n))

(A(Ahhn,mn,m)]=[m*H(Ln,m)-)]=[m*H(Ln,m)-(Ln)]/m (Ln)]/m

TÉCNICAS ANALÍTICASTÉCNICAS ANALÍTICASCadenas de MarkovCadenas de Markov

Para el algoritmo LS con m= 2 Para el algoritmo LS con m= 2 procesadoresprocesadores

La Xi son v.i.i.d. Aleatorias, y {Vi}La Xi son v.i.i.d. Aleatorias, y {Vi}i i 0 0 es es una cadena de Markov. Entonces se una cadena de Markov. Entonces se tiene:tiene:

E[AE[ALSLS(Ln,2)] E[Vi]/2= 1/6(Ln,2)] E[Vi]/2= 1/6

0i ,0

,1|,| 1 niXVVi ii

TÉCNICAS ANALÍTICASTÉCNICAS ANALÍTICASCadenas de MarkovCadenas de Markov

Para el algoritmo NF Para el algoritmo NF

{NF(Ln),ln}{NF(Ln),ln}n n 1 1 es una cadena de es una cadena de markov bivariable. ln es la suma de los markov bivariable. ln es la suma de los tamaños de los items de Ln, tamaños de los items de Ln, empaquetados.empaquetados.

Con X Con X U(0,1), E[W U(0,1), E[WNFNF(Ln)] = n/6+6 (Ln)] = n/6+6

TÉCNICAS ANALÍTICASTÉCNICAS ANALÍTICASLIMITESLIMITES•Limitando la función objetivo: Limitando la función objetivo: Encontrar g(Ln) tal que g(Ln) Encontrar g(Ln) tal que g(Ln) H(Ln) H(Ln) para toda Ln. En el caso promedio para toda Ln. En el caso promedio E[H(Ln)] E[H(Ln)] E[g(Ln)]. E[g(Ln)].

•Algoritmos dominantes:Algoritmos dominantes: Introducir un algoritmo más simple y Introducir un algoritmo más simple y fácil de analizar H´ , para el cual se fácil de analizar H´ , para el cual se pueda probar que H´(Ln) pueda probar que H´(Ln) H(Ln). H(Ln).

CORRESPONDECIA CORRESPONDECIA ESTOCASTICA PLANAESTOCASTICA PLANA

• Los problemas de Los problemas de correspondencia en una o mas correspondencia en una o mas dimensiones han surgido en el dimensiones han surgido en el analisis de diversos analisis de diversos empaquetamientos heurísticos.empaquetamientos heurísticos.

• MMnn denote una correspondencia denote una correspondencia maxima superior derecha de maxima superior derecha de puntos positivos a puntos puntos positivos a puntos negativos tal que si un positivo negativos tal que si un positivo en (x,y) es asociado a uno en (x,y) es asociado a uno negativo en (x',y'), luego x negativo en (x',y'), luego x x', x', yyy’y’

• UUnn denote denote el numero de puntos el numero de puntos que quedan sin asociar por Mque quedan sin asociar por Mnn

• Los limites asintóticos sobre el Los limites asintóticos sobre el valor experado estan dados valor experado estan dados por:por:

E[UE[Unn]=]=n log n log 3/43/4 n) n)

• MBF (Mejor encaje modificado) MBF (Mejor encaje modificado) acerca una casilla a cualquier acerca una casilla a cualquier item alejado siempre y cuando item alejado siempre y cuando la casilla reciba un item que no la casilla reciba un item que no sea mas grande que 1/2.sea mas grande que 1/2.

• Las casillas de MBF tienen al Las casillas de MBF tienen al menos dos ítemsmenos dos ítems

• Traza los items de Ln como Traza los items de Ln como puntos en la mitad izquierda puntos en la mitad izquierda del cuadrado unitario, de del cuadrado unitario, de manera que los Xi tienen una manera que los Xi tienen una coordenada “y” equivalente a coordenada “y” equivalente a 1-i/n y una coordenada 1-i/n y una coordenada “x”,denotada por X“x”,denotada por Xii..

• Si XSi Xii 1/2 o denotada por 1-X 1/2 o denotada por 1-Xii si 1/2 <Xsi 1/2 <Xii 1 1

• Una correspondencia MBF es Una correspondencia MBF es una correspondencia maxima una correspondencia maxima superior derechasuperior derecha

• El modelo difiere del original El modelo difiere del original en dos aspectos: en dos aspectos:

1. Los puntos son muestras en la 1. Los puntos son muestras en la mitad izquierda del cuadrado mitad izquierda del cuadrado unitariounitario

2. La coordenada x ha sido 2. La coordenada x ha sido separada de manera que x separada de manera que x pertenece a {0,1/n,….(n-1)/n}.pertenece a {0,1/n,….(n-1)/n}.

• observamos que MBF(Lobservamos que MBF(Lnn) es la ) es la suma del espacio ocupado suma del espacio ocupado (L(Lnn) y del espacio que no esta ) y del espacio que no esta ocupado, la mas reciente ocupado, la mas reciente cantidad limitada por Ucantidad limitada por Unn. De . De esta manera esta manera E[MBF(LE[MBF(Lnn)]=n/2+)]=n/2+n log n log 3/43/4 n) n)

PROGRAMACION LINEALPROGRAMACION LINEAL

• Si el tamaño de los items en Ln conforman un conjunto discreto, luego el BP es facilmente formulado como un programa entero.

• S1,…,SN este conformado por items de diferente tamaño en Ln y permitamos que mj 1 j N, sea el numero de items con tamaño Sj

• Definición: la i-esima Definición: la i-esima configuración posible es una configuración posible es una secuencia de enteros Csecuencia de enteros Cijij 0, 10, 1 j j N, tales que N, tales que

es decir, un conjunto de items es decir, un conjunto de items CCijij de tamano S de tamano Sjj 1 1 j j N que N que pueda ser empacado dentro de pueda ser empacado dentro de una casilla simpleuna casilla simple

11

j

N

j ijSC

• Si M denota el numero de Si M denota el numero de configuraciones posibles, luego,configuraciones posibles, luego,

donde {tdonde {tii*} resuelve el programa *} resuelve el programa entero: minimizar entero: minimizar ttii sujeto a sujeto a que tque tii 0, 1 0, 1 i i M y M y ttiiCCijij m mjj 11 j j N. N.

M

i in tLOPT1

*)(

• Las disminuciones de tales Las disminuciones de tales programas enteros conducen a programas enteros conducen a límites útiles para el análisis de límites útiles para el análisis de soluciones óptimas.soluciones óptimas.

TEMAS RELACIONADOSTEMAS RELACIONADOS

• Describe algunas de las preguntas mas importantes que se han generado de los estudios iniciales de probabilidad de BP y MS.

Variantes: Los problemas siguientes tienen la misma demostración o ejemplo Ln como BP.

• Cubierta de las casillas. La partición de Ln en un número maximo de subconjuntos (casillas) tales que cada una sume al menos 1.

• Empaquetamiento en casillas doble. Encontrar un subconjunto L’n Ln de máxima cardinalidad C(Ln,m) tal que L’n pueda ser particionado en m subconjuntos donde cada uno sume máximo 1

DIMENSIONES DIMENSIONES SUPERIORESSUPERIORES

• Las adaptaciones de BP a dos y Las adaptaciones de BP a dos y tres dimensiones tienen una tres dimensiones tienen una motivación practica motivación practica persuasiva, especialmente en persuasiva, especialmente en las aplicaciones de recorte de las aplicaciones de recorte de existencias.existencias.

• En cuanto al empaquetamiento En cuanto al empaquetamiento en dos dimensiones existe un en dos dimensiones existe un modelo probabilístico muy modelo probabilístico muy comun, en el cual, toda la comun, en el cual, toda la altura y ancho de los altura y ancho de los rectangulos se suponen como rectangulos se suponen como muestras independientes de muestras independientes de U(0,1)U(0,1)

LIMITES GENERALESLIMITES GENERALES

• Los límites inferiores para BP han sido utiles en la estimacion del costo de ciertas restricciones para el diseno de los algoritmos.

• Permiten evaluar el espacio que se pierde en promedio al usar algorítmos en línea

DISTRIBUCIONESDISTRIBUCIONES

• En los estudios de BP se ha hecho En los estudios de BP se ha hecho énfasis sobre la distribución énfasis sobre la distribución uniforme U(0,1), debido a que esto uniforme U(0,1), debido a que esto permite un análisis mas dócil.permite un análisis mas dócil.

• Los modelos de MS se han Los modelos de MS se han concentrado en U(0,1) y en concentrado en U(0,1) y en distribuciones exponenciales, por distribuciones exponenciales, por la misma razónla misma razón

INSTRUCCIONES PARA INSTRUCCIONES PARA ESTUDIOS LEJANOSESTUDIOS LEJANOS

• Existen problemas abiertos, Existen problemas abiertos, concernientes con distribuciones concernientes con distribuciones F(x) mas generales y con F(x) mas generales y con resultados mas precisos, limites resultados mas precisos, limites utiles sobre las constantes utiles sobre las constantes multiplicaticas ocultas en la multiplicaticas ocultas en la notacion asintóticanotacion asintótica