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:
- Design algorithms to optimally allocate a finite set of resources to process a workload;
- Determine useful metrics to quantify performance and costs of an allocation policy;
- Adjust optimal decisions with the amount of information available, coping with uncertainties;
- Identify presence of selfish decision makers in real-wolrd problems;
- Quantify the performance degradation arisign from selfish decision making;
- Understand applications of the theory, such as workflow management and how traffic is routed over the internet.
(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 course will alternative 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. EdStem 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 feedbacks 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