Prof. Peter Anderson
Rochester Institute of Technology, USA

Prof. Mark Girolami
University of Paisley, Scotland, United Kingdom

The task of scheduling is the allocation of jobs over time when limited resources are available, where a number of objectives should be optimized, and several constraints must be satisfied. Scheduling problems differ according to the resource environment, restrictions and objective functions to be considered.Very common scheduling problems belongs to the NP-hard problems. Consequently, diverse heuristics has been developed to face them. Evolutionary algorithms showed their effectiveness and efficiency to solve a wide variety of scheduling problems. Latest improvements in Evolutionary Computation include multirecombination and parallelism. This tutorial will show diverse novel evolutionary techniques applied to single machine, parallel machines, job shop and flow shop scheduling problems. Single and multicriteria optimization of diverse objectives will be discussed.

Contents

• The general scheduling problem.
  Schedule classes: nondelay, active and semiactive. Performance measures: Completion Time, Flowtime, Lateness, Tardiness, Earliness. Objective functions to optimize: makespan, weighted flowtime, weighted lateness, weighted tardiness, weighted number of tardy jobs, weighted early-tardy jobs. Maximum flowtime, maximum lateness and maximum tardiness. Restrictions: release dates, due dates, preemptions, sequence dependent set up times. Machine environments: Single machine, Parallel machines Flow shop and Job shop.
• Improved Evolutionary Algorithms.
  Introduction to a multiplicity feature in evolutionary algorithms. Evolution of the multiplicity feature. Multiple crossovers per couple (MCPC). The latest multirecombinative approach: Multiple crossovers on multiple parents (MCMP). Hybridization: evolutionary algorithms and local search.
• Applications of MCPC and MCMP in single single machine, parallel machines flow shop and job shop scheduling problems. Single and and multiobjective optimization
• Parallel evolutionary algorithms.
  Their application to scheduling problems.

Bibliography

• Bäck T., Fogel D., Michalewicz Z.: Handbook of Evolutionary Computation. Oxford University Press, 1997.
• Esquivel S., Leiva H.,.Gallard R., "Multiplicity in genetic algorithms to face multicriteria optimization", Proceedings of the 1999 Congress on Evolutionary Computation (IEEE). Washington DC, pp 85-90.
• Esquivel S., Zuppa F., Gallard R., ¨Contrasting Conventional and evolutionary Approaches for the Flow Shop Scheduling Problem¨, Second International ICSC Symposium of Intelligent Systems EIS 2000, June 27-30 , 2000, University of Paisley, Scotland U.K.
• Esquivel S., Leiva H.,.Gallard R., "Multiple crossovers between multiple parents to improve search in evolutionary algorithms", Presentado y publicado en Proceedings of the 1999 Congress on Evolutionary Computation (IEEE). Washington DC, pp 1589-1594
• Esquivel S., Leiva A., Gallard R. –"Selection Mechanisms in Evolutionary Algorithms"- "- in Fundamenta Informaticae, IOS Press, vol 35, No 1-4, pp 17-33. Aug. 1998.
• 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

