Scheduling and Resource Allocation
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.
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.
(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.
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.
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.
Module leadersDr Dario Paccagnan
Dr Giuliano Casale
To be advised - module reading list in Leganto