A Knowledge Management Framework That Supports Evolution of Configurable Products

Thorsten Krebs

Kurzübersicht

-
ISBN: 978-3-941216-00-6
Veröffentlicht: August 2009, Band 1 der Schriftenreihe Computer Science. Auflage, Einband: Broschur, Seiten 268, Format DIN B5, Gewicht 0.58 kg
Lieferzeit: 2 - 6 Werktage
Verfügbarkeit: Auf Lager
42,50 €

A Knowledge Management Framework That Supports Evolution of Configurable Products

Mehr Ansichten

Details

Produkthersteller haben häufig das Problem, eine Auswahl an Produkten auf dem Markt anzubieten, die sich kontinuierlich weiter entwickeln. Zur Realisierung einer solchen Auswahl werden am Markt konfigurierbare Produkte angeboten. Ähnliche, aber unterschiedliche, Produkte - eine Produktfamilie - werden aus vordefinierten Komponenten zusammengestellt: konfiguriert.

Konfiguration alleine ist jedoch nicht ausreichend in einer sich stetig verändernden Produktwelt! Produktmodelle werden obsolet wenn sich die Domäne verändert und müssen angepasst werden. Diese Dissertation beschreibt ein Framework zur Verwaltung des Produktwissens; mit expliziter Unterstützung von sich weiterentwickelnden Produkten, sogenannter Evolution von Produkten. Das Framework enthält eine durchdachte Repräsentation allen relevanten Wissens, inclusive den Komponenten, aus denen Produkte zusammengestellt werden können, den Produkten selbst und eine Methode, dieses Wissen auch bei Veränderung konsistent zu verwalten.

Abstract

Modern product manufacturers face the problem of managing a variety of products that change over time. To realize such a variety, configurable products are offered to the market. Similar but different products – a product family – are configured from a common set of pre-defined components.
But configuration alone is not sufficient when applied to an evolving product domain! Configuration models become obsolete when the product domain changes and need to be adjusted accordingly over time. This dissertation presents a knowledge management framework that explicitly supports configurable products changing over time: their evolution. The framework consists of a sophisticated representation of all relevant knowledge, including components from which product can be configured, the products themselves and a method to ensure consistency of the knowledge despite its evolution.

Summary

This dissertation has tackled the problem of managing a variety of products that change over time. Such a variety of products is typically required for being able to control a speci?c market segment. Technical advancements, new designs, increasing customer demands, etc. drive the need to continually evolve the variety of products. In order to realize such a variety, a set of con?gurable products o?er alternative and optional choices from which a customer can choose. To avoid time-consuming redesign and manual adaption, such complex products are assembled from a given set of smaller components. Con?guration tools are widely used to reach this goal.
Con?guration is a well-known approach to support the composition of products from a given set of components. Structure-based con?guration, in particular, employs hierarchical specialization and composition structures in a con?guration model. Within a con?guration model, all potentially con?gurable products of a domain are implicitly represented by de?ning the components from which a product can be composed, component attributes and relations between the components. Similar products are con?gured from a common set of components while diversity is realized with di?erent compositions, with respect to technical possibilities and given customer requirements. Structure-based con?guration models are especially well-suited to represent products that are assembled from a given set of smaller components.
We call the continuous change of stored knowledge representing con?gurable products and the components from which products can be assembled evolution of con?gurable products. This dissertation has developed a knowledge management framework that supports the evolution of con?gurable products, enabling developers to concentrate on the product domain rather than on details of the underlying knowledge representation formalism. The developed framework includes representation and change management for all required con?guration knowledge, i.e. both the components from which products can be assembled and the con?gurable products themselves, evaluation of impacts that changing the component base has on con?gurable products, and vice versa, evaluation of impacts that changing con?gurable products has on the component base.
The knowledge management framework de?nes an intuitive and productmodeling centered set of modeling facilities. The modeling facilities concept, attribute, composition relation and constraint are mapped to corresponding elements of the knowledge representation language SWRL-ALCQI+(D), which is a hybrid formalism integrating rules and Description Logics. The mapping provides a formal foundation for product modeling. The three change types addition, modi?cation and removal together with the modeling facilities provide the set of elementary changes. For every elementary change, a base operation de?nes its formal semantics with preconditions and postconditions. The preconditions for a change operation encode what the model must be like in order for the change to be executable. The postconditions describe the immediate consequences resulting from the change. More complex changes can be de?ned through compound operations, forming a logical unity that is compiled from a set of base operations. While database systems typically decline changes that cause inconsistency, we rather allow the change and suggest suitable repair options. For every type of inconsistency there is a set of potential repair operations from which the developer can choose, leading to a “click-and-repair” process.
The e?ectiveness of a con?guration application heavily depends on the quality of the underlying knowledge, that is the con?guration model. The term consistency and related terms are de?ned with respect to con?guration models, together with basic inference services of Description Logics, such as satis?ability, subsumption, equivalence, disjointness and classi?cation. Two more advanced inference services are developed especially for this dissertation: the invariantbased consistency checking and the optimized constraint satisfaction:
Invariant-based consistency checking consists of a set of invariants and a process to check consistency of a con?guration model. The invariants de?ne consistency of a con?guration model. Invariants are formulae that have a particular status: they must be guaranteed to hold at every quiescent state of the model, that is, before and after a change is executed. Checking an invariant has one of two possible outcomes: it is satis?ed or it is violated. A satis?ed invariant denotes consistency with respect to this invariant while an violated invariant denotes inconsistency. A distinction between base invariants and extension invariants enables managing con?guration models that are based on di?erent language speci?cations. While the base invariants de?ne a common basis of all language speci?cations, di?erent combinations of extension invariants allow to check consistency of con?guration models that rely on di?erent, probably domain-speci?c or con?guration-tool speci?c language speci?cations.
Optimized constraint satisfaction consists of a standard process for solving constraints and a set of optimizations that can be exploited for the conceptual representation of typical product domains. The optimizations are node consistency as preprocessor, which evaluates unary constraints ?rst in order to eliminate local inconsistencies, reducing the search space, which propagates property values from leaf concepts to their parents in order to prune unnecessary values and to reduce the search space for constraint satisfaction, evaluating constraints on the conceptual level, which evaluates the constraints for instances of those concepts for which they are de?nes, not for every potential combination of instances of leaf concepts, and independent constraint subnets, which evaluates constraints only when they belong to an a?ected constraint subnets, not constraints that belong to other, independent constraint subnets.
Knowledge management supporting the evolution of con?gurable products addresses managing both the representation of components from which products can be assembled and the representation of the con?gurable products. Both components and con?gurable products have their own evolution spaces. Hence, the following three scenarios emerge. All potential situations emerging because of managing changes to the stored knowledge are grouped into typical use cases in which a product manufacturer may be interested.

