Course Information Undergraduate prospectus

Models and Algorithms for Scheduling

Course summary

Course code: MATH1089
Level: 6
Credits: 15
School: Architecture, Computing and Hums
Department: Mathematical Sciences
Course Coordinator(s): Vitaly Strusevich

Specification

Pre and co requisites

Discrete Mathematics and Combinatorics, Operational Research for Industry.

Aims

To introduce the students to the variety of scheduling models that occur in manufacturing and service industries.
To help them to choose a right model for a practical problem and to select an appropriate tool, analytical or software, for finding a suitable solution.

Learning outcomes

On successful completion of this course a student will be able to:

1. Formulate practical problems that involve scheduling and sequencing in terms of standard scheduling models and their extensions;
2. Find exact and approximate solutions to scheduling problems by polynomial time algorithms;
3. Design and run branch and bound algorithms for scheduling problems;
4. Understand and be able to run various local search algorithms;
5. Use software tools to handle various scheduling models.

Indicative content

• Single-stage and multi-stage scheduling systems. Types of parallel machines. Types of multi-machine shops. Standard restrictions and objective functions. The three-field classification scheme.
• Polynomial-time algorithms for single-machine problems and parallel machine problems. Worst-case analysis.
• Flow shop, job shop and open shop problems. Exact and approximation algorithms.
• Problems with pre-emption, with precedence constrains.
• Branch and Bound algorithms
• Dispatching rules. Introduction to local search. Algorithms of iterative improvement, threshold acceptance, tabu search, simulated annealing, genetic algorithms.
• Using Microsoft Excel, Lekin and LiSA for solving the problems.

Teaching and learning activity

Concepts are introduced in the lectures and re-inforced in tutorials and by a coursework.
Students are expected to conduct a considerable amount of independent study under the lecturer guideness, including work with software tools.

Assessment

Summative assessment:
Coursework - 50%
An individual coursework assessing learning outcomes 1, 2, 3, 5

Exam - 50%
A 3-hour exam assessing learning outcomes 1-4.

Formative assessment: Regular tutorial exercises