Cursos de Grado

Ministerio de Educación, Ciencia y Tecnología
Universidad Nacional de San Luis
FACULTAD DE CS. FISICO MAT. Y NAT.

ANEXO II

PROGRAMA DEL CURSO: OPTATIVA
DEPARTAMENTO DE: INFORMATICA
AREA: Area II: Sistemas de Computaci	AÑO: 2003 (Id: 2380)
Estado: En tramite de Aprobación

**I - OFERTA ACADÉMICA**
CARRERAS PARA LAS QUE SE OFRECE EL MISMO CURSO	PLAN DE ESTUDIOS ORD. Nº	CRÉDITO HORARIO
		SEM.	TOTAL
LIC. EN CIENCIAS DE LA COMPUTACION	11/98	8,6	120

**II - EQUIPO DOCENTE**
Funciones	Apellido y Nombre	Total hs en este curso	Cargo y Dedic.	Carácter
Responsable	GALLARD, RAUL HECTOR	60 hs.	PROFESOR TITULAR EXC.	Efectivo

**III - CARACTERÍSTICAS DEL CURSO**
CREDITO HORARIO SEMANAL				MODALIDAD	REGIMEN
Teórico/ Práctico	Teóricas	Prácticas de Aula	Práct. de lab/ camp/ Resid/ PIP, etc.		1c
Hs.	60 Hs.	Hs.	60 Hs.	Promocional	Otro:
					Duración: 14 semanas
					Período del 15/3/03 al 27/6/03

**IV.- FUNDAMENTACION**
Los problemas de scheduling, implican la asignación de recursos a tareas con restricciones en el tiempo. Son problemas de optimización combinatoria de dificil solución y la mayoría de ellos se clasifican como NP- duros o NP-completos. Dada su dificultad y su impacto económico en las plantas productivas son de interés creciente en la investigación, desarrollando heurísticas cada vez mas precisas y veloces. El curso introduce los problemas de scheduling en ambientes de máquina única pues éstos siven de base para ambientes y objetivos más complejos

**V.- OBJETIVOS**
El curso introduce los problemas de scheduling de máquina única en los sistemas productivos abordando objetivos no triviales. Para ello se presentarán inicialmente problemas para los cuales existe un algoritmo que provea soluciones óptimas o satisfactorias en tiempo polinomial. Se implementarán heurísticas convencionales y se las contrastará con algoritmos evolutivos multirecombinados y alternativas de representación para insertar conocimiento específico del problema. Se espera que el alumno adquiera conocimientos de los distintos problemas de scheduling y de métodos alternativos, actualmente utilizados en la práctica y en la investigación científica, para resolverlos.

**VI. - CONTENIDOS**
El problema general de Scheduling. Medidas de performance Enfoques para la solución del problema de scheduling. Fundamentos de scheduling de máquina única. Métodos matemáticos para la solución. Nuevas direcciones. Introducción a los Algoritmos Evolutivos (AEs) basados en algoritmos genéticos.

**VII. - PLAN DE TRABAJOS PRÁCTICOS**
A) desarrollo prácticos de aula y de computación. B) desarrollo de proyectos de software grupales.

**VIII - RÉGIMEN DE APROBACIÓN**
El régimen es sólo promocional. Promoción a través de desarrollo de prácticos, proyectos de software grupales y una evaluación conceptual.

