Modelling and algorithm for the slab designing problem based on constraint satisfaction

A constraint satisfaction model whose objective is to minimize the slab number was built for slab production in consideration of the slab designing problem with a fixed demand of order weight and a minimum limitation of order weight assigned in one slab. The problem was proved to be NP-hard by reducing a known NP-hard three-partition problem to the discussed problem in polynomial time. Concerning with special characteristics of the problem, variable selection strategies and value selection strategies were presented. A constraint-satisfaction-based algorithm was proposed and it was proved to be convergent. The effectiveness of the proposed algorithm was verified with simulation experiments.