Narendra Jussien

ICAPS Conference 2013 Conference Paper

An Optimal Constraint Programming Approach to the Open-Shop Problem

• Arnaud Malapert
• Hadrien Cambazard
• Christelle Guéret
• Narendra Jussien
• André Langevin
• Louis-Martin Rousseau

This is a summary of the journal article published by Journal on Computing entitled "An Optimal Constraint Programming Approach to the Open-Shop Problem. " The article presents an optimal constraint programming approach for the Open-Shop scheduling problem, which integrates recent constraint propagation and branching techniques with new upper bound heuristics. Randomized restart policies combined with nogood recording allow to search diversification and learning from restarts. This approach is compared with the best-known metaheuristics and exact algorithms, and shows better results on a wide range of benchmark instances.

AIJ Journal 2002 Journal Article

Local search with constraint propagation and conflict-based heuristics

• Narendra Jussien
• Olivier Lhomme

Search algorithms for solving csp (Constraint Satisfaction Problems) usually fall into one of two main families: local search algorithms and systematic algorithms. Both families have their advantages. Designing hybrid approaches seems promising since those advantages may be combined into a single approach. In this paper, we present a new hybrid technique. It performs a local search over partial assignments instead of complete assignments, and uses filtering techniques and conflict-based techniques to efficiently guide the search. This new technique benefits from both classical approaches: a priori pruning of the search space from filtering-based search and possible repair of early mistakes from local search. We focus on a specific version of this technique: tabu decision-repair. Experiments done on open-shop scheduling problems show that our approach competes well with the best highly specialized algorithms.

AAAI Conference 2000 Conference Paper

Local Search with Constraint Propagation and Conflict-Based Heuristics

• Narendra Jussien

In this paper, we introduce a new solving algorithm for Constraint Satisfaction Problems (CSP). It performs an overall local search helped with a domain filtering technique to prune the search space. Conflicts detected during filtering are used to guide the search. First experiments with a tabu version of the algorithm have shown good results on hard instances of open shop scheduling problems. It competes well with the best highly specialized algorithms.

ECAI Conference 1998 Conference Paper

Dynamic Domain Splitting for Numeric CSPs

• Narendra Jussien
• Olivier Lhomme