**IX.a - BIBLIOGRAFÍA BÁSICA**
Bäck T: Evolutionary algorithms in theory and practice. Oxford University Press, 1996. Esquivel S., Gallard R., Michalewicz Z., - MCPC: Another Approach to Crossover in Genetic Algorithms- Proceedings of the 1st Congreso Argentino de Cs. de la Computación, pp 141-150, Universidad Nacional del Sur, October 1995. Esquivel S., Leiva A., Gallard R., - Multiple crossover per couple in genetic algorithms. Proc. of the 4th IEEE International Conf. on Evolutionary Computation (ICEC\'97), pp 103-106, Indianapolis, USA, April 1997. Esquivel S., Leiva H.,.Gallard R., Multiple Crossovers Between Multiple Parents To Improve Search In Evolutionary Algorithms - Submitted to the 1999 Int. Congress on Evolutionary Computation. Goldberg D. E., - Genetic Algorithms in Search, Optimization & Machine Learning,Addison Wesley, 1989. Michalewicz Z. - Genetic Algorithms + Data Structures = Evolutions Programs, Springer-Verlag, Third, Extended Edition, 1996 Morton T., Pentico D.: Heuristic scheduling systems. Wiley Interscince. 1993 Pinedo M,: Scheduling - Theory, Algoritms, and Systems - PRENTICE HALL -1995. Tsujimura Y., Gen M., Kubota e., Flow shop scheduling with fuzzy processing time using genetic algorithms. The 11th Fuzzy Systems Symposium pp 248-252. Okinawa. 1995. Taillard, E. Benchmarks for basic scheduling problems, European Journal of Operational Research, vol. 64, pp. 278-285, 1993.

**IX b - BIBLIOGRAFÍA COMPLEMENTARIA**
Esquivel S.C., Zuppa F., Gallard R., “Hybrid-Multirecombined Evolutionary Algorithms for Flow Shop Scheduling”. En International Journal of Knowledge Based Intelligent Engineering Systems, Special Edition on Soft Computing and Intelligent Systems for Industry. University of Brighton. Vol 6, No. 4, pp 186-191, Octubre 2002. Pandolfi D., De San Pedro M., Villagra A., Vilanova G., Gallard R.- “ Studs mating immigrants in evolutionary algorithm to solve the earliness-tardiness scheduling problem” . En Cybernetics and Systems del Taylor and Francis Journal, (U.K.), pp 391-400, June 2002. Esquivel S., Ferrero S., Gallard R.- “Parameter settings and representations in pareto-based optimisation for job shop scheduling” . En Cybernetics and Systems del Taylor and Francis Journal, (U.K.), pp 559-578, September 2002. Esquivel S., Ferrero S., Gallard R., Salto C., Alfonso H. Schütz M., ¨Enhanced evolutionary algorithms for single and multiobjective optimization in the job shop scheduling problem¨. Journal of Knowledge Based Systems, Vol 15/1-2, pp 13-25, Elsevier, January 2002. Esquivel S., Gatica C., Gallard R.- “Performance of Evolutionary Approaches for Parallel Task Scheduling under Different Representations”, Lecture Notes in Computer Science, LNCS 2279, pp 41-50, Springer Verlag, april 2002. Esquivel S., Leguizamón G., Zuppa F., Gallard R., - “A performance comparison of alternative heuristics for the flow shop scheduling problem”, Lecture Notes in Computer Science, LNCS 2279, pp 51-60, Springer Verlag, april 2002. Esquivel S., Gatica C., Gallard R. Conventional and Multirecombinative Evolutionary Algorithms for the Parallel Task Scheduling Problem. Lecture Notes in Computer Science, LNCS 2037, pp 223-232, Springer Verlag 2001. Esquivel S., Gatica C., Gallard R., - “A Genetic Approach using Direct Representation of Solutions for the Paralell Task Scheduling Program”, Journal of Computer Science and Technology, Vol. III, pág. 7 –13, PGNAU, ISTEC, http://journal.info.unlp.edu.ar/, 2000.

COMPLEMENTO DE DIVULGACION

**OBJETIVOS DEL CURSO**
El curso introduce los problemas de scheduling de máquina única en los sistemas productivos abordando objetivos no triviales. Se espera que el alumno adquiera conocimientos y capacidad de evaluar los distintos problemas de scheduling y de métodos alternativos, actualmente utilizados en la práctica y en la investigación científica, para resolverlos.

**PROGRAMA SINTETICO**
1. El problema general de Scheduling. Scheduling como estrategia. La idea general. Buenos schedules. Agrupación de actividades y recursos. Problemas extendidos; reconfiguración. Niveles de scheduling. Ambientes de máquinas: Máquina única, máquinas paralelas, flow shop, flexible flow shop, open shop y job shop. 2. Medidas de performance: Completion time, Flowtime, Lateness, Tardiness, Earliness. Funciones objetivas a optimizar: makespan, weighted flowtime, weighted lateness, weighted tardiness, weighted number of tardy jobs, weighted early-tardy jobs. Maximum flowtime, maximum lateness y maximum tardiness. Restricciones:release dates, due dates, preemptions, sequence dependent set up times. 3. Enfoques para la solución del problema de scheduling. Categoría de los enfoques. Enfoques anteriores y actuales. Heurísticas convencionales. Nuevas heurísticas, Tabu search, simulated annealing, algoritmos evolutivos, enumeración parcial. Métodos de cuello de botella. 4. Fundamentos de scheduling de máquina única. Métodos de relajación. Clasificación de los problemas de máquina única. Modelo dinámico. Proposiciones fundamentales. Problemas estáticos regulares. Objetivos basados en utilización y en flujo. 5. Métodos matemáticos para la solución. Métodos clásicos. Intercambio de pares. Hill climbing. Prioridades. Búsqueda en el vecindario. Programación dinámica. Branch and bound (ramificación y acotación). 6. Nuevas direcciones. Beam search, programación dinámica aproximada, búsqueda extendida en el vecindario. Revisión de tabu search, simulated annealing y algoritmos evolutivos. 7. Introducción a los Algoritmos Evolutivos (AEs) basados en algoritmos genéticos. Mejoras en los AEs via la multirecombinación. Múltiple crossover sobre múltiples padres en optimización multi y simple objetivo. Conocimiento específico del problema. Implementación de Algoritmos Evolutivos y comparación de resultados sobre distintas instancias de los problemas de scheduling.

**IMPREVISTOS**
No se preveen imprevistos.