Sage Journals: Discover world-class research

Abstract

In modern manufacturing, constraint satisfaction problem based product configuration systems have been recognized as an effective and promising approach to represent and solve product family design tasks. In this article, based on an extended dynamic constraint satisfaction problem based product configuration system, a hybrid constraint satisfaction problem solving algorithm with forward checking and backjumping with fail-first heuristic is proposed. To control backtracking occurrence in this hybrid solving algorithm when new active variables are introduced into dynamic constraint satisfaction problem, a hybrid heuristic (a combination of an amended most-constrained heuristic and fail-first heuristic) is integrated with forward checking and backjumping for better solution efficiency. Experiments on both algorithms have been performed on a dynamic constraint satisfaction problem based PC configuration task.

Keywords

Forward checking backjumping fail-first heuristic amended most-constrained heuristic dynamic constraint satisfaction problem based product configuration

Get full access to this article

View all access options for this article.

References

Bacchus

Grove

(1995) On the forward checking algorithm. CP ’95 proceedings of the 1st international conference on principles and practice of constraint programming, Lecture Notes in Computer Science, vol. 976, pp. 292–309.

Barták

(1999) Constraint programming—what is behind? In: Proceedings of the workshop on constraint programming in decision and control (ed Figwer

), Gliwice, Poland, June.

Barták

(2005) Constraint propagation and backtracking-based search—a brief introduction to mainstream techniques of constraint satisfaction. Lecture Note of the first international summer school on Constraint Programming of Charles University, September 11–15, 2005, Maratea, Italy. Available at: http://kti.mff.cuni.cz/;bartak/downloads/CPschool05notes.pdf.

Chenouard

Granvilliers

Sebastian

(2009) Search heuristics for constraint-aided embodiment design. Artificial Intelligence for Engineering Design, Analysis and Manufacturing 23(2): 175–195.

Jiao

Tseng

(2001) Architecture of product family: fundamental and methodology. Concurrent Engineering: Research and Applications 9(4): 309–325.

Fujita

Yoshida

(2004) Product variety optimization: simultaneously designing module combination and module attributes. Concurrent Engineering: Research and Applications 12(2): 105–118.

Jiao

Simpson

Siddique

(2007) Product family design and platform-based product development: a state-of-the-art review. Journal of Intelligent Manufacturing 18(1): 4–29.

Mittal

Falkenhainer

(1990) Dynamic constraint satisfaction problems. In: Proceedings of the 8th national conference on artificial intelligence (AAAI-90), Boston, MA, July 29–August 3, pp. 25–32. AAAI Press.

Mittal

Frayman

(1989) Towards a generic model of configuration tasks. In: Proceedings of the 11th international joint conference of artificial intelligence, Detroit, MI, August 20–26, pp. 1395–1401. Morgan Kaufmann Publishers Inc. San Francisco, CA, USA.

10.

Razgon

(2005) Complexity analysis of heuristic CSP search algorithms. In: Joint annual workshop of ERCIM/CoLogNet on constraint solving and constraint logic programming, Uppsala, Sweden, June 20–22, pp. 88–99. Springer-Verlag Berlin Heidelberg.

11.

Simpson

D’Souza

(2001) Assessing variable levels of platform commonality within a product family using a multiobjective genetic algorithm. Concurrent Engineering: Research and Applications 12(2): 119–130.

12.

Wang

Song

(2011) Extended DCSP approach on product configuration with cost estimation. Concurrent Engineering: Research and Applications 19(2): 123–138.

13.

Chen

JLQ

Xie

(2004) Framework of a product lifecycle costing system. Journal of Computing and Information Science in Engineering 6: 69–77.

Hybrid solving algorithms for an extended dynamic constraint satisfaction problem based configuration system

Abstract

Keywords

Get full access to this article

References