JIT: Just In Time / Douki Seisan sequencing

  • A Beam Search approach for the optimization version of the Car Sequencing Problem



Joaquin Bautista1, Jordi Pereira1 and Belarmino Adenso-Díaz2.


1 UPC - Nissan Chair

2 Universidad de Oviedo


The Car Sequencing Problem (CSP) is a feasibility problem that has attracted the attention of the Constraint Programming community for a number of years now. In this paper, a new version (opt-CSP) that extends the original problem is defined, converting this into an optimization problem in which the goal is to satisfy the typical hard constraints. This paper presents a solution procedure for opt-CSP using Beam Search. Computational results are presented using public instances that verify the goodness of the procedure and demonstrate its excellent performance in obtaining feasible solutions for the majority of instances while satisfying the new constraints.

An appendix with results we found for each instance (instead of the grouped results that the paper provides) can be downloaded here

Return to previous page