Planning and Scheduling Methodologies

Code:

EIC0063

Acronym:

MPES

Keywords
Classification	Keyword
OFICIAL	Artificial Intelligence

Instance: 2012/2013 - 2S

Active?	Yes
Web Page:	http://paginas.fe.up.pt/~eol/PRODEI/mpe1213_eng.htm
E-learning page:	https://moodle.fe.up.pt/
Responsible unit:	Department of Informatics Engineering
Course/CS Responsible:	Master in Informatics and Computing Engineering

Cycles of Study/Courses

Acronym	No. of Students	Study Plan	Curricular Years	Credits UCN	Credits ECTS	Contact hours	Total Time
MIEIC	19	Syllabus since 2009/2010	4	-	6	56	162

Teaching language

Suitable for English-speaking students

Objectives

To address planning and scheduling problems in an integrated perspective.

 

To study traditional approaches to planning and scheduling problems.

 

To explore recent planning and scheduling methodologies, based on heuristic algorithms from the domain of Artificial Intelligence.

 

To apply heuristic techniques for planning and scheduling in problems of medium complexity.

Learning outcomes and competences

To get acquainted with the main approaches to solve planning and scheduling problems.

 

To know how to apply traditional planning and scheduling methods.

 

To be able to identify planning and scheduling problems that require heuristic methods (from the domain of Artificial Intelligence).

 

To know how to apply heuristic methods to planning and scheduling problems of medium complexity.

Working method

Presencial

Program

Definitions of Planning and Scheduling. Planning vs. Scheduling. Introduction to Planning and Scheduling conventional methodologies; CPM and PERT. Problems and applications.

 

Plan Automatic Generation: Means-Ends Analysis, Linear, non-linear, hierarchic and partially oriented planning. Planning and Learning: Plan generalization. Planning problems and applications.

 

Scheduling problems. Machines and jobs. Performance measures. Classification of scheduling problems. The alpha|beta|gamma notation. Machines: number, type. Job shop, flow shop and open shop. Scheduling constraints: preemption, no-wait, precedences. Objective function: makespan, lateness, tardiness. Deterministic and stochastic scheduling models.

 

Complexity of scheduling problems. Decision vs. optimization. The NP-Complete class of problems. Approximation algorithms.

 

Scheduling algorithms. Branch and bound. Dispatching rules. Local search algorithms. Hill-climbing. Simulated annealing. Tabu search. Genetic algorithms. Ant colony optimization. Constraint programming.

 

Modeling and solving of real world planning and scheduling problems.

Mandatory literature

Pinedo, Michael; Scheduling. ISBN: 0-13-706757-7
Peter Brucker; Scheduling algorithms. ISBN: 3-540-20524-1
ed. by Joseph Y-T. Leung; Handbook of scheduling. ISBN: 1-584-88-397-9

Complementary Bibliography

Barry McCollum et al.; International Timetabling Competition, 2007
ICAPS - International Conference on Automated Planning and Scheduling, 2011

Teaching methods and learning activities

Introduction to the subjects in an interactive way. Project-oriented learning. Practical assignments assisted development.

keywords

Physical sciences > Mathematics > Applied mathematics > Operations research
Physical sciences > Computer science > Cybernetics > Artificial intelligence

Evaluation Type

Distributed evaluation without final exam

Assessment Components

Description	Type	Time (hours)	Weight (%)	End date
Attendance (estimated)	Participação presencial	42,00	0,00
Assignment/Project: Interim Presentation	Defesa pública de dissertação, de relatório de projeto ou estágio, ou de tese	15,00	30,00
Assignment/Project	Trabalho laboratorial	50,00	0,00
Assignment/Project: Scientific Paper	Trabalho escrito	20,00	40,00
Assignment/Project: Final Presentation	Defesa pública de dissertação, de relatório de projeto ou estágio, ou de tese	8,00	30,00
	Total:	-	100,00

Amount of time allocated to each course unit

Description	Type	Time (hours)	End date
Study	Estudo autónomo	27
	Total:	27,00

Calculation formula of final grade

Distributed evaluation without final exam.

Assignment/Project (100%):

• Interim presentation about the topic and approach (30%)
• Final report in the form of a Scientific Paper (40%)
• Final presentation of the assignment (oral/demo) (30%)

Examinations or Special Assignments

Assignment/Project (including presentation, demo and paper). Students must arrange with teachers appropriate dates for presenting their assignments.

Special assessment (TE, DA, ...)

Assignment/Project (including presentation, demo and paper). Students must arrange with teachers appropriate dates for presenting their assignments.

Classification improvement

Assignment/Project (including presentation, demo and paper). Students must arrange with teachers appropriate dates for presenting their assignments.