Transcript Welcome to G53ASD AUTOMATED

Welcome to G53ASD
AUTOMATED SCHEDULING
Lecturer:
Dr. Sanja Petrovic
School of Computer Science and Information
Technology
E-mail: [email protected]
The University of Nottingham
1
Module Details
Module Code: G53ASD
Location and Time: Tuesday, 11:00, room B53
Tuesday, 12:00, room B53
Prerequisites (desirable but not essential):
Mathematics for Computer Scientists (G51MCS)
Mathematics for Computer Scientists (G51MC2)
Artificial Intelligence Methods (G51BAIM)
Assessment: One written 2 hour examination
2
Aim and Objectives
Aim:
• To provide a sound understanding of the fundamental techniques
and algorithms for scheduling problems from a range of
commercial and service sectors.
Objectives:
• To give an understanding of the methods and techniques that are
available for building scheduling systems.
• To introduce a number of scheduling applications from a variety of
industrial and service sectors and show how software packages are
designed to solve them.
3
Contents
What will be covered in this course?
•
•
Description of the module
Introduction to Scheduling and Classification of Scheduling
Problems
6.
General Purpose Procedures Applied to Scheduling
General Purpose Procedures Applied to Scheduling
Simulated Annealing
Tabu-Search
Exercise: Tabu Search, Solution
Genetic Algorithm
7.
Timetabling Problems
Graph Coloring Heuristics
3.
4.
5.
4
Contents
8.
9.
10.
University Timetabling
paper: "Recent Research Directions in Automated Timetabling",
Burke, E.K., Petrovic,S.,
accepted for publication in European Journal of Operational
Research - EJOR, 2002.
paper: "A Memetic Algorithm for University Exam Timetabling",
Burke, E.K., Newall, J.P., Weare, R.F., 1996.
In: (Eds.) Burke, E., Ross, P. The Practice and Theory of Automated
Timetabling: Selected Papers from the 1st Int'l Conf. on the Practice
and Theory of Automated Timetabling, Napier University,
August/September 1995, Springer Lecture Notes in Computer
Science Series, Vol. 1153., pp. 241-250.
Employee Timetabling
Exercise:
Solving a Nurse Rostering Problem with Enhanced Tabu Search
Lecture given by Dr. Kath Dowsland
5
Contents
11.
12.
13.
14.
15.
16.
17.
Nurse Rostering
Lecture given by Greet Vanden Berghe
Production Scheduling
Single Machine Deterministic Models
Completion Time Models
Lateness Models
Tardiness Models
Sequence Dependent Setup Models
Exercise: Single Machine Scheduling Problems, Solution
Multiple Machines Problems
Project Scheduling
Exercise: Project Scheduling, Solution
Flow Shop Scheduling
Exercise: Flow Shop, Solution
6
Contents
18.
19.
20.
21.
22.
Job Shop Scheduling
Exercise: Job Shop, Solution
New Approaches to Scheduling Problems
Fuzzy Scheduling
Design of Scheduling Systems NEW
Demonstration of LEKIN – Software System for Production Scheduling
NEW
Lecture given by Gareth Beddoe
Revision Lecture
Example of Exam Questions, Solution
7
Literature
Recommended Reading
1.
Operations Scheduling with Applications in Manufacturing
and Services,
Michael Pinedo and Xiuli Chao,
McGraw Hill, 2000.
2.
Scheduling, Theory, Algorithms, and Systems,
Michael Pinedo,
Prentice Hall, 1995.
NEW: Second Edition, 2002
8
Literature
Other Good Books
3.
Deterministic Scheduling Theory
Gary Parker,
Chapman & Hill, 1995.
4.
Scheduling Under Fuzziness
Roman Slowinski, and Miciej Hapke, (eds)
Physica-Verlag, A Springer-Verlag Company, 2000.
5.
Scheduling Algorithms
Peter Brucker,
Spring 2001.
9
Lecture Notes
• Lecture Notes will be available online on the module
website:
http://www.cs.nott.as.uk/~sxp
• All announcements for the module will be made in
lectures and put on the course website
10