Scheduling and Resource Allocation

Module aims

Real-life problems arising in computer science, computational management and economics often involve deciding the best way to use a given set of resources (e.g., servers, networks, routes) to complete a desired set of tasks within constraints (e.g., costs, deadline). Examples include job scheduling, workflow allocation, traffic routing, business processes optimization. The module blends methods from optimization, scheduling, and game theory to teach the best decision algorithms for such problems. Emphasis will be given to understand the trade-offs between cooperative and competitive approaches, both in centralized and decentralized decision making.

Learning outcomes

Upon successful completion of this module you will be able to:

(1) Specify algorithms to optimally allocate a finite set of resources to process a workload;

(2)  Consider useful metrics to quantify performance and costs of an allocation policy;

(3) Generate optimal decisions with the amount of information available, coping with uncertainties;

(4) Identify presence of selfish decision makers in real-world problems;

(5) Evaluate the performance degradation arising from selfish decision making;

(6) Illustrate applications of the theory to relevant scenarios, e.g., workflow management and internet traffic routing.

Module syllabus

(1) Theory of scheduling; (2) Workflow analysis; (3) Jobs with uncertain execution times; (4) Forecasting and arrival processes; (5) Introduction to competitive decision making (game theory); (6) Selfish resource allocation and the price of anarchy; (7) Online decision making and regret minimization; (8) Case studies: routing over the internet.

Teaching methods

The module will alternate traditional lectures and group tutorials, the latter to consolidate the material taught in class. Tutorial sheets will be regularly released and used to support the learning process and reinforce the understanding of the key concepts taught in class. Exercises will include samples of exam-type problems to prepare students for the final exam. An online discussion forum and Panopto will be used to support the offline teaching experience.

Assessments

There will normally be a group coursework to evaluate in an applied context the notions learned throughout the course. The coursework component accounts for 20% of the final grade. The remaining 80% will be for the written exam.

Individual coursework feedback will be given to the students to strenghen the preparation of the exam and the recognition of pitfalls during the learning process.

Reading list

Module leaders

Dr Dario Paccagnan
Dr Giuliano Casale