Module Details
| Module Code: |
COMP9070 |
| Title: |
Planning & Scheduling
|
|
Long Title:
|
Planning & Scheduling
|
| NFQ Level: |
Expert |
| Valid From: |
Semester 1 - 2018/19 ( September 2018 ) |
| Field of Study: |
4811 - Computer Science
|
| Module Description: |
Planning and scheduling are emerging areas derived from Artificial intelligence with important applications areas ranging from process planning and space mission control to scheduling work rosters for aircraft crews. In this module, the learner will be introduced to the theory of planning and scheduling and the challenges behind co-operative approaches applied to the field. Furthermore, this module will explore current state-of-the-art techniques to solve complex planning and scheduling problems.
|
| Learning Outcomes |
| On successful completion of this module the learner will be able to: |
| # |
Learning Outcome Description |
| LO1 |
Assess the benefits and limitations of complete and incomplete heuristics to solve planning and scheduling problems. |
| LO2 |
Categorize planning and scheduling problems with respect to their computational complexity. |
| LO3 |
Design and implement a solution to a real-world planning problem. |
| LO4 |
Analyse the performance of planning and scheduling heuristics to solve real world problems. |
| LO5 |
Design and implement a planning and scheduling solution that can deal with incomplete or uncertain information and operate in dynamic environments. |
| Dependencies |
Module Recommendations
This is prior learning (or a practical skill) that is strongly recommended before enrolment in this module. You may enrol in this module if you have not acquired the recommended learning but you will have considerable difficulty in passing (i.e. achieving the learning outcomes of) the module. While the prior learning is expressed as named MTU module(s) it also allows for learning (in another module or modules) which is equivalent to the learning specified in the named module(s).
|
|
Incompatible Modules
These are modules which have learning outcomes that are too similar to the learning outcomes of this module. You may not earn additional credit for the same learning and therefore you may not enrol in this module if you have successfully completed any modules in the incompatible list.
|
| No incompatible modules listed |
Co-requisite Modules
|
| No Co-requisite modules listed |
Requirements
This is prior learning (or a practical skill) that is mandatory before enrolment in this module is allowed. You may not enrol on this module if you have not acquired the learning specified in this section.
|
| No requirements listed |
| Indicative Content |
|
Introduction
Introduction and overview of complex real-world problems that are solvable using planning and scheduling techniques. Problems such as school timetabling, staff allocation, airline scheduling etc.
|
|
Classical planning
Formalisation of planning problems and logic-based representations for discrete planning, i.e., set representation and first-order logic
|
|
Planning algorithms
Mainstream classical planning algorithms such as: Forward State-Space Search, Breadth-First Search, Uniform-Cost Search, A*. Encoding the planning problem into a set of SAT (Boolean Satisfiability) and CSP (Constraint Satisfaction Problems) problems
|
|
Scheduling problems
Classical scheduling problems such as: single and multiple machine scheduling (identical Vs. different), the job-shop problem, flow Shops, and open Shops, staff allocation, school timetabling, airline scheduling, etc
|
|
Scheduling algorithms
Exact or complete algorithms to find optimal solutions, e.g., mixed integer programming, constraint programming, and dynamic programming for scheduling; Incomplete heuristic algorithms to find near-optimal solutions, e.g., First-come first-served (FIFS), first-in first-out (FIFO), Shortest Job First (SJF), Round Robin (RR) scheduling, etc
|
|
Planning and scheduling with uncertainty
Predictive-reactive scheduling to repair solutions after an unexpected event; proactive-reactive robust planning & scheduling that incorporate a degree of disruption or unexpected events
|
|
Module Content & Assessment
|
| Assessment Breakdown | % |
|---|
| Coursework | 100.00% |
Assessments
| No End of Module Formal Examination |
| Reassessment Requirement |
Coursework Only
This module is reassessed solely on the basis of re-submitted coursework. There is no repeat written examination.
|
The University reserves the right to alter the nature and timings of assessment
Module Workload
| Workload: Full Time |
| Workload Type |
Contact Type |
Workload Description |
Frequency |
Average Weekly Learner Workload |
Hours |
| Lecture |
Contact |
Presentation of theory |
Every Week |
2.00 |
2 |
| Lab |
Contact |
Lab supporting lectures |
Every Week |
2.00 |
2 |
| Independent & Directed Learning (Non-contact) |
Non Contact |
Student undertakes independent study. The student reads recommended papers and practices implementation. |
Every Week |
3.00 |
3 |
| Total Hours |
7.00 |
| Total Weekly Learner Workload |
7.00 |
| Total Weekly Contact Hours |
4.00 |
| Workload: Part Time |
| Workload Type |
Contact Type |
Workload Description |
Frequency |
Average Weekly Learner Workload |
Hours |
| Lecture |
Contact |
Presentation of theory |
Every Week |
2.00 |
2 |
| Lab |
Contact |
Lab supporting lectures |
Every Week |
2.00 |
2 |
| Independent & Directed Learning (Non-contact) |
Non Contact |
Student undertakes independent study. The student reads recommended papers and practices implementation. |
Every Week |
3.00 |
3 |
| Total Hours |
7.00 |
| Total Weekly Learner Workload |
7.00 |
| Total Weekly Contact Hours |
4.00 |
|
Module Resources
|
| Recommended Book Resources |
|---|
-
Michael L. Pinedo. (2016), Scheduling: Theory, Algorithms, and Systems, 5. Springer, [ISBN: 3319265784].
-
Stuart Russell and Peter Norvig. (2016), Artificial Intelligence: A Modern Approach, 3. 10, 11, Prentice Hall, [ISBN: 1292153962].
| | Supplementary Book Resources |
|---|
-
Malik Ghallab, Dana Nau and Paolo Traverso. (2004), Automated Planning and Acting, Cambridge University, [ISBN: 9781107037274].
-
Jussi Rintanen/Armin Biere, Marijn Heule, Hans van Maaren, Toby Walsh. (20), Handbook of Satisfiability, 15, IOS Press, 2009, [ISBN: 978-1-58603-9].
-
Philippe Baptiste, Philippe Laborie, Claude Le Pape, Wim Nuijten/Francesca Rossi Peter van Beek Toby Walsh. (2006), Handbook of Constraint Programming, 1. 22, Elsevier Science, [ISBN: 9780444527264].
| | Supplementary Article/Paper Resources |
|---|
-
Laura Climent, Richard J. Wallace,
Miguel A. Salido, Federico Barber. (2014), Robustness and Stability in Constraint
Programming under Dynamism and
Uncertainty, Journal of Artificial Intelligence
Research, 49, p.49--7,
| | Other Resources |
|---|
-
Website, Planning & Scheduling (Charles
University),
-
Website, AI Planning, Execution, and Learning
(Carnegie Mellon University),
-
Website, Planning and Scheduling Methodologies
(University of Porto),
|
|