« G12 MiniZinc version 1.5.1 released | Main | SweConsNet Workshop 2012 - including my presentation "Comparison of >= 14 CP systems - and counting" »

Manufacturing Cell Design Problem (MCDP): My first Constraint Programming related academic papers

Some days ago I was told that the journal paper I have co-authored about Manufacturing Cell Design Problem (MCDP, see below) has been accepted for publication in a journal. Also, some weeks ago a short conference paper about the same topic was accepted. My part in both papers was that I created a couple of MiniZinc models (first the standard formulation and then some other using different approaches) and running a large number of benchmarks on a couple of FlatZinc solvers. This is really fun, since these papers are my first academic papers related to Constraint Programming.

Since the papers are not yet published/presented, I cannot reveal much more than the following. After the publications, I will blog more.

The journal paper

The journal paper is

Ricardo Soto, Hakan Kjellerstrand, Orlando Durán, Broderick Crawford, Eric Monfroy, Fernando Paredes: Cell formation in group technology using constraint programming and Boolean satisfiability

Published in the journal Expert Systems with Applications (ScienceDirect page, "In Press, Corrected Proof")

Cell formation consists in organizing a plant as a set of cells, each of them containing machines that process similar types or families of parts. The idea is to minimize the part flow among cells in order to reduce costs and increase productivity. The literature presents different approaches devoted to solve this problem, which are mainly based on mathematical programming and on evolutionary computing. Mathematical programming can guarantee a global optimal solution, however at a higher computational cost than an evolutionary algorithm, which can assure a good enough optimum in a fixed amount of time. In this paper, we model and solve this problem by using state-of-the-art constraint programming (CP) techniques and Boolean satisfiability (SAT) technology. We present different experimental results that demonstrate the efficiency of the proposed optimization models. Indeed, CP and SAT implementations are able to reach the global optima in all tested instances and in competitive runtime.

Manufacturing cells; Machine grouping; Constraint programming; Boolean satisfiability

Conference paper

The short conference paper is the following (with almost the same authors as the journal paper)

Ricardo Soto, Hakan Kjellerstrand, Juan Gutiérrez, Alexis López, Broderick Crawford, and Eric Monfroy: Solving Manufacturing Cell Design Problems using Constraint Programming

for the conference IEA/AIE 2012 (International Conference on Industrial, Engineering and Other Applications. of Applied Intelligent Systems, 2012 Dalian, China )

A manufacturing cell design problem (MCDP) consists in creating an optimal production plant layout. The production plant is composed of cells which in turn are composed of machines that process part families of products. The goal is to minimize part flow among cells in order to reduce production costs and increase productivity. In this paper, we focus on modeling and solving the MCDP by using state-of-the-art constraint programming (CP) techniques. We implement different optimization models and we solve it by using two solving engines. Our preliminary results demonstrate the efficiency of the proposed implementations, indeed the global optima is reached in all instances and in competitive runtime.

More about MCDP

Manufacturing Cell Design Problem is a kind of clustering problem where the object is to cluster machines that belongs to the same part (families) as good as possible. For a little more about the problem, see the following (Powerpoint) presentation by My Mingang Fu, Lin Ben, and Kuowei Chen Manufacturing Cell Design - Problem Formulation.