WATT Digest 2003, Issue 4 Date Issued : 1st October 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 4 : Iss 1) is due 1st January 2004. 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-04) 1. WATT EMAIL Groups 2. New WATT Members 3. 5th WATT Workshop at EURO/INFORMS 4. PATAT 2004 Call for Papers 5. 4th EPSRC ISN PhD Student Workshop on Scheduling 6. MISTA Conference Selected Papers 7. MISTA Conference Best Paper Award 8. Special Issue of Annals of Operations Research 9. International Timetabling Competition 10. Selected Papers from PATAT-2002 11. Items Wanted 12. Timetabling Bibliography 13. Problem Datasets 14. Timetabling Resources 15. 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: Block, Roger (Argentina) Santos, Haroldo Gambini (Brazil) Trianon, Andres (Malaysia) 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 was 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 were presented: --------------------------- Implementation of a University Final Examination Timetabling System Mehmet Sevkli, Arife Burcu Colak, and Mazhar Unsal The university final examination timetabling problem is investigated. Most previous investigators have resorted to heuristic methods of solving the university final examination timetabling problem because of the difficult combinatorial nature of this problem considering the voluminous amount of decision variables and constraints involved. A nonlinear integer program formulation of the problem is presented in the present study which is then transformed into a linear integer program. The resulting problem is solved using a commercial software package. Results from the present study together with the limitations of the present method are discussed by means of a practical example. --------------------------- Determining Feature Weights in a Case-Based Reasoning Approach to Nurse Rostering Gareth Beddoe and Sanja Petrovic We present a method for capturing nurse rostering experience and adapting it to solve new problems using the Case-Based Reasoning paradigm. This method allows rostering knowledge to be stored implicitly rather than by using inflexible sets of IF-THEN rules. Cases are retrieved from the case-base using characteristic feature values. The problem of automatically assigning weights to these features is investigated. These weights must represent the relevance and relative importance of the features based on a set of supplied training cases. We discuss various approaches and present an automated feature weighting algorithm tailored to the case-based rostering method. --------------------------- Building Quality Timetables with Integer Programming Sophia Daskalaki and Theodore Birbas We propose an IP formulation for certain types of timetabling problems. Students attend general education, specialized and elective courses. Forming timetables for schools with such system is difficult, because students form groups to attend some courses and then split to form different groups. When compactness in student timetables is required, the problem becomes even harder. With our model we introduce a number of 0-1 variables, very primitive in structure, thus flexible in modeling. The model obeys all hard functional constraints imposed by the educational system. In addition, quality issues are addressed to create more satisfying timetables for the users. --------------------------- Scheduling the Italian Football League: an ILP-Based Approach Federico Della Croce and Dario Oliveri We consider the problem of scheduling the Italian Football League. This problem consists in finding a round robin schedule taking into account home-away conditions, twin-schedules for teams belonging to the same home-town, specific balanced calendars constraints due to cable televisions requirements and so on. We adapt the ILP-based approach proposed by Nemhauser and Trick to schedule a College Basketball Conference that considers however only half of the teams involved here. The proposed approach allows generating within few minutes several different reasonable ideally balanced calendars minimizing the total number of home-away breaks and satisfying various other operational constraints. 4. PATAT 2004 Call for Papers ============================= The 5th international conference on the Practice And Theory of Automated Timetabling Wednesday, 18th August - Friday, 20th August 2004 Sheraton Hotel Pittsburgh USA This conference is the fifth in a series of conferences that serve as a forum for an international community of researchers, practitioners and vendors on all aspects of computer-aided timetable generation. For more information about the series of conferences see http://www.asap.cs.nott.ac.uk/patat/patat-index.shtml The themes of the conference include (but are not limited to): o Educational Timetabling o Transport Timetabling o Employee Timetabling o Sports Timetabling o Complexity Issues o Distributed Timetabling Systems o Experiences o Implementations o Commercial Packages o Interactive vs Batch Timetabling o Timetable Updating o Relationship with Other Scheduling Problems o Timetabling Research Areas, including: Constraint Based Methods Evolutionary Computation Artificial Intelligence Graph Colouring Expert Systems Heuristic Search Knowledge Based Systems Operational Research Simulated Annealing Local Search Mathematical Programming Soft Computing Tabu Search Submissions: Authors are invited to submit presentations in one of two categories: (a) Full Papers Authors should submit papers describing significant, original and unpublished work. Such papers are expected to be approximately 10-20 pages in length but this guideline is not strict. These papers will be fully refereed by the programme committee and the accepted ones will appear in a conference proceedings. As in previous years, a selection of the papers will appear in a post conference volume published in the Springer Lecture Notes in Computer Science series. The second round of refereeing for this volume will take place shortly after the conference. (b) Abstracts Abstracts of up to 1000 words in length (3-4 pages) can be submitted by those who wish to give a talk but do not want to write an academic paper. Abstracts will be fully refereed. The accepted ones will appear in the conference proceedings. The actual abstracts will not go forward to the second round of refereeing for the post-conference volume. However, authors of accepted abstracts will have the opportunity to write a paper (based on their abstract) and submit it for the selected papers volume at a later date (shortly after the conference). Submission Process: All submissions should be done through our online system available at http://mat.gsia.cmu.edu/PATAT04 (available September 1, 2003). Authors who cannot utilize the online system should contact one of the co-chairs of the Programme Committee for instructions. Deadlines: Paper/abstract submissions January 26th 2004 Notification April 30th 2004 (at the latest) Programme Committee: Edmund Burke (co-chair) University of Nottingham, UK Michael Trick (co-chair) Carnegie Mellon University, USA Jonathan Bard University of Texas, USA Viktor Bardadym Noveon Inc., Belgium Cynthia Barnhart MIT, USA Patrice Boizumault University of Caen, France Peter Brucker University of Osnabrueck, Germany Michael Carter University of Toronto, Canada David Corne University of Exeter, UK Peter Cowling University of Bradford, UK Patrick De Causmaecker KaHo St.-Lieven, Gent, Belgium Kathryn Dowsland Gower Optimal Algorithms Ltd. Andreas Drexl University of Kiel, Germany Moshe Dror University of Arizona, USA Wilhelm Erben FH Konstanz - University of Applied Sciences, Germany Jacques A. Ferland University of Montreal, Canada Martin Henz National University of Singapore, Singapore Alain Hertz Ecole Polytechnique de Montreal, Canada Jeffrey Kingston University of Sydney, Australia Raymond Kwan University of Leeds, UK Gilbert Laporte HEC Montreal, Canada Vahid Lotfi University of Michigan-Flint, USA Anuj Mehrotra University of Miami, USA Amnon Meisels Ben-Gurion University, Beer-Sheva, Israel George Nemhauser Georgia Institute of Technology, USA Thiruthlall Nepal Durban Institute of Technology, South Africa James Newall EventMap Ltd, UK Ben Paechter Napier University, Edinburgh, UK Gilles Pesant Ecole Polytechnique de Montreal, Canada Sanja Petrovic University of Nottingham, UK Andrea Schaerf Universita` di Udine, Italy Jan Schreuder University of Twente, Enschede, The Netherlands Stephen Smith Carnegie Mellon University, USA Jonathan Thompson Cardiff University, UK Paolo Toth University of Bologna, Italy Greet Vanden Berghe KaHo St.-Lieven, Belgium Stefan Voss University of Hamburg, Germany Dominique de Werra EPF-Lausanne, Switzerland George White University of Ottawa, Canada Michael Wright Lancaster University, UK Jay Yellen Rollins College, USA About the Venue: Pittsburgh has long shed its reputation as a town of soot and smog. Today, it is a vibrant city with a new wave of high-tech and service industries and architectural masterpieces. Intimate restaurants and high-energy clubs make Pittsburgh one of the "most livable" cities in the country. Pittsburgh boasts abundent shopping at great prices, world-class museums, symphony, ballet, opera, and a multitude of attractions. The conference will be held in one of Pittsburgh's most active areas. Lying just south of downtown, Station Square incorporates shopping, bars, restaurants, and clubs. Downtown is a short walk away across the river. Frequent river boats offer a unique view of Pittsburgh, and can even be used to get to Pittsburgh's sports venues. The conference hotel, the Sheraton Station Square, is at the heart of this area, and offers both affordable rates and outstanding conference facilities. Pittsurgh International Airport was ranked number one in the United State and number three in the world by Conde Nast Traveler and is a short 20 minute cab ride from Station Square. On the Saturday after the conference, we will organize outings to the beautiful Pennsylvania countryside. One group will head off to some of the best white-water rafting in the eastern seaboard. The Youghiogheny offers challenges to experienced rafters while not overwhelming the novice. A second group will head out to tour one of architect Frank Lloyd Wright's masterpieces "Fallingwater", a home through which a stream literally runs. The two groups will meet up for final conversation and dinner. You can find more information about Pittsburgh at http://www.visitpittsburgh.com/cvbonline/default.asp and more about the hotel at http://www.starwood.com/sheraton/search/hotel_detail.html?propertyID=693 For more information, contact: Prof E.K.Burke Automated Scheduling, Optimisation and Planning Research Group. School of Computer Science and Information Technology University of Nottingham University Park, Nottingham NG7 2RD United Kingdom e-mail: ekb@cs.nott.ac.uk or Prof M.Trick Graduate School of Industrial Administration Carnegie Mellon University Pittsburgh, PA 15213 USA e-mail: trick@cmu.edu PATAT 2004 WEB SITE Full updated information is always available from http://mat.gsia.cmu.edu/PATAT04 5. 4th EPSRC ISN PhD Student Workshop on Scheduling =================================================== The 4th EPSRC ISN PhD Student Workshop on Scheduling will take place this November 14th at Coventry University. Important dates are: Abstract submission deadline: October 14, 2003. Abstract acceptance announced: October 24, 2003. Date of PhD Workshop: November 14, 2003. Please see http://www.asap.cs.nott.ac.uk/iol/is-network/ for more information. We are exited to announce TWO invited speakers for this workshop. Prof. Colin Reeves, Professor of Operational Research in the School of Mathematical and Information Sciences at Coventry University will give the opening talk. The closing talk will be given by Dr. Ralf Keuthen, a research scientist at a.p.solve ltd, a recent spin-off of the British Telecom Research Laboratories BTexact. At a.p.solve he explores new scheduling technologies for mobile workforce management. Please email smg@cs.nott.ac.uk with abstract submissions or any queries relating to the workshop. -- Steven GUSTAFSON School of Computer Science & IT University of Nottingham, UK http://www.cs.nott.ac.uk/~smg 6. MISTA Conference Selected Volume =================================== The MISTA (The 1st Multidisciplinary International Conference on Scheduling : Theory and Applications) took place 13-16 Aug 2003. A programme (which includes a list of the presented papers) can be downloaded from http://www.mistaconference.org/2003/programme.pdf If you have an abstract or full paper in the MISTA conference proceedings, you are encouraged to update your work in the light of the feedback received at the conference, or new results/analysis, and submit a full paper to be considered for the selected volume. This is a post conference publication (published by Kluwer). Papers will undergo a further round of rigorous reviewing by the programme committee. There is no strict page limit. Five copies of the papers should be sent to Diana French (MISTA) School of Computer Science & IT Jubilee Campus The University of Nottingham Wollaton Road Nottingham NG8 1BB UK The papers MUST adhere to Kluwer single style book format (more details on the web site). The important dates are Deadline for submission : 30th October 2003 Reviewing Process : 1st November 2003 to 31st January 2004 Notification to Authors : As soon as possible Volume to Appear : Spring 2004 Further details can be seen at http://www.mistaconference.org 7. MISTA Conference Best Paper Award ==================================== The BEST PAPER AWARD at the recent MISTA conference was won by A Dynamic Model of Tabu Search for the Job-Shop Scheduling Problem Watson J-P., Whitley D. and Howe A.E. The authors received 250USD of books, of their choice, from Kluwer. 8. Special Volume of Annals of Operations Research ================================================== Call for Papers: Special Volume of Annals of Operations Research on "Personnel Scheduling and Planning" Guest Editors: Sanja Petrovic and Greet Vanden Berghe In recent years there has been an increased recognition of the importance and complexity of personnel scheduling and planning problems in a wide range of organisations. Papers are called for a special volume of Annals of Operations Research on "Personnel Scheduling and Planning" devoted to all aspects and research issues that arise in making decisions on size of personnel and in personnel scheduling. Both theoretical issues and application results are welcome. Topics covered by the special volume may include, but are not restricted to, the following themes: * Heuristics and meta-heuristics * Knowledge-based approaches * Constraint-based scheduling * Multiobjective scheduling * Multi-agent systems * Distributed planning and scheduling * Mathematical programming in scheduling Potential authors are invited to submit manuscripts either via e-mail or by sending 4 hard-copies to the addresses indicated below. Refereeing and the selection of papers will be carried out according to the standards of the Annals of Operations Research. All submissions should include a title page containing title, author(s) names and affiliations, contact author, regular postal addresses, and e-mail addresses. Manuscripts can be sent to either of the guest editors: Sanja Petrovic University of Nottingham School of Computer Science and IT Automated Scheduling, Optimisation and Planning Research Group Jubilee Campus, Wollaton Road Nottingham, NG8 1BB UK Email sxp@cs.nott.ac.uk or Greet Vanden Berghe KaHo Sint-Lieven Information Technology Gebr. Desmetstraat 1 9000 Gent BELGIUM Email greet.vandenberghe@kahosl.be Deadline for submissions: April 30, 2004 Detailed instructions for authors can be found on the Web page of Annals of Operations Research: http://www.kluweronline.com/issn/0254-5330 9. International Timetabling Competition ======================================== The results of the International Timetabling Competition are now available on the web page: http://www.idsia.ch/Files/ttcomp2002/ The best entries are shown there and most of the scores have been independently verified (a process that took much longer than we expected!). You can also find the descriptions of the methods employed by the competitors. We would like to offer our congratulations again to all those who produced such good results, and helped to further timetabling research. Best Regards Ben Paechter and Olivia Rossi-Doria 10. Selected Papers from PATAT-2002 ================================== The Selected Papers from 4th International Conference on the Practice and Theory of Automated Timetabling has been published by Springer as part of the Lecture Notes in Computer Science series. This volume can be purchased from the Springer website for EUR 50: http://www.springer.de/cgi/svcat/search_book.pl?isbn=3-540-40699-9 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 -- 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