1. Managing the component base re?ects changing the set of components from which products can actually be assembled while preserving consistency of the component model. Changing a component base does not only a?ect its own consistency but implicitly also a?ects the set of potentially con?gurable products. The following four use cases can be distinguished:
*    De?ning a component.
*    Retiring a component.
*    Changing a component.
*    Managing constraints.

The use cases expose the need to evaluate the following technical questions:
*    Which con?gurable products are a?ected by a change?
*    Which new components become available?
*    Which components are no longer available?
*    Can a con?gurable product still be con?gured?

2. Managing con?gurable products addresses de?ning a variety of products that best suit the customer’s interests and reacting to in?uences of the market. Changing con?gurable products also concerns ensuring that the products remain con?gurable. A product is con?gurable if, and only if, its representation is consistent and covered by the component base. This means that all components from which a con?gurable product can be assembled need to refer to existing components of the component base. The following three use cases can be distinguished:
*    De?ning a con?gurable product.
*    Retiring a con?gurable product.
*    Changing a con?gurable product.

The use cases expose the need to evaluate the following technical questions:
*    Which new components are required to realize a con?gurable product?
*    Which components are not required for any con?gurable product?

3. But also without explicitly taking evolution into account, there is some interaction between managing the component base and managing con?gurable products. The following four use cases can be distinguished:
*    Creating a component model from a set of con?gurable products.
*    Identifying required components.
*    Checking satis?ability of components.
*    In?uencing the evolution of con?gurable products.

The use cases expose the need to evaluate the following technical questions:
*    Which components are required for a con?gurable product?
*    Which components and constraints are related to a con?gurable product?
*    Which attribute values are consistent?
*    Which property values are common for a set of con?gurable products?

This dissertation describes all use cases on a high level with examples while re-occurring reasoning services are de?ned in technical questions with formally de?ned algorithms, examples and an analysis of their computational complexity. All algorithms have exponential or better worst-case computational complexity, except for those use cases that include constraint satisfaction. Constraint satisfaction problems are known to be NP-complete. But the optimized constraint satisfaction focuses on aspects that – in most cases – considerably reduce computational complexity.
Major Contributions Summing up, the major contributions of this dissertation are the following.
*    Formal representation and reasoning support for all product-con?guration related knowledge.

–     The dissertation introduces a semantic distinction between concepts that represent components (in a component model) and concepts that represent con?gurable products (in product models). This distinction stems from the di?erent purposes of the representation. While basic de?nitions like satis?ability, subsumption or equivalence are the same for both kinds of representation, a con?gurable product needs to be covered by the component base.

