WATT Digest 2003, Issue 3 Date Issued : 1st July 2003 =============================================================== WATT Digest appears every 3 months and is automatically sent to all members of WATT. Send submissions/articles to Gareth Beddoe at grb@cs.nott.ac.uk Back issues of WATT digest can be viewed at http://www.asap.cs.nott.ac.uk/watt/index.html If you wish to subscribe/unsubscribe to WATT you should EMAIL Limin Han at The University of Nottingham. Limin's EMAIL address is lxh@cs.nott.ac.uk The WATT website can be found at http://www.asap.cs.nott.ac.uk/ASAP/watt/index.html The next issue (vol 3 : Iss 4) is due 1st October 2003. WATT Digest is edited by: Gareth Beddoe Automated Scheduling Optimisation and Planning Research Group School Of Computer Science and Information Technology University of Nottingham, Jubilee Campus Nottingham NG8 1BB United Kingdom Tel : +44 (0) 115 846 6525 http://www.cs.nott.ac.uk/~grb ============================================================= In this issue (#2003-02) 1. WATT EMAIL Groups 2. New WATT Members 4. 5th WATT Workshop at EURO/INFORMS 5. INTROS 2003 Call for Participation 6. The 1st MISTA Conference 7. Selected Papers from PATAT-2002 8. Special Issue of the Journal of Scheduling 9. EJOR Special Issue on Timetabling 10. EvoNet Summer School in Evolutionary Computation 11. EPSRC ISN Workshop on Applications of Constraint Programming in Scheduling 12. Items Wanted 13. Timetabling Bibliography 14. Problem Datasets 15. Timetabling Resources 16. Conferences of Interest to the Timetabling Community === 1. WATT EMAIL Groups ==================== To make an announcement, please send an email to this e-mail list. The e-mail will be forwarded to watt@cs.nott.ac.uk automatically. The e-mail list watt@cs.nott.ac.uk will continue to be used as a discussion group. If anybody wants to contribute, please send email only to watt@cs.nott.ac.uk. Members who do not want to be involved in discussions should send an e-mail to Limin Han (lxh@cs.nott.ac.uk). She will remove you from watt and add you to watt-announcement. 2. New WATT Members =================== On behalf of WATT I would like to welcome our new members: Ahrweiler, Chris (Germany) Alizadeh, Mohamed (Iran) Asn Ach, Roberto Javier (Bolivia) Baalman, Philippus (Netherlands) Chand, Atish (Fiji) Chuprat, Suriayati (Malaysia) Hammond, Michelle (United Kingdom) Helmy, Ayman (Egypt) Lissmaria, Lissmaria (India) Reddick, James (United Kingdom) Slechta, Petr (Czech Republic) Udugama Jalathge, Tharanga (Sri Lanka) A full list of members and their contact details can be found on the WATT website: http://www.asap.cs.nott.ac.uk/watt/members/members.html 3. 5th WATT Workshop at EURO/INFORMS ==================================== The 5th WATT Workshop will be held at the EURO / INFORMS Joint International Conference in Istanbul, Turkey, on July 6-10, 2003. Details of the EURO Conference can be seen on the Web page: http://www.istanbul2003.org/main.html The following papers are to be presented: Determining Feature Weights in a Case-Based Reasoning Approach to Nurse Rostering Gareth Beddoe and Sanja Petrovic Building Quality Timetables with Integer Programming Sophia Daskalaki and Theodore Birbas Scheduling the Italian Football League: an ILP-Based Approach Federico Della Croce and Dario Oliveri Please contact the workshop organiser Jonathan Thompson for more details at EMAIL: ThompsonJM1@cardiff.ac.uk 4. INTROS 2003 Call for Participation ===================================== An International Educational Workshop: INtroductory TutoRials in Optimization, Search and decision support methodologies (INTROS) Tuesday 12th August 2003, Royal Moat House Hotel, Nottingham, UK CALL FOR PARTICIPATION Sponsored by: o The Engineering and Physical Sciences Research Council (EPSRC) o The London Mathematical Society (LMS) o Kluwer Academic Publishers o The University of Nottingham The INTROS Workshop will offer the opportunity to engage with some of the leading researchers in the world in optimization, search and decision support technology. The programme lies at the interface between Artificial Intelligence and Operational Research. The workshop is aimed at anyone who wants to learn about some of the most important search methodologies that are currently at the forefront of international research efforts. We expect each tutorial to last one and a half hours. The programme is: 8.30-9.00: Registration 9.00-9.15: Welcome 9.15-10.45: David Goldberg*: Genetic Algorithms (Room 1) Michael Trick* and Bob Bosch%: Integer Programming (Room 2) 10-45-11.15: Coffee 11.15-12.45: Riccardo Poli* & John Koza%: Genetic Programming (Room 1) Roman Slowinski*: Rough Set Based Decision Making (Room 2) 12.45-2.00: Lunch 2.00-3.30: Dipankar Dasgupta*: Artificial Immune Systems (Room 1) Michel Gendreau*: Tabu Search (Room 2) Mark Wallace* & Eugene Freuder%:Constraint Based Reasoning (Room 3) 3.30-3.45: Tea 3.45-5.15: Kalyanmoy Deb*: Multi-objective Optimization (Room 1) Pierre Hansen* & Nenad Mladenovic%: Variable Neighborhood Search (Room 2) 5.15-5.30: Break 5.30-7.00: Xin Yao*: Machine Learning (Room 1) Darrell Whitley* & Jean-Paul Watson%: Complexity Theory and The No Free Lunch Theorem (Room 2) Key: * = Tutorial Presenter % = Co-author for an associated book chapter that will be published in a book by Kluwer that will be based around the workshop. The tutorials are specifically aimed at: o Academic Researchers o PhD students o Industrial Practitioners o Consultants/Software Engineers The workshop will be particularly appropriate for those who require a "refresher" course in modern Artificial Intelligence, Operational Research and Optimisation/Search/Decision Support methods. Workshop places are limited, so early booking is essential. Registration will be open from 12th April. See http://www.mistaconference.org/intros03/registration.html It is possible to make an expression of interest (no obligation) on that web page which will reserve a place until two weeks after registration opens. There are some PhD student bursaries available to provide free registration (not travel and subsistence). For details about how to apply for these see http://www.mistaconference.org/intros03/bursaries.html For further details about attendance and registration see http://www.mistaconference.org/intros03/ or contact Dr Graham Kendall at the University of Nottingham (gxk@cs.nott.ac.uk). The INTROS'03 workshop is being held the day before the MISTA conference. For details about MISTA see http://www.mistaconference.org 5. The 1st MISTA Conference =========================== The 1st Multidisciplinary International Conference on Scheduling: Theory and Applications (MISTA) Wednesday 13th to Saturday 16th August 2003, hosted by The University of Nottingham, UK. This conference is the first in a series of conferences that serve as a forum for an international community of researchers, practitioners and vendors on all aspects of multi-disciplinary scheduling. The conference will cover, but not be limited to, the following disciplines: Artificial Intelligence, Computer Science, Engineering, Management, Manufacturing, Mathematics and Operational Research. The aim is to bring together scheduling researchers and practitioners from all the disciplines that engage with scheduling research. Conference Web Page ------------------- For latest/more information see: http://www.mistaconference.org This page includes the registration details Being held in conjunction with ------------------------------ INtroductory TutoRials in Optimization, Search and decision support methodologies (INTROS'03) Tuesday 12th August 2003, Nottingham, UK See : http://www.mistaconference.org/intros03 for more details Plenary Speakers ---------------- Michael Pinedo, Stern School of Business, New York University Title : ORDER SCHEDULING MODELS WITH APPLICATIONS IN PRACTICE Abstract : Order scheduling models can be described as follows. A machine environment (e.g., a number of non-identical machines in parallel) can produce a fixed variety of different products. Any one machine can process a given set of different product types. If it can process only one type of product it is referred to as a dedicated machine, otherwise it is referred to as a flexible machine. A flexible machine may be subject to a setup when it switches from one product type to another product type. Each product type has certain specific processing requirements on the various machines. There are n customers, each one sending in one order. An order requests specific quantities of the various different products; it has a release date as well as a due date (committed shipping date). When the processing of all the different products. for an order have been completed, the order can be shipped. We first introduce a notation for this class of models. We then focus on various different machine environments and several objective functions, including the total weighted completion time, the maximum lateness, the number of orders shipped late, and so on. We present polynomial time algorithms for some models, complexity proofs for problems that are NP-Hard, as well as heuristics with their worst case performance and empirical analyses. We conclude with a number of practical applications of these models. Stephen Smith Title/Abstract : Not Yet Available Gerhard Woeginger Title/Abstract : Not Yet Available Conference Scope (but not limited it) ------------------------------------- * Commercial Packages * Automated Reasoning * Timetabling * Constraint Logic Programming * Evolutionary Algorithms * Rostering * Knowledge-Based Systems * Heuristic Search * Real-Time Scheduling * Local Search * Shop-Floor Scheduling * Multi-processor Scheduling * Transport Scheduling * Process Scheduling * Complexity of Scheduling Problems * Rule-Based Expert Systems * Real World Scheduling * Sports Scheduling * Production Scheduling * Vehicle Routing * Machine Scheduling * Meta-heuristic Search * Batch Scheduling * Theoretical Scheduling * Applications * Delivery Scheduling International Advisory Committee -------------------------------- * Graham Kendall (Chair), The University of Nottingham, UK * Abdelhakim Artiba, Facultes Universitares Catholiques de Mons (CREGI - FUCAM), Belguim * Jacek Blazewicz, Institute of Computing Science, Poznan University of Technology, Poland * Peter Brucker, University of Osnabrueck, Germany * Edmund Burke, The University of Nottingham, UK * Xiaoqiang Cai, The Chinese University of Hong Kong, Hong Kong * Ed Coffman, Columbia University, USA * Moshe Dror, The University of Arizona, USA * David Fogel, Natural Selection Inc., USA * Fred Glover, Leeds School of Business, University of Colorado, USA * Bernard Grabot, Laboratoire Gnie de Production - Equipe Production Automatise, France * Claude Le Pape, ILOG, France * Toshihide Ibaraki, Kyoto University, Japan * Mike Pinedo, New York University, USA * Ibrahim Osman, American University of Beirut, Lebanon * Jean-Yves Potvin, Universit de Montreal, Canada * Michael Trick,Graduate School of Industrial Administration, Carnegie Mellon University, USA * Stephen Smith, Carnegie Mellon University, USA * Steef van de Velde, Erasmus University, Netherlands * George White, University of Ottawa, Canada Program Committee ----------------- * Graham Kendall (co-chair), The University of Nottingham, UK * Edmund Burke (co-chair), The University of Nottingham, UK * Sanja Petrovic (co-chair), The University of Nottingham, UK * Uwe Aickelin, The University of Bradford, UK * Hesham Alfares, King Fahd University of Petroleum & Minerals, Saudi Arabia * Abdelhakim Artiba, Facultes Universitares Catholiques de Mons (CREGI - FUCAM), Belguim * Belarmino Adenso-Diaz, University of Oviedo, Spain * Philippe Baptise, IBM T. J. Watson Research Center, USA * James Bean, Department of Industrial and Operations Engineering, University of Michigan, USA * Jacek Blazewicz, Institute of Computing Science, Poznan University of Technology, Poland * Joachim Breit, Saarland University, Germany * Peter Brucker, University of Osnabrueck, Germany * Xiaoqiang Cai, The Chinese University of Hong Kong, Hong Kong * Jacques Carlier, Compigne cedex France * Edwin Cheng, The Hong Kong Polytechnic University, Hong Kong * Philippe Chretienne, Paris 6 University, France * Ed Coffman, Columbia University, USA * Peter Cowling, The University of Bradford, UK * Patrick De Causmaecker, KaHo St.-Lieven, Ghent, Belgium * Mauro Dell'Amico, University of Modena and Reggio Emilia, Italy * Erik Demeulemeester, Katholieke Universiteit Leuven, Belgium * Kath Dowsland, Gower Optimal Algorithms Ltd., UK * Andreas Drexl, University of Kiel, Germany * Moshe Dror, University of Arizona, USA * Maciej Drozdowski, Poznan University of Technology, Poland * Janet Efstathiou, University of Oxford, UK * Wilhelm Erben, FH Konstanz - University of Applied Sciences, Germany * Dror Feitelson, The Hebrew University, Israel * Gerd Finke, Laboratory LEIBNIZ-IMAG, Grenoble, France * Peter Fleming, University of Sheffield, UK * David Fogel, Natural Selection, USA * Dalibor Froncek, University of Minnesota, USA * Michel Gendreau, Universit de Montral, Canada * Celia A. Glass, Department of Actuarial Sciences and Statistics, City University, UK * Fred Glover, Leeds School of Business, University of Colorado, USA * Bernard Grabot, Laboratoire Gnie de Production - Equipe Production Automatise, France * Alain Guinet, Industrial Engineering Department, INSA de Lyon, France * Jin-Kao Hao, University of Angers, France * Martin Henz, National University of Singapore, Singapore * Jeffrey Herrmann, University of Maryland, USA * Willy Herroelen, Department of Applied Economics, Katholieke Universiteit Leuven, Belgium * Han Hoogeveen, Utrecht University, The Netherlands * Toshihide Ibaraki, Kyoto University, Japan * Jeffrey Kingston, University of Sydney, Australia * Hiroshi Kise, Kyoto Institute of Technology, Japan * Wieslaw Kubiak, MUN, Canada * Raymond Kwan, University of Leeds, UK * Claude Le Pape, ILOG, France * Chung-Yee Lee, The Hong Kong University of Science and Technology, Hong Kong * Arne Lkketangen, Dept. of Informatics, Molde College, Norway * Dirk C. Mattfeld, University of Bremen, Germany * David Montana, BBN Technologies, USA * Martin Middendorf, University of Leipzig, Germany * Alix Munier, LIP6, university Paris 12, France * Alexander Nareyek, Carnegie Mellon University, USA * Klaus Neumann, University of Karlsruhe, Germany * Bryan A. Norman, University of Pittsburgh, USA * Wim Nuijten, ILOG, France * Ibrahim Osman, American University of Beirut, Lebanon * Costas P.Pappis, University of Piraeus, Greece * Erwin Pesch, University of Siegen, Germany * Dobrila Petrovic, Coventry University, UK * Michael Pinedo, New York University, USA * Chris Potts, University of Southampton, UK * Christian Prins, University of Technology, Troyes, France * Jean-Yves Potvin, Universit de Montreal, Canada * Kirk Pruhs, University of Pittsburgh, USA * Vic J. Rayward-Smith, University of East Anglia, UK * Colin Reeves, Coventry University, UK * Celso C. Ribeiro, Catholic University of Rio de Janeiro, Brazil * Andrea Schaerf, University of Udine, Italy * Guenter Schmidt, Saarland University, Germany * Roman Slowinski, Poznan University of Technology, Poland * Stephen Smith, Carnegie Mellon University, USA * Vincent T'Kindt, University of Tours, France * Roberto Tadei, Politecnico di Torino, Italy * Jonathan Thompson, Cardiff University, UK * Michael Trick, Graduate School of Industrial Administration, Carnegie Mellon University, USA * Edward Tsang, University of Essex, UK * Denis Trystram, ID - IMAG, France * Steef van de Velde, Erasmus University, Netherlands * Greet Vanden Berghe, KaHo St.-Lieven, Ghent, Belgium * Stefan Voss, University of Hamburg, Germany * Jan Weglarz, Poznan University of Technology, Poland * Dominique de Werra, IMA, Facult des Sciences de Base, Lausanne, Switzerland * George White, University of Ottawa, Canada * Darrell Whitley, Colorado State University, USA * Gerhard J Woeginger, Faculty of Mathematical Sciences, University of Twente, The Netherlands * Yakov Zinder, University of Technology, Sydney, Australia * Qingfu Zhang, University of Essex, UK 6. Selected Papers from PATAT-2002 ================================== The Selected Papers from 4th International Conference on the Practice and Theory of Automated Timetabling is to be published in summer 2003 by Springer as part of the Lecture Notes in Computer Science series. For more information see the Springer website: http://www.springer.de 7. Special Issue of the Journal of Scheduling ============================================= Special Issue of Journal of Scheduling on "Expert Systems and Machine Learning in Scheduling" Guest Editor: Sanja Petrovic A special issue of the Journal of Scheduling will be devoted to expert systems and machine learning technology across a variety of scheduling and scheduling-related problems and domains. The deadline for submission to this special issue has passed. The issue will be published in 2004. 8. EJOR Special Issue on Timetabling ==================================== The EJOR Special Issue on Timetabling will appear in 2003. For more information see: http://www.elsevier.com/inca/publications/store/5/0/5/5/4/3/index.htt 9. EvoNet Summer School in Evolutionary Computation =================================================== EVONET'S SUMMER SCHOOL IN EVOLUTIONARY COMPUTING Host Institution: University of Parma, Italy (24 - 31 August 2003) The 6th EvoNet Summer School is for everyone who wants to learn about evolutionary computing and how to apply it in real world problems. Organised by the EvoNet Network of Excellence and the University of Parma, it is especially aimed at PhD students, postdocs, researchers and practitioners, and repeats a winning formula of presenting challenging problems with appropriate tools and tutorials to solve them in practical sessions. The focus is on teamwork, collaboration and pooling resources with numbers limited to maximise learning and student interaction. Highlights include: * A selection of challenging real-life problems and easy-to-use tools * Problem solving in small teams * Introductory lectures for first-time users and advanced tutorials for more experienced researchers * Practical, hand-on sessions to maximise learning * Skill tutorials on conducting good research, writing papers and giving presentations * Guidance from leading researchers in European evolutionary computing Problems areas will include: * Exploring mechanisms to deal with problems embedded in dynamic environments * Evolution and analysis of neural robot controllers * Automatic Concept Evolution * N-Player Iterated Prisoner's Dilemma Games Fast Advanced Unconventional Genetic Programming * A 2D cutting problem from glass industry Senior Researchers will include: * Ernesto Costa, University of Coimbra * Terry Fogarty, South Bank University * Riccardo Poli, University of Essex * Gnther Raidl, Vienna University of Technology * Xin Yao, University of Birmingham * Tom Ziemke, University of Skvde The EvoNet Summer School will be held in the historic town of Parma with its rich cultural and gastronomic traditions. The local organiser is Stefano Cagnoni, Department of Computer Engineering, University of Parma. For more information and registration details, please visit the following website: http://www.evonet.info/summerschool2003/ If there are any queries, please email: EvoNet Events Administrator: evo-admin@napier.ac.uk ------------------------------------------------------------- Michelle Hammond EvoNet Marketing and Information Manager CISM, South Bank University 103 Borough Road, London SE1 0AA, UK tel. +44 (0) 207 815 7477 : fax. +44 (0) 207 815 5893 http://evonet.dcs.napier.ac.uk/ michelle.hammond@sbu.ac.uk 10. EPSRC ISN Workshop on Applications of Constraint Programming in Scheduling =================================================== EPSRC Interdisciplinary Scheduling Network http://www.asap.cs.nott.ac.uk/iol/is-network/ Workshop on Applications of Constraint Programming in Scheduling ==================================================== Tuesday September 9th - Wednesday September 10th 2003 University of Huddersfield Constraint Programming is a problem-solving approach that has successfully been used to solve scheduling problems. Problems are defined in terms of constraints, that describe the relationships between the problem unknowns. A key feature of constraint programming is constraint propagation: the constraints are used to derive new information on the consequences of decisions made during problem-solving. On top of this basic framework, a variety of algorithms and heuristics can be built. The workshop will discuss the specific application of these ideas in scheduling. There will be two keynote speakers at the workshop: Wim Nuijten is Senior Director, Optimization Technology, for ILOG. ILOG supply optimization software, including Solver (for constraint-based optimization) and Scheduler (a supplement to Solver for scheduling resources and tasks). Wim is a co-author, with Philippe Baptiste and Claude Le Pape, of "Constraint Based Scheduling" published by Kluwer in 2001. Mark Wallace is Deputy Director of IC-PARC, the Centre for Planning and Resource Control at Imperial College London. He leads the development of the ECLiPSe constraint programming environment at IC-PARC and was involved in its beginnings at the European Computer-Industry Research Centre (ECRC) in Munich in the early 1990s. His main interests are in hybrid algorithms, combining mathematical programming and constraint programming. In addition, an introductory talk at the Workshop will illustrate the principles of constraint programming, by presenting a specific problem and different ways of solving it. Other speakers wishing to give talks at the workshop should send abstracts (by email) to the organizer, Barbara Smith, by 23rd June. Accepted speakers will be notified by 4th July. Speakers wishing to provide a longer paper for the workshop notes should do so by 11th August. The workshop will run from lunchtime on Tuesday to lunchtime on Wednesday. It is expected that the cost of attending the workshop will be around 50 pounds, including both lunches. A limited number of free places will be available for PhD students (details later). Enquiries and abstracts to: Professor Barbara Smith School of Computing and Engineering University of Huddersfield Queensgate Huddersfield HD1 3DH email: b.m.smith@hud.ac.uk 11. Items Wanted =============== In order to make WATT Digest as interesting as possible, I would like to include as much as I can in each issue. Please let me have anything that you think may be of interest to the timetabling community. Just to give you some ideas, how about sending me -Titles and abstracts of good, recent papers you have come across -Upcoming conferences -Reviews of papers -Details about software packages -Recently published thesis Timetabling problems that you are working on (and maybe could use some help with) -Questions that you would like to ask the community 12. Timetabling Bibliography =========================== The WATT pages contain a comprehensive bibliography up to 1995 (see http://www.asap.cs.nott.ac.uk/watt/resources/bibliography.html) We are currently working on updating this resource to include ALL timetabling papers from the 1995 to date. We would like you to tell us about ANY timetabling papers you know from 1995. However please note that we are If you know of any timetabling papers please EMAIL them to Limin Han (lxh@cs.nott.ac.uk) at The University of Nottingham, UK 13. Problem Datasets ==================== The WATT pages contain a small number of problem datasets (see http://www.asap.cs.nott.ac.uk/watt/resources/downloads.html) Set of 200 random examples for shift scheduling problem are availiable from http://www.dbai.tuwien.ac.at/proj/Rota/benchmarke.htm We would like to extend these datasets and we invite you to submit any datasets you have available so they can be listed on the WATT pages. We are particularly interested in datasets relating to course timetabling, examination timetabling, school timetabling and personnel timetabling. If you have any solution results we would also like to put these on WATT so that future researchers have something to compare against. Also, if you know of the references where the datasets are used, that would also be useful. Please EMAIL any information to Limin Han (lxh@cs.nott.ac.uk) at The University of Nottingham, UK 14. Timetabling Resources ========================= The WATT page at http://www.asap.cs.nott.ac.uk/watt/resources/resources.html contains a list of useful resources to timetabling researchers. Please take a few minutes to look at it and see if there is anything missing. If you would like a link added to the page, please EMAIL Dario Landa (jds@cs.nott.ac.uk) at The University of Nottingham 15. Conferences of Interest to the Timetabling Community ==================================================== Conferences of interest to timetablers can be found at the Conference Diary web site for the Journal of Scheduling. The URL is http://www.interscience.wiley.com/jpages/1094-6136/sites.html -- Gareth R. Beddoe Automated Scheduling Optimisation and Planning Research Group School of Computer Science and Information Technology, Jubilee Campus, University of Nottingham Nottingham, NG8 1BB United Kingdom http://www.cs.nott.ac.uk/~grb Ph. 0115 8466525 Mob. 07961 157976 _______________________________________________ watt mailing list watt@cs.nott.ac.uk http://www.cs.nott.ac.uk/mailman/listinfo/watt