Constraint satisfaction approach to product configuration with cost estimation

• Main Author: Wang, Lin
• Other Authors: Song Bin
• Format: Theses and Dissertations
• Language: English
• Published: 2013
• Subjects: DRNTU::Engineering::Computer science and engineering::Information systems::Information systems applications
• Online Access: https://hdl.handle.net/10356/54837
• Institution: Nanyang Technological University

Due to the dynamism and heterogeneity of today’s markets, mass customization has been widely applied in the manufacturing industry with the objective of satisfying individual customer needs while maintaining near mass production efficiency. Product family design is an effective approach for mass customization where problem modeling and solution are two significant concerns. As a large amount of data with diverse variety need to be represented (including production data, customer requirements and design knowledge), powerful knowledge representation models are necessary to capture the large variety and complexity of data. Given a configuration problem description and representation, efficient reasoning methods are also required for configuration solution search and optimization. Cost is a critical composition and criterion for product family design; however, the integration of cost estimation and product family design has not been successfully addressed. In this thesis, an extended Dynamic Constraint Satisfaction Problem (DCSP) based product configuration and cost estimation system is proposed to to effectively represent the large amount of data with great variety and complexity in product family design as DCSP terms (i.e., variables, domains and constraints). In the extended DCSP-based system, structural constraints are proposed to capture the inherent hierarchy among modules and components. Activation constraints are composed to represent derivation relationships among variables in the extended DCSP-based system. As both structural and activation constraints can activate variables into the DCSP according to triggering conditions (i.e., hierarchical and derivation relationships among variables), they are utilized to dynamically extend the search space of the extended DCSP-based system such that only a subset of the original variables are involved in the final solution. To integrate cost estimation with product family design tightly, cost calculation constraints are introduced into the extended DCSP-based system, by which results of product configuration and cost estimation can be obtained simultaneously. Thus, cost can be utilized as a coherent criterion for product configuration. To study the impact of changes to cost drivers and design parameters on the cost of a product, the entire product family, or even the entire product lifecycle, cost variation constraint are proposed. Mapping relationships between concepts of the extended DCSP-based system and the data traditionally stored in product data models are also analyzed to facilitate the construction of the extended DCSP-based system. Based on the extended DCSP-based product configuration and cost estimation system, an augmented backtracking algorithm is designed. In the algorithm, structural constraint handler and activation constraint handler are embedded into a classical Constraint Satisfaction Problem (CSP) solving procedure, both of which are able to trigger the extension of the extended DCSP-based system. Thus, the solving process of the extended DCSP-based system can be viewed as a sequence of stable phases, each of which is classical backtracking performed on a fixed classical CSP. To address issues of augmented backtracking (trashing and late conflict detection), a hybrid solving algorithm—forward checking and backjumping with fail-first heuristic (FC-BJ with FF)—is applied to the extended DCSP-based system to enhance solving efficiency. Furthermore, a hybrid heuristic (a combination of an amended constraint-most heuristic with fail-first heuristic) is integrated with FC-BJ to control backtracking occurrence in the implementation of the algorithm FC-BJ with FF on the extended DCSP-based system. Finally, the extended DCSP-based configuration and cost estimation system is evaluated using two configuration tasks (desktop PC configuration and cable-operated elevator configuration). Three proposed algorithms are performed on the two DCSP-based configuration tasks respectively and good solving efficiency is achieved.