A. Malapert
Modélisation Avancée PPC/PL
S3 3 ECTS 24h OPT A. Malapert
Lectures
We work on the cryptator project using the choco solver.
 Getting started with the project.
 Introduction to constraint programming ;
 Research project management
 Scientific context and objectives.
 Tasks, milestones, deadlines, etc.
Schedule
Archive 20212022
Lectures
We learn basics of constraint programming using the choco solver.
 Introduction to constraint programming
 Modeling puzzle: the famous nqueens problem
 Modeling puzzle: cryptarithm
 Designing custom constraints and search for the nqueens problem
 Modeling a project scheduling problem
 Final Exam
 Modeling a university timetabling problem (project)
Resources
 The shared github repository.
 Lectures 14: Choco tutorials; my old CP course (sorry in French).
 Lectures 5: chapter 10 entitled Project Management with PERT/CPM from the book Introduction to operations Research written by Hillier and Lieberman ; see also archive 20192020.
 Lectures 6: the problem specification and stateoftheart are part of the project.
Grading
 Labs (20%): publishing corrections for two labs; github; pair work.
 Project (40%): github; team work.
 Final Exam (40%): modeling two simple problems on your computer within 3 hours; email; individual work.
Archive 20202021
Lesson 1: Project Management
We start with a a quick reminder from the graph theory course from pages 193 to 212 that will present the main algorithm used in project management : shortest path in a directed acyclic graph. Then, we will follow the chapter 10 entitled Project Management with PERT/CPM from the book Introduction to operations Research written by Hillier and Lieberman. The lab will be conducted using IBM Ilog Optimization Studio instead of an Excel worksheet.
Some additional resources are listed below :
 Project Management Tools and Techniques (PERT Project Evaluation and Review Technique; CPM Critical Path Method)
 Project Planning And Scheduling Using PERT And CPM Techniques With Linear Programming: Case Study
 Project Completion Probability after Crashing PERT/CPM Network
Guidelines and addtional questions for the PERT/CPM Lab
I suggest to use the data model given below.
// Table 10.1 (without estimated durations)
tuple Activity {
key string code;
string description;
{string} predecessors;
}
{Activity} Activities = ...;
// Figure 10.11
tuple TimeCostTradeoff {
int normalTime;
int crashTime;
int normalCost;
int crashCost;
}
// Table 10.7
TimeCostTradeoff tradeoffs[Activities] = ...;
CPM Models
 The most simple approach is to define two optimization models to apply the critical path method. The first model computes the Earliest Start Schedule while the second model computes the Latest Start Schedule for a given deadline/makespan.
 But, you will remark that these two models are very similar. In fact, it is possible to write a single model for which parameters, given as external data, define the schedule to compute (ES or LS).
 However, you still have to manually execute two run configurations to apply the CPM model. You can automate these two steps by using the IBM OPL Script language.
Approximating the Probability of Meeting the Deadline (p. 491) :
 What is the probability of finishing the project within of 44 weeks ?
 What is the probability of meeting the deadline of 47 weeks ?
 What is the probability to get the bonus by finishing the project within 40 weeks ?
Crashing
 You should start by writing a new model for crashing activities for a given makespan. If needed, the model is described in the chapter.
 Then, you can try to factorize some code with the CPM model(s) by using the
include
command.  Last, you must compute the total crash cost for every possible makespan. Again, it can be automated with the IBM OPL Script language.
Unary Resource
A unary or disjunctive resource models a set of noninterruptible activities which must not overlap in the schedule: two tasks cannot be executed simulatenously.
 All activities use the the unary resource.
 Only crashed activities use the unary resource.
Textbooks
 Scheduling Algorithms, Peter Brucker (free download).
 Scheduling  Theory, Algorithms, and Systems, Michael L. Pinedo.
 ConstraintBased Scheduling  Applying Constraint Programming to Scheduling Problems, Philippe Baptiste, Claude Le Pape, Wim Nuijten.
Archive 20192020
We will study and solve a reallife nurse rostering problem occurring at the university hospital centre Pasteur II.
Nurse rostering is a complex scheduling problem that affects hospital personnel on a daily basis all over the world ^{1}. You will be provided the following information :
 A decisionmaker who is grappling with nurse rostering problem that needs solving.
 A description of the problem context.
 A formal problem specification.
 Supporting data and past timetables.
 Light software specifications.
You will apply theoretical concepts and software development process in a real world situation. Hopefully, the problem specification remains accessible and the problem instances remain small so that it is solvable with respect to time constraints of the course.
You will be developing more skills in:
 Problem solving
 literature review
 Using analytical tools, both quantitative and qualitative
 Decision making in complex situations
 Coping with ambiguities
 Learning how to apply optimization methods in similar situations
More precisely, you will discover new techniques or strengthen your knowledge in:
 Nurse rostering problems
 Integer programming and constraint programming
 Local search and metaheuristics
 Multicriteria decisionmaking Note that there is no prerequisite and that we will choose methods and techniques according to your will and skills. We will study several articles cited in the survey ^{1}.
The teacher and all students will act as a team. We will define several work packages that will be assigned to groups of students. Your grades will depend on the realization of the work packages.

The State of the Art of Nurse Rostering, Burke, E.K., De Causmaecker, P., Berghe, G.V. et al. Journal of Scheduling (2004) 7: 441. https://doi.org/10.1023/B:JOSH.0000046076.75950.0b ↩ ↩^{2}