Conférence de David BERGMAN : "Variable ordering for the application of BDDs to the maximum independent set problem"
Master class de Emmanuel HEBRARD, CNRS, Laas, France : "Scheduling and SAT"
"In a two-machine flow shop scheduling problem, the set of approximate sequences ( i.e. , solutions within a factor 1+ of the optimal) can be mapped to the vertices of a permutation lattice. We introduce two approaches, based on properties derived from the analysis of permutation lattices, for characterizing large sets of near-optimal solutions. In the first approach, we look for a sequence of minimum level in the lattice, since this solution is likely to cover many optimal or near-optimal solutions. In the second approach, we look for all sequences of minimal level, thus covering all approximate sequences.
Integer linear programming and constraint programming models are first proposed to solve the former problem. For the latter problem, a direct exploration of the lattice, traversing it by a simple tree search procedure, is proposed. Computational experiments are given to evaluate these methods and to illustrate the interest and the limits of such approaches."
Master class de Michele LOMBARDI, Université de Bologne, Italie : "Resource allocation and scheduling from CP/OR hybrid perspective"
"This paper proposes a global cumulative constraint for cyclic scheduling problems. In cyclic scheduling a project graph is periodically re-executed on a set of limited capacity resources. The objective is to find an assignment of start times to activities such that the feasible repetition period ? is minimized. Cyclic scheduling is an effective method to maximally exploit available resources by partially overlapping schedule repetitions. In our previous work [4], we have proposed a modular precedence constraint along with its filtering algorithm. The approach was based on the hypothesis that the end times of all activities should be assigned within the period: this allows the use of traditional resource constraints, but may introduce resource inefficiency. The adverse effects are particularly relevant for long activity durations and high resource availability. By relaxing this restriction, the problem becomes much more complicated and specific resource constrained filtering algorithms should be devised. Here, we introduce a global cumulative constraint based on modular arithmetic, that does not require the end times to be within the period. We show the advantages obtained for specific scenarios in terms of solution quality with respect to our previous approach, that was already superior with respect to state of the art techniques."