1 Universidad de Santiago de Chile Departamento de Ingeniería Informática ALFA Project Víctor Parada [email protected] www.diinf.usach.cl/vparada www.optimos.usach.cl Profesor Visitante en el Departamento de Ingeniería Industrial – Centro de Gestión de Operaciones –CGO Universidad de Chile

2 Universidad de Santiago de Chile Image Gallery: http://www.usach.cl/index2.php?id=7196&nom=Estudiantes&pag=6515

3 Universidad de Santiago de Chile www.usach.cl www.usach.cl Departamento de Ingeniería Informática www.diinf.usach.cl Undergraduate Conputer Science Engineering (Since 1982, 700 students). Master in Computer Science Engineering (30 students). Doctorate in Science of Computing and Informatic (5 students).

4 Research Topics

5 One-dimensional Problem Two-dimensional Problem Cutting stock problem

6 Two-dimensional Problem Cutting stock problem Three-dimensional Problem

7 Cutting stock problem a b c d e 3 2 3 1 5 a d e a b b c Plate f 5

8 8 2 5 2 2 1 3 1 2 b i x i 4 Cutting Stock Problem Example

9 Min Z(x) = WL -  w i l i x i s.t. i) 0  x i  b i  i  R ii) x i integer  i  R iii) Cortes Factibles: - Guillotina - Sobreposición Wang, P. 1983, Opn. Res. (WA) Vasko, F. 1989 Comp. Ind. Eng. Oliveira, J. & Ferreira, J. 1990, EJOR (MW) Viswanathan, K. & Bagchi, A. 1993 Opn. Res. Parada, V. et al. 1995, EJOR (AAO*) Parada, V. et al. 1995, Nissen Ed. (GAO) Parada, V. et al. 1998, Comp&Ops. Res. (SA) Cutting Stock Problem

10 Solution Methods Wang’s algorithm Wang (WA) Constructive rectangles are generated. Vertical and horizontal combinations. An internal loss is defined. Trim (parameter  ). Oliveira & Ferreira (MW) Modifies Wang’s Method. Defines external loss.

11 Solution Methods Wang’s algorithm Algorithm - WA. Begin Choose a value for , 0    1; Define L (0) = F (0) ={ p 1, p 2,..., p n } k = 0 While F (k)   k= k+ 1; Determine F (k), a the set of rectangles T = { R 1, R 2,..., R n } satisfying: (i)T is a combination of rectangles belonging to L (k-1), (ii)the total loss of each R i is less than or equal to  1 HW, (iii)R i belonging to T do not surpass the limits b i of each piece, Set L (k) = L (k-1)  F (k), eliminating equivalent patterns; Choose the rectangle of L (k) with minimum total loss, End.

12 AAO* Solution Methods And/Or Graph P P1P2 P3

13 A solution is represented by means of And/Or graphs. A node represents a combination between pieces. Generalizes methods WA and MW. Optimal solutions can be obtained. AAO* Algorithm AAO* Solution Methods

14 Simulated Annealing Algorithm - SA. Begin Find an initial solution i and an initial value for T 0 ; t = 0; Repeat n = 0; Repeat Generate solution j neighbor to i; d = f(j) - f(i); If d  0 then i = j; Else If random(0,1) < exp{-d/T} then i = j; n = n + 1; Until n = N(t); t = t + 1; T = T(t); Until stop criterion achieved; End. Solution Methods

15 Algorithm Annealing (SA) Solution Methods P1 P2 (0,0) X Y (9x7) 3 6 P2 (9,7) (6,0) G1 G2P1 (0,0) (9,7) B1 B2 B3 (0,3) (0,0) (6,3) (4,7) (4,3) (6,7) (0,3) (6,7) (0,0) (6,7) 6x3 4x4 G2 G1 a) b) 9 7 Simulated Annealing

16 Genetic algorithm Genetic Algorithm (GAO) It is based on the evolutionary process, used in Genetic Algorithms. Syntactic binary trees representing the problem. A constructive solution is generated. The solution is a string. Solution Methods

17 Genetic algorithm Resolution Methods “VVaaHHbbVcc” V VH aaHV bccb

18 Analysis between WA, MW, AAO*, SA and GAO. For WA, MW and AAO*  = (0, 0.08 and 1). For SA the Nº of iterations iter = (10 and 100). For GAO the Size of population pop = (n y 2n). 1000 instances of grouped problems  = [2, 39] ). Platform : Silicon Graphics Challenge. 2 processors (150 MHz). 256 MB RAM. Quality, Running time and % of resolution are measured. Numerical Results

19 All Methods - % of Resolution Comparative Analysis

20 All Methods - % of trim loss

21 Comparative Analysis All Methods - Running Time

22 Comparative Analysis GAO and SA - Running Time

23 Comparative Analysis GAO and SA Methods - % of Trim loss

24 Characterization Running Time High T resp > 1 min. Medium 5 sec.  T resp  1 min. Low T resp < 5 sec. Problem size Small   4 medium 5   15 Large  16 Comparative Analysis

25 Conclusions Several methods which resolves the Constrained Guillotine 2- Dimensional Cutting Problem have been implemented The theoretical results have been validated through 1000 instances of the CGTCP Problems have been organized according to their complexity degree Only GAO y SA could be considered reliable For small instances it is better to use exact algorithms

26 WWW.OPTIMOS.USACH.CL A web site to solve on-line optimization problems

27 http://www.optimos.usach.cl Pequeñas Empresas: Problemas de optimización de materia prima Realidad Industrial

28 http://www.optimos.usach.cl Empresas: Problemas de planificación de la producción Problemas de pronósticos de demanda

29 http://www.optimos.usach.cl

30 Objetivo de Optimos Difundir conocimiento sobre el área Optimización de manera amena y clara a diversos tipos de usuarios y posibilitar la resolución de problemas de optimización de manera “on-line”. http://www.optimos.usach.cl

31 Requerimientos de empresariales: Resolución “on-line” de: Problemas de corte de piezas guillotinables. Problemas de corte de piezas no guillotinables. Problema de organización de actividades. Definición de horarios. Problema de distribución de energía eléctrica. Problemas de determinación de pit final...

32 http://www.optimos.usach.cl Requerimientos de enzeñanza: Resolución “on-line” de: Problemas de programación lineal (Simplex) Problemas de Programación entera (B&B) Árboles de Cobertura de Costo mínimo. Flujo de Costo mínimo. Flujo Máximo.

33 Estructura del Sitio NoticiasEventos Parte Dinámica P1P2P3P4..Pn Problemas PLPNLPE P.M. AGBTSA M.H. Métodos de Resolución de Problemas Parte Estática Juegos de Optimización Clase de Optimización

34

35 http://www.optimos.usach.cl Conclusiones: Impacto en el sector productivo. Difusión de las potencialidades de la optimización. Alto costo de manutención. Distribución en diversas unidades académicas.