# 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