Short Biography
Raúl Gallard received the Computador Científico degree from the University of Buenos Aires, Argentina, the Master of Sciences degree from the University of Aston in Birmingham, UK, and the Ph D. degree, from the Institute of Computer Science of the Polish Academy of Sciences, Varsovia. In 1975 he began working as Assistant Professor, then became Associated Professor in 1977 and Full Professor in 1985. In 1984 created the GIST-COMP (Interest Group on Computer Systems) and from that time he conducted six different projects in the area, all of them supported by the university and/or the CONICET (Argentinian Research Council) and the ANCYPT (Argentinian National Agency for the Promotion of Science and Technology). Three other projects in the Universidad Nacional de Rio Cuarto, Universidad Nacional de la Pampa and Universidad Nacional de la Patagonia Austral were recently created, and are developed under his supervision. All of them are related to theory and applications of Evolutionary Computation. In 1988-1989 was invited by the ICTP (International Centre for Theoretical Physics) as visiting scientist, where a project on self healing systems was developed. In 1995 and 1996 he was designated as member of the Peers Committee for the FOMEC (Funds for the Improvement of the Teaching of Sciences) of the Ministry of Education. Many universities invited him as external advisor and evaluator of research projects. He was member of the Program Committee of many Argentinean computer science conferences and congresses. He has been reviewer (1990-1993), of the Computer Journal (British Computer Society), belongs to the reviewers committee of the Integrated Computer-Aided Engineering Journal (John Wiley). Currently is member of various program committees of national and international congresses and conferences (PPSN VI, CACIC’ 2000, ICSC, IASTED, ICEC’99, EIS2000). He is member of the International Academic Advisory Council of NAISO (Natural and Artificial Intelligent Systems Organization), Canada. In 1997-98 he was designated as member of the Evaluators Committee of the CONICET and as an External Evaluator of the UBA, UTN, UNS, UNSJ, UNSA, UNT and other national universities. In 1999 he was designated as evaluator for the Regional Centro Oeste categorization process, to assign categories III y IV of the Plan de Incentivos for research and academic activities. Recently he was called by the ANPCYT to audit selected projects of Engineering and Technology, developed during 1998. Dr. Gallard is member of SADIO (Argentinean Society of Operational Research and Informatics), voting member of the ACM, member of the IEEE and member of the IASTED (International Association of Science and Technology for Development). He is co-author of two text books Redes de Computadoras edited by the Argentinean-Brazilian Program on Research and Advanced Studies on Informatics (1993) and Computación Evolutiva: Conceptos y Aplicaciones (1997) to be edited by the Universidad Nacional de la Plata. He is co-autor (1999) of the chapter "Selection Mechanisms in Evolutionary Algorithms", in the book "Evolutionary Computation". IOS Press. He has given many seminars in Argentina, Spain, U.K., USA, Poland, and Germany. Currently he advises various grant holders, Master thesis and Doctoral thesis.

Prof. Juan M. Corchado
University of Salamaca, Spain

Biography
Juan M. Corchado (Ph.D.) received a PhD. in Artificial Intelligence from the University of Paisley (UK) in 2000. At present he is Associate Professor at the University of Salamanca (Spain), previously he was Sub-director of the Escuela Superior de Ingeniería Informática of the University of Vigo (Spain, 1998-00) and Researcher at the University of Paisley (UK, 1995-98). He has been a research collaborator with the Plymouth Marine Laboratory (UK) since 1993. He has worked on several Artificial Intelligence (AI) Research projects sponsored by Spanish and European public and private Institutions. He is the co-author of over 50 books, book chapters, journal papers, technical reports, etc. published by organisations such us IEEE, IEE, ACM, AAAI, Springer Verlag, Elsevier, Morgan Kaufmann, etc, most of these present practical and theoretical achievements of Hybrid AI Systems.

Abstract
Research into artificial intelligence (AI) has produced various hybrid problem-solving methods, which may be applied to give more powerful computer based problem solving capabilities than may be obtained using purely algorithmic methods. The reason for the application of an AI approach is very often precisely because the nature of the problem to be addressed is such that no appropriate algorithm is either known or is applicable. For example, if the knowledge about a problem is incomplete or fuzzy, it may be difficult to select or to develop an algorithm or even an AI approach to solve it. It is in such situations where hybrid AI systems may be effective. Case-based reasoning systems have proved to be successful in situations where prior experience of solving similar problems is available. But the nature of a complex problem solving situation may be such that there are different aspects of the problem that may best be addressed through the application of several distinct problem solving methodologies. In particular, the application of artificial intelligence methods to the problem of describing the ocean environment offers potential advantages over conventional algorithmic data processing methods; an AI approach is, in general, better able to deal with uncertain, incomplete and even inconsistent data. Neural network, case-based and statistical forecasting techniques could be used separately in situations where the characteristics of the system are relatively stable (Lees et al., 1992). However, time series forecasting, based on neural network or statistical analysis, may not provide sufficiently accurate forecasting capability in chaotic areas such as are found near a front (i.e. an area where two or more large water masses with different characteristics converge). During this tutorial it will be presented a universal forecasting strategy, in which the term universal is taken to mean a forecasting tool which is able to operate effectively in any location, of any ocean. It will be described the application of a hybrid artificial intelligence approach to prediction in the domain of oceanography. A hybrid artificial intelligence strategy for forecasting the thermal structure of the water ahead of a moving vessel is presented. This approach combines the ability of a case-based reasoning system for identifying previously encountered similar situations and the generalising ability of an artificial neural network to guide the adaptation stage of the case-based reasoning mechanism. The system has been successfully tested in real time in the Atlantic Ocean; the results obtained are presented and compared with those derived from other forecasting methods. The case-based reasoning system is used to select a number of stored cases relevant to the current forecasting situation. The neural network retrains itself in real time, using a number of closely matching cases selected by the CBR retrieval mechanism, in order to produce the required forecasted values.