–     Advanced reasoning services: besides the standard Description Logics inferences, this dissertation de?nes invariant-based consistency checking and optimized constraint satisfaction reasoning services.
*    Both services are designed to especially exploit the peculiarities of representations of typical product domains.
*    Notably, invariant-based consistency checking enables a domainindependent and con?guration-tool independent way to check consistency of con?guration models.

*    The knowledge management framework introduces consistency-preserving change management that covers all possible situations, including:


–     Support for all potential changes to stored knowledge that is based on the de?ned knowledge representation language.

–     Evaluation of impacts that executing all potential changes to stored knowledge have:
Evaluating impacts that changes to the component base have on con?gurable products.
Evaluating impacts that changes to a con?gurable product have on the component base.

–     Analyzing impacts of separately managing a component base and managing con?gurable products.

Proof of Concept A prototype model editor has been implemented. The model editor allows creating and managing con?guration models and evaluates impacts that changes to the component base have on con?gurable products. Conducted experiments demonstrate feasibility of the conceptual idea and show its scalability: executing change operations to a component model and evaluating impacts on con?gurable products are suitably e?cient and practical also when applied to large con?guration models. Additionally, the improvement of implementing the optimized constraint satisfaction is shown, compared to a standard generate-and-test algorithm.

Contents

I Introduction 1
1 Motivation 3
1.1 Introduction . . .   3
1.2 Goals and Requirements . .  6
1.3 A Guiding Example . . 8
1.4 Typographic Conventions . .  9
1.5 Reader’s Guide . . .  9
1.6 Further Reading . . .  10
1.6.1 Product Data Management . .   10
1.6.2 Mass Customization . .  11
1.6.3 Product Lines . . 12
1.6.4 Reuse . . .  13

II State-of-the-Art 15

2 Structure-based Configuration 17
2.1 Introduction . . .   17
2.2 Knowledge Representation and Reasoning . .  18
2.2.1 A Survey . . .  18
2.2.2 Structure-based Knowledge Representation . .  20
2.2.3 Structure-based Reasoning . .   21
2.3 Classes of Configuration Problems . .   21
2.4 Further Reading . . .  24
2.4.1 Product Modeling . .  24
2.4.2 Non-routine Configuration . .    25

3 Knowledge Representation 27
3.1 Introduction . . .   27
3.2 Of Ontologies, Knowledge Bases and Configuration Models . .  29
3.3 Foundation for Configuration . . 32
3.4 Description Logics . . . 34
x Contents
3.4.1 The Knowledge Representation Language
SWRL-ALCQI+(D) . .  34
3.4.2 The ALCQI+(D) Component . .   34
3.4.3 The SWRL Component . .   36
3.5 Modeling Facilities . . . 37
3.5.1 Concepts . . .  38
3.5.2 Instances . . .  39
3.5.3 Specialization Relations . .   39
3.5.4 Attributes . . .  40
3.5.5 Composition Relations . . 41
3.5.6 Constraints . . . 42
3.6 Building a Configuration Model . .   45
3.7 Reasoning . . .  46
3.7.1 Configuration Process . . 47
3.7.2 Product Individuals . .  48

4 Evolution 49

4.1 Introduction . . .   50
4.2 Evolution of Configuration Models . .   51
4.2.1 Changes . . .  52
4.2.2 Types of Changes . .  53
4.2.3 Planning Evolution . .  55
4.3 Evolution of Products . .   55
4.3.1 Evolution of Configurable Products . .  55
4.3.2 Evolution of Product Individuals . .  56
4.4 Versioning . . .  56
4.4.1 General Introduction . .  56
4.4.2 Modeling Versions . .  57
4.4.3 Versioning of Configuration Models . .  58
4.5 Further Reading . . .  60
4.5.1 The “Classic” Categories of Evolution . .   60
4.5.2 Configuration Management . .   60
4.5.3 Belief Change . . 61
4.5.4 Database Schema Evolution . .   62

III Conceptual Idea 63

5 The Knowledge Management Framework 65
5.1 Representing Products . .   65
5.1.1 Configurable Products . . 66
5.1.2 Modeling Products . .  66
5.2 Knowledge Management . .  72
5.2.1 Managing the Component Base . .   73
5.2.2 Managing Configurable Products . .  75
Contents xi
5.2.3 Interaction Between Managing the Component Base and
Configurable Products . . 76
5.3 Preliminaries . . .  78
5.3.1 Abstract and Concrete Concepts . .  78
5.3.2 General and Product-specific Constraints . .   79
5.3.3 Mapping . . .  79
5.4 Consistency . . .   81
5.5 Basic Inferences . . .  83
5.5.1 Reasoning Tasks for Concepts . .   83
5.5.2 Reasoning Tasks for Conceptual Models . .   84
5.6 Invariant-based Consistency Checking . .   85
5.6.1 Invariants . . .  85
5.6.2 Checking Consistency . . 92
5.7 Optimized Constraint Satisfaction . .   95
5.7.1 Types of Constraints . .  95
5.7.2 Solving Constraints . .  97
5.7.3 Optimizations . . 98
5.8 Specification of Change Operations . .   100
5.8.1 Semantics of Change Operations . .  101
5.8.2 Specification of Base Operations . .  103
5.8.3 Specification of Compound Operations . .   103
5.8.4 Compiling Compound Operations . .  104

6 Managing the Component Base 111
6.1 The Change Process . . 111
6.1.1 Change Identification . . 112
6.1.2 Compilation of Change Operations . .  113
6.1.3 Execution of Change Operations . .  114
6.1.4 Impact Evaluation . .  115
6.2 The Use Cases . . .  117
6.2.1 Use Case 1: Defining Components . .  117
6.2.2 Use Case 2: Retiring Components . .  118
6.2.3 Use Case 3: Changing Components . .  119
6.2.4 Use Case 4: Managing Constraints . .  120
6.3 The Technical Questions . .  121
6.3.1 Which Configurable Products Are Affected By a Change? 121
6.3.2 Which New Components Become Available? . .  123
6.3.3 Which Components Are No Longer Available? . .   128
6.3.4 Can a Configurable Product Still Be Configured? . .  132

7 Managing Configurable Products 137

7.1 The Change Process . . 137
7.1.1 Differences Between the Processes . .  138
7.1.2 Impact Evaluation . .  139
7.2 The Use Cases . . .  141
7.2.1 Use Case 1: Defining a Configurable Product . .  141
xii Contents
7.2.2 Use Case 2: Retiring a Configurable Product . .  144
7.2.3 Use Case 3: Changing a Configurable Product . .   144
7.3 The Technical Questions . .  146
7.3.1 Which New Components Are Required to Realize a Configurable
Product? . .  146
7.3.2 Which Components Are Not Required for Any Configurable
Product? . .  150

8 Interaction Between Managing the Component Base and Managing
Configurable Products 155

8.1 The Use Cases . . .  155
8.1.1 Use Case 1: Creating a Component Model From a Set of
Configurable Products . . 156
8.1.2 Use Case 2: Identifying Required Components . .   160
8.1.3 Use Case 3: Checking Satisfiability of Components . .  161
8.1.4 Use Case 4: Influencing the Evolution of Configurable
Products . . .  163
8.2 The Technical Questions . .  165
8.2.1 Which Components Are Required for a Configurable Product?
. . .   165
8.2.2 Which Components and Constraints Are Related to a
Configurable Product? . . 166
8.2.3 Which Attribute Values Are Consistent? . .   169
8.2.4 Which Property Values Are Common for a Set of Configurable
Products? . .  171

IV Outlook 173
9 Proof of Concept 175
9.1 Existing Tools . . .  175
9.2 Prototype Implementation . .  177
9.2.1 Development Environment . .   177
9.2.2 Specifics of the Prototype . .    179
9.3 Experiments . . .   181
9.3.1 Goals . . .  182
9.3.2 Experiments Set-up . .  182
9.3.3 Test Data . . .  183
9.3.4 Results . . .  185

10 Summary 191


11 Scope of Applications 197
11.1 Product Domains . . .  197
11.1.1 Suitable Product Domains . .    197
11.1.2 Unsuitable Product Domains . .   198
Contents xiii
11.2 Limitations of the Framework . . 198

12 Future Work 201
12.1 Recommending Changes . .  201
12.2 Support for Additional Language Specifications . .   202
12.2.1 KONWERK and EngCon . .    202
12.2.2 Kumbang . . .  203
12.2.3 Web Ontology Language (OWL) . .  204
12.3 Support for Procedural Knowledge . .   205
12.4 Versioning . . .  206

A Language Specification 211

B Inconsistency and Repair 215

B.1 Invariants, Inconsistency and Repair . .   215
B.2 Repair Processes . . .  223
B.2.1 Concept-related Changes . .    224
B.2.2 Attribute-related Changes . .    225
B.2.3 Composition-related Changes . .   227
B.2.4 Constraint-related Changes . .   229
B.2.5 Conclusion . . . 231

Zusatzinformation

Gewicht 0.5800
Lieferzeit 2 - 6 Werktage

Sie könnten auch an folgenden Artikeln interessiert sein

Determination of position and three-dimensional orientation of single quantum emitters in a λ/2-microresonator

Determination of position and three-dimensional orientation of single quantum emitters in a λ/2-microresonator

38,00 €