03964.com

文档资料库 文档搜索专家

文档资料库 文档搜索专家

This article was downloaded by: [Beijing Jiaotong University] On: 06 June 2014, At: 00:52 Publisher: Taylor & Francis Informa Ltd Registered in England and Wales Registered Number: 1072954 Registered office: Mortimer House, 37-41 Mortimer Street, London W1T 3JH, UK

International Journal of Production Research

Publication details, including instructions for authors and subscription information: http://www.tandfonline.com/loi/tprs20

Domain-based production configuration with constraint satisfaction

Linda L. Zhang , Qianli Xu , Yugang Yu & Roger J. Jiao

a b c d a b c d

IESEG School of Management (LEM-CNRS), Catholic University of Lille , Lille , France Department of Computer Graphics & Interfaces , A*STAR, Singapore School of Management , University of Science and Technology of China , Hefei , China

The George W. Woodruff School of Mechanical Engineering , Georgia Institute of Technology , Atlanta , GA , USA Published online: 12 Jan 2012.

To cite this article: Linda L. Zhang , Qianli Xu , Yugang Yu & Roger J. Jiao (2012) Domain-based production configuration with constraint satisfaction, International Journal of Production Research, 50:24, 7149-7166, DOI: 10.1080/00207543.2011.640714 To link to this article: http://dx.doi.org/10.1080/00207543.2011.640714

PLEASE SCROLL DOWN FOR ARTICLE Taylor & Francis makes every effort to ensure the accuracy of all the information (the “Content”) contained in the publications on our platform. However, Taylor & Francis, our agents, and our licensors make no representations or warranties whatsoever as to the accuracy, completeness, or suitability for any purpose of the Content. Any opinions and views expressed in this publication are the opinions and views of the authors, and are not the views of or endorsed by Taylor & Francis. The accuracy of the Content should not be relied upon and should be independently verified with primary sources of information. Taylor and Francis shall not be liable for any losses, actions, claims, proceedings, demands, costs, expenses, damages, and other liabilities whatsoever or howsoever caused arising directly or indirectly in connection with, in relation to or arising out of the use of the Content. This article may be used for research, teaching, and private study purposes. Any substantial or systematic reproduction, redistribution, reselling, loan, sub-licensing, systematic supply, or distribution in any form to anyone is expressly forbidden. Terms & Conditions of access and use can be found at http:// www.tandfonline.com/page/terms-and-conditions

International Journal of Production Research Vol. 50, No. 24, 15 December 2012, 7149–7166

Domain-based production configuration with constraint satisfaction

Linda L. Zhanga*, Qianli Xub, Yugang Yuc and Roger J. Jiaod

IESEG School of Management (LEM-CNRS), Catholic University of Lille, Lille, France; bDepartment of Computer Graphics & Interfaces, A*STAR, Singapore; cSchool of Management, University of Science and Technology of China, Hefei, China; dThe George W. Woodruff School of Mechanical Engineering, Georgia Institute of Technology, Atlanta, GA, USA (Received 19 September 2011; final version received 8 November 2011) Production configuration is well recognised as an effective means of planning production processes for product families. The major challenge of production configuration originates from the handling of the numerous constraints associated with product and process variety. This paper develops a constraint satisfaction approach to facilitate production configuration decisions regarding constraint identification, representation, and evaluation. A domain-based model is formulated to conceptualise the production configuration process, involving inter-connections among multiple domains in conjunction with diverse domain decision variables and constraints. Within the domain framework, production configuration is formulated as a constraint satisfaction problem (CSP), which is solved using constraint heuristic search. Within constraint heuristic search, a decision propagation structure incorporating a connectionist approach is developed to facilitate the exploration of solution spaces. A case study of textile spindle production configuration is elaborated to illustrate the feasibility and potential of the domain-based CSP model for production configuration. Keywords: production planning; operations planning; production modelling

a

Downloaded by [Beijing Jiaotong University] at 00:52 06 June 2014

1. Introduction Developing product families has attracted the attention of many manufacturing companies that strive to gain a competitive edge by providing a large variety of customised products and achieving configure-to-order production at low cost (Kumar et al. 2009, Ye et al. 2009). Production configuration lends itself to be an effective means for companies to exploit the process reuse and mass production efficiency underlying product families (Zhang 2007, Zhang and Rodrigues 2010). The rationale is to anchor the planning of production processes for product family members (or product variants) to a common platform (i.e. to reconfigure existing processes and capital), thus eliminating unnecessary process changeovers. Unlike the traditional trial-and-error-based planning practice, production configuration tries to achieve optimal production performance of the cohort of a product family with respect to, for example, time and cost, instead of an individual product. In addition, in the light of the fact that companies produce and deliver final products that are formed by both component parts and component assemblies (do Carmo-Silva and Alves 2006), it considers complete production processes, which includes both manufacturing processes for parts and assembly processes for assemblies, for final products. From a broad perspective, production configuration entails a process of (1) identifying the relevant process elements, such as routings, operations and manufacturing resources (e.g., machines, tools, fixtures) for the given product variants, (2) configuring production processes from the identified process elements, and (3) selecting appropriate processes based on the evaluation of the multiple alternatives configured. Due to the large product variety and the limited manufacturing resources available on the shop floor, production configuration involves numerous constraints that must be satisfied and/or compromised in order to obtain feasible solutions. The major difficulties of handling constraints in production configuration manifest themselves through constraint identification, representation and evaluation, as elaborated below. 1.1 Technical difficulties (1) Constraint identification. For a given product, its design specifications lead to a set of manufacturing requirements that can be fulfilled by different production processes. Such processes correspond to different

*Corresponding author. Email: l.zhang@ieseg.fr

ISSN 0020–7543 print/ISSN 1366–588X online ? 2012 Taylor & Francis http://dx.doi.org/10.1080/00207543.2011.640714 http://www.tandfonline.com

7150

L.L. Zhang et al.

Downloaded by [Beijing Jiaotong University] at 00:52 06 June 2014

routings (i.e. different configurations of operations, workstations/machines together with other necessary manufacturing resources). (For illustrative simplicity, ‘machines’ is used to denote ‘workstation/machines together with other necessary manufacturing resources’ in the following text.) Furthermore, it is common that different machines are able to perform operations on the same material items to complete the same jobs, and, in most cases, these operations incur different cycle times. Moreover, according to its specifications, any machine has a limited number of manufacturing capabilities. For example, a machine can perform operations on alloy steel, rather than aluminum. The above design specifications, manufacturing requirements, machine capabilities and mapping relationships between product and process variety lead to many restrictions (or constraints) in identifying proper process elements. In addition, in practice, companies use only one machine to process material items at one time, and adopt one production process to produce the same products, in the hope of reducing the difficulties and complexities in production on the shop floor (Borenstein and Becker 2004, Zheng et al. 2008). In this regard, determining the appropriate production processes needs to comply with additional constraints in association with performance measures. Thus, the diverse constraints must be identified properly for production configuration. The large product variety and the limited number of manufacturing resources impose difficulties in identifying these constraints. (2) Constraint representation. Personnel from different functional areas (e.g., designers, planners) view products from different perspectives, and employ different sets of contexts to interpret the same products. The resulting differences in semantics and terminology hinder the desired communication. Thus, constraints along with the associated product and process data need to be represented in such a way that can lead to the same interpretation. However, there are some inherent difficulties in properly representing the identified constraints. First, the constraints are normally expressed in abstract, fuzzy or conceptual terms in the natural language. Consequently, these terms are often associated with ambiguousness, adding difficulties in effectively representing the constraints. Second, in most cases, the types of constraints are a combination of both qualitative and quantitative constraints. Such multiple types impose difficulties in consistently representing constraints using one format. Third, due to product variety, both the categories and the numbers of constraints are large, which complicates constraint representation. (3) Constraint evaluation. Usually, many constraints are involved in the selection of a process element, be it a machine or an operation. In this regard, how to analyse and evaluate these constraints (e.g., which constraint should be considered first, what are the constraints to be considered subsequently) introduces difficulties in decision making in satisfying constraints. In such constraint satisfaction, many compromises and trade-offs might be involved. Moreover, different combinations of process elements can achieve the same objective. For example, more than one manufacturing process can produce the same parts. Thus, determining the necessary constraints and further satisfying them may impose additional difficulties in constraint analysis and evaluation.

1.2 Strategy for solution Due to its important role in many applications, constraint satisfaction is recognised as a promising approach to solving complex problems (Tsang 1993, H’Mida and Vernadat 2009). Thus, this study develops an approach based on constraint satisfaction to facilitate production configuration decisions regarding constraint identification, representation, and evaluation. A production configuration domain model is put forward to capture the many elements (e.g., components, operations) and constraints among them. Based on the domain model, production configuration is formulated as a constraint satisfaction problem (CSP). A number of variables and associated constraints are defined in the CSP. To solve the CSP by evaluating constraints, a decision propagation structure (DPS) is developed as a mechanism of constraint heuristic search (CHS) to explore the configuration space. A connectionist approach is further applied to refine the search space, leading to logical solutions with the appropriate selection of operations.

2. Related work 2.1 Production configuration In accordance with the unique characteristics of producing diverse products, new concepts and solution methods have been reported to achieve product family production efficiency. Two concepts most relevant to this study are

International Journal of Production Research

7151

Downloaded by [Beijing Jiaotong University] at 00:52 06 June 2014

reconfigurable manufacturing systems (RMS; Youssef and EIMaraghy 2006) and process configuration (Schierholt 2001). Due to the inherent design limitations, traditional manufacturing systems (e.g., dedicated manufacturing systems) and conventional manufacturing systems (e.g., cellar manufacturing systems) cannot produce a large variety of product variants without incurring high costs and long lead-times. In this regard, RMS has emerged as a new paradigm of manufacturing systems when facing product diversity. A number of researchers have investigated RMS from various aspects with focus on different issues. A review suggests that the reported work on RMS can be classified into two streams. One stream of research focuses on the handling of system component reconfiguration issues for part manufacturing. The representative group of this stream is from the NSF Engineering Research Center for RMS at The University of Michigan (http://erc.engin.umich.edu/). As a result of considering part manufacturing only, the proposed methods and frameworks cannot work well for products that include both parts and assemblies. In the other stream, researchers deal with the handling of manufacturing system reconfiguration for different product families with emphasis on production changeovers among product families (Zhao et al. 2000a, 2000b, Abdi and Labib 2003, 2004). Consequently, they do not address production variations of products belonging to the same families. In contrast to the research in RMS, production configuration tackles production variations both within and between product families. To exploit similarities among product variants in their production, Schierhot (2001) presents the concept of process configuration, where the product configuration principle is utilised to support process planning tasks. Zheng et al. (2008) develop a systematic knowledge model to facilitate process configuration. In their model, process knowledge is organised at different granularity levels, such as core process skeletons, process networks, process routes, etc. Aldanondo and Vareilles (2008) discuss in general how process configuration can be formulated as a CSP. In summary, due to its focus on part manufacturing only, in essence process configuration is an alternative to computer-aided process planning. As pointed out by do Carmo-Silva and Alves (2006) and Zhang and Rodrigues (2010), since what customers want are final products rather than parts or assemblies, more focus should be placed on process planning for complete products, instead of either parts or assemblies. In response to the lack of research, Zhang (2007) introduced production configuration to plan production processes for product families, where both component parts and assemblies are considered. In the literature, approaching production configuration from different perspectives, authors have reported their models and case studies. Jiao et al. (2008) deal with the identification of the mapping relationships between product and process variety inherent in production configuration based on association rule mining. Zhang et al. (2007) develop a structural model to help organise product and process family data in production configuration. Zhang and Rodrigues (2010) adopt Petri net techniques to model the production configuration process, in an attempt to shed light on the configuration dynamics. While the existing studies have their own foci, they do not clarify the reasoning behind production configuration, namely constraint handling in relation to enormous product and process variety.

2.2 Constraint satisfaction Constraint satisfaction has received much interest from both academia and industry. This is well evidenced by the many published articles and its applications in the real world, such as British Airways, British Telecom, French Railways, Cathay Pacific, the Port of Singapore, etc. (Tsang 1999). The constraint satisfaction paradigm provides not only a natural, simple and expressive language to model the problems, but well-established and efficient solution techniques and algorithms (Sabin 2003). In addition, solving complex problems based on constraint satisfaction can help clarify the reasoning behind finding solutions (Jonsson and Frank 2000). To capture more adequately the specific characteristics of the application domains, a number of extensions of standard CSPs have emerged, including dynamic CSPs (Mittal and Falkenhainer 1990), generative CSPs (Haselbock 1993), composite CSPs (Sabin and Freuder 1996), and conditional CSPs (Sabin and Freuder 1998). In general, studies of CSPs can be categorised into two groups: CSP applications and CSP solution techniques development. Authors from the computer science community have devoted themselves to the development of more efficient CSP solution techniques and algorithms (Tsang 1993, Sabin and Freuder 1998, Gelle and Faltings 2003, Sabin 2003). CHS (Fox et al. 1989) and the connectionist approach (Tsang 1993) have been proven to be powerful techniques to solve CSPs (Sathi et al. 1992, Tsang 1993). While CHS integrates constraint satisfaction and heuristics search, thus providing the advantages of both, the connectionist approach is able to determine the feasibility of solutions by testing against constraints. In light of their problem-solving capabilities and the nature of constraints in

7152

L.L. Zhang et al.

production configuration (to be elaborated in Section 5), in this study we incorporate both CHS and the connectionist approach in our solution framework. The application of constraint satisfaction encompasses a wide range of areas, including planning and scheduling, computer vision, verification and diagnosis, engineering design, and product configuration (Gelle and Faltings 2003, Sabin 2003). In particular, many authors have applied constraint satisfaction to product configuration (Frayman 1989, Mittal and Stumptner and Haselbock 1993, Stumptner et al. 1994, Fohn et al. 1995, Xie et al. 2005). As mentioned earlier, Aldanondo and Vareilles (2008) discuss in general how process configuration can be formulated as a CSP. While as a starting point their work may stimulate in-depth research on process configuration, it does not touch on how to solve process configuration based on constraint satisfaction. Moreover, the formulation in their work is too simple to cover most of the restrictions and variables in real-world production. The study reported in this paper lends itself to be a new initiative to formulate production configuration as a CSP. It also goes a step further by adopting CHS and the connectionist approach to solve production configuration.

Downloaded by [Beijing Jiaotong University] at 00:52 06 June 2014

3. Overview of domain-based production configuration 3.1 Production configuration domains Production configuration entails a configurable process model representing a family of all possible production processes to fulfill the corresponding product variants in a family. A production process relates to a routing that is determined by operations and the corresponding machines (Balogun et al. 2004). In accordance with product components, be they parts or assemblies, a routing of a final product can be decomposed into a number of subroutings, each of which is for producing a product component. This study employs the above understanding of production processes. Accordingly, production configuration encompasses four domains, namely the product, component, routing, and operations domain, as shown in Figure 1. The domain model helps organise the variables in production configuration by associating the characteristics of domain elements with these variables. For instance, the product domain embodies the interpretation of product families and product variants. The interconnections between domains are represented by arrows. The inter-domain connections together with each individual domain are the basis for identifying constraints. The product domain represents the set of product families (PFs) and product family members (FMs) (i.e. product variants). The members of each family differ from one another in terms of their unique components, which may present in the form of assemblies or parts. In the component domain, all the component families (CFs) involved in a PF are modelled. Each CF can be a component assembly family or a component part family, consisting of a number of specific component variants (CVs). Each product in the product domain can be fulfilled by at least one routing. In accordance with the components in a product hierarchy, each routing consists of several specific subrouting alternatives (SAs) in the routing domain. Essentially, the specific alternatives of the same sub-routing form an abstract sub-routing family (SF). Each SA specifies the precedence relationships between operations, and is determined by specific operations together with machines. In the operations domain, an operation (Op) is described by the machines (Ms) that can perform it and the corresponding cycle times (CTs). One operation can be carried out by more than one machine, and, similarly, one machine can perform multiple operations. Therefore, different combinations of operations and their machines form different sub-routings in the routing domain to produce the same product in the product domain.

Product domain PF FM 1 FM 2 FM FM a

Component domain CF CV 1 CV 2 CV b

Routing domain SF SA 1 SA 2 SA d

Operations domain Op M/CT 1 M/CT 2 M/CT c

Figure 1. The domains in production configuration.

International Journal of Production Research

7153

3.2 The domain-based constraint satisfaction model Figure 2 shows the proposed domain-based constraint satisfaction model for production configuration. Three consecutive stages are involved: conceptualisation, CSP formulation, and CSP solution. (1) Conceptualisation. To deal with the complexity resulting from the large volumes of product and process data, the first stage is to construct a production configuration domain model, as shown in Figure 1. The purpose is to embody the relationships between products, processes, products and processes, and the configuration of production processes. (2) CSP formulation. Based on the domain model, production configuration is formulated as a CSP. To accomplish this, constraint satisfaction techniques are employed to model the decision factors within and between domains. The decision factors include variables and the associated constraints. (3) CSP solution. As a powerful tool of CHS, DPS is applied to explore the search space defined in production configuration. Decision scores and choice scores are assigned to alternative solutions, functioning as the operators to prune the search space. Subsequently, the stability of the candidate solutions is tested using the connectionist approach, leading to a refined state-space. The feasible solution is considered to be found when a complete constraint graph is established based on the stable state of the connectionist network.

Downloaded by [Beijing Jiaotong University] at 00:52 06 June 2014

4. CSP formulation A CSP is defined as a triple, P ? hV, D, Ci, where V ? fv1 , v2 , . . . , vn g is a finite set of variables, D ? fDv1 , Dv2 , . . . , Dvn g is a set of domains of the corresponding variables, providing a finite set of values for each variable vi : Dvi ? fdi1 , di2 , . . . , dij g, and C ? fc1 , c2 , . . . , cm g is a finite set of constraints. A constraint cj with arity j specifics the set of allowed combinations of values for a set of variables v1 , v2 , . . . , vj , which is a subset of the Cartesian product of the domains of the variables. The goal is to find either one or all solutions to a CSP, P ? hV, D, Ci. Each solution manifests an assignment of a value from its domain to every variable from V such that every constraint from C is satisfied. This indicates that solving a CSP instance simply means determining whether or not there is a substitution C : V ° D that satisfies all constraints. In accordance with the unique characteristics of production configuration, this study identifies variables along with their domains and constraints for formulating production configuration as a CSP as follows.

Figure 2. An overview of constraint satisfaction-based production configuration.

7154

L.L. Zhang et al.

4.1 Variable modelling In the light of the domain model in Figure 1, product variants, product components, sub-routings, and operations are the major elements to be dealt with in production configuration. In accordance with these major elements, there ? are four types of variables, namely VP , VR, VR and VO , along with their associated domains, that are deemed to be associated with production configuration decisions. The union of these variables forms the entire set of variables, VPC, in the domain-based constraint satisfaction model for production configuration: VPC ? VP [ VR [ VR [ VO , where (i) VP ? f p1 , p2 , . . . , pa g?a 2 Z? ? model the determination of individual products as variables, where a is the cardinality of the set of product variants belonging to a family, and p1 , p2 , . . . , pa are the variables modelling the choice of a different product variants with 1, if pi is to be produced, pi ? 0, otherwise,

?

Downloaded by [Beijing Jiaotong University] at 00:52 06 June 2014

where i ? 1, 2, . . . , a: (ii) VR ? fr1 , r2 , . . . , rb g?b 2 Z? ? models the determination of component assemblies and parts and thus the corresponding sub-routings as variables, where b is the total number of sub-routings to produce the corresponding component assemblies and parts in the product family, and r1 , r2 , . . . , rb are the variables modelling the choice of b different sub-routings, with 1, if ri is chosen, ri ? 0, otherwise, where i ? 1, 2, . . . , b: ? (iii) VR ? fr11 , r12 , . . . , r1jr1 j , . . . , ri1 , ri2 , . . . , rijri j , . . . , rbjrb j g?b 2 Z? ; jrb j 2 Z? ? models the selection of specific alternatives to implement the above sub-routings as variables, where b is the total number of sub-routings and jrb j is the total number of alternatives of rb , and r11 , r12 , . . . , rbjrb j are the variables modelling the choice of different sub-routing alternatives, with 1, if rij is chosen, rij ? 0, otherwise, where i ? 1, 2, . . . , b and j ? 1, 2, . . . , jri j. (iv) VO ? fo1 , o2 , . . . , oc g?c 2 Z? ? models the selection of operations as variables, where c is the cardinality of the set of operations involved in producing the product family, and o1 , o2 , . . . , oc are the variables modelling the choice of c different operations, with oi ? where i ? 1, 2, . . . , c. Therefore, VPC ? fp1 , p2 , . . . , pa g [ fr1 , r2 , . . . , rb g [ fr11 , r12 , . . . , rbjrb j g [ fo1 , o2 , . . . , oc g: In line with the above modelling, domains of the four types of variables are identified and represented as DVP , DVR , DVR? , and DVO . The domain set DVP ? fDVP ga describes the determination of product variants belonging to a i family, DVR ? fDVR g describes all the possible combinations of sub-routings in accordance with component items in b i the product family, DVR? ? fDVR? gd describes all the possible combinations of sub-routing alternatives that can be i used to produce product variants, and DVO ? fDVO gc describe all the possible combinations of operations that can i form sub-routing alternatives. Accordingly, the domains for all four types of variables are f0, 1g, i.e. DVP ? f0, 1g, i for i ? 1, 2, . . . , a, 1, 0, if oi is chosen, otherwise,

International Journal of Production Research

7155

DVR ? f0, 1g, i DVR? ? f0, 1g,

i

for i ? 1, 2, . . . , b, for i ? 1, 2, . . . , d, for i ? 1, 2, . . . , c:

DVO ? f0, 1g,

i

Note that, in the CSP context, the meaning of domain D is different from that in the production configuration domain model. While for the former, domains refer to all possible values that can be assumed by the respective variables, for the latter they are associated with the different stages in production process planning.

Downloaded by [Beijing Jiaotong University] at 00:52 06 June 2014

4.2 Constraint identification A constraint, cj 2 C, is used to restrict the problem variables fv1 , v2 , . . . , vj g 2 VPR within certain boundaries so as to reduce the number of potential solutions to be explored. Such constraints act as declarative statements, which state the relationships that must be satisfied by the variables. These constraints may assume different forms, and may originate from many sources. Production configuration addresses production process planning for product families by capitalising on design similarities in production. Therefore, in production configuration, for given product specifications, the first task is to determine whether or not the products belong to an existing family. Subsequently, sub-routings and their specific implementation alternatives in accordance with component assemblies and parts are to be considered. Finally, operations and machines are to be evaluated to determine whether or not they can be selected to form the subrouting alternatives. In making decisions of operations and machines selection, several factors, such as operations capability, compatibility, and cycle time, need to be taken into account. In line with the above process, constraints in production configuration are identified, and further classified into eight categories. (i) GC 1 : Production capability. Constraints in this category determine whether or not a product variant belongs to the product family under consideration, i.e. whether or not products can be produced by taking advantage of process similarity inherent in a product family. By considering the domains (i.e. f0, 1g) of the variables involved in this constraint category, the representation of this constraint category is 1, if pi belongs to product family P, C G1 ? pi jP? ? 0, otherwise: (ii) GC 2 : Routing capability. Constraints in this category denote the capability of a sub-routing, ri , associated with an item to produce a product, pj . The implication is whether or not the item is a constitute component of the product. Similarly, the representation of constraints in this category is 1, if ri can be used to produce pj , C G2 ?ri , pj ? ? 0, otherwise: (iii) GC 3 : Routing compatibility. Constraints in this category determine the compatibility of two sub-routings, ri and rj , i.e. whether or not ri and rj can be used together to produce the product, pa . The representation of constraints in this category is 1, if ri and rj can be used together to produce pa , GC ? r , r j p ? ? a 3 i j 0, otherwise: (iv) GC 4 : Implementation capability. Constraints in this category denote the capability of a specific sub-routing alternative, rij , to implement a sub-routing, ri , i.e. whether or not rij is an instantiation of ri . The representation of constraints in this category is 1, if rij is able to implement ri , GC ? r , r ? ? ij i 4 0, otherwise:

7156

L.L. Zhang et al.

(v) GC 5 : Routing alternative compatibility. Constraints in this category denote the compatibility of two specific sub-routing alternatives, rab and rst , i.e. whether or not rab and rst can be adopted together to implement ri . The representation of constraints in this category is 1, if rab and rst can be used together to implement ri , GC ? r , r j r ? ? 5 ab st i 0, otherwise: (vi) GC 6 : Operations capability. Constraints in this category denote the capability of an operation, oi , to fulfill the required task, thus being included in a sub-routing alternative, rab . The representation of constraints in this category is 1, if oi can be included in rab , C G6 ?oi , rab ? ? 0, otherwise: (vii) GC 7 : Operations compatibility. Constraints in this category determine the compatibility of two operations, oi and oj , i.e. whether or not oi and oj can be adopted together to form the specific sub-routing, rab . The representation of constraints in this category is 1, if oi and oj can be used together in rab , C G7 ?oi , oj jrab ? ? 0, otherwise: (viii) GC 8 : Cycle time of a production process. Unlike the above constraints, constraints in this category address decision making in production process selection at a higher level by referring to the aggregated cycle time of operations. The representation of constraints in this category is ( GC 8 ?oi , rst , rs , pa ? ? 1, 0, if PPP

s t t

Downloaded by [Beijing Jiaotong University] at 00:52 06 June 2014

T?oi , rst , rs , pa ?

S

T? pa ?

otherwise,

where T?oi , rst , rs , pa ? is the cycle time of oi in rst of rs to produce pa , and S T? pa ? is the allowable maximum cycle time for producing pa .

C C C C C C Among these constraint categories, GC 1 , G2 , G3 , G4 , G5 , G6 and G7 are ‘hard’ constraints that should not be violated in any circumstances. This is because the relations they denote are determined by design and production capabilities. On the other hand, constraints GC 8 are ‘soft’ and violation is permitted, provided that (1) a solution that satisfies all constraints is not available, or (2) the violation can bring benefits that counteract the loss of constraint violation.

5. CSP solving The large variety of product variants leads to an increased number of process element options, such as sub-routings C C and operations (Wortmann et al. 1997). Decisions regarding these options are manifested by GC 2 , G4 and G6 . Because of such a large number of options, solving production configuration may require additional effort in understanding each option and its effect on the solution. The traditional constraint satisfaction techniques, such as problem reduction, solution space search, and solution synthesis, are mainly applied to remove values that do not satisfy the constraints or to assign plausible values to variables (Tsang 1993). Consequently, they are inefficient in dealing with this type of problem, where many options exist to accomplish the same objective, because they tend to assign values to variables without exploiting information on the available choices and alternatives. In such a context, finding a single, feasible solution with high search efficiency is of paramount importance. Heuristic-based search methods suggest themselves to be effective in tackling this type of problem, where heuristic rules are used to guide the search towards a direction that is more likely to lead to solutions (Tsang 1993). Therefore, this study adopts CHS (Fox et al. 1989) and develops a DPS to facilitate search in the solution space. In solving production configuration, after an initial solution is found using CHS, the task is reduced to check whether or not the other constraints are violated. If they are, it is required to refine the solution so as to bring it to a new, feasible one. The major challenge is how to deal with the constraints that are associated with a series of subsets of variables, as these are associated with different constraints within the production configuration domain model. The connectionist approach has been proven to be efficient in dealing with CSP with massive parallelism associated

International Journal of Production Research

7157

with various constraints (Tsang 1993). Thus, in this study, we adopt the connectionist approach together with the C C C C C C C C DPS to deal with GC 1 , G2 , G3 , G4 , G5 , G6 and G7 , especially G4 and G6 . Based on the stable state of the connectionist network, a complete constraint graph is established to determine potential solutions. Finally, constraint category GC 8 is checked manually based on the calculation of cycle times of production processes.

Downloaded by [Beijing Jiaotong University] at 00:52 06 June 2014

5.1 Decision propagation structure The CHS problem-solving paradigm aims to seek solutions through state-space search. The search procedure is steered by heuristics, and moves from one point to another in the solution space. The next search step is partially determined by the consequence of the previous move. Therefore, the heuristic search method is considered as nondeterministic in nature. In this study, CHS is applied to determine specific product variants, and identify the corresponding sub-routings and operations. The DPS is used as the mechanism, guiding the selection of possible alternatives in the solution search process. It portrays the search process with the CSP as the starting point. Each search process in the DPS will result in a partial constraint graph. The partial graph will eventually be completed when the DPS is exhaustively pruned. DPS consists of search spaces that are represented as nodes, and the corresponding states at that particular search instance, as shown in Figure 3. It represents a solution space that is free of constraints. In order to make the search more efficient, the choice-scoring and decision-scoring operators are applied to prune the DPS starting from the top level, modelling the decomposition of the production process of product pi . In most cases, the production process of a product can be decomposed into a number of sub-routings, r1 , r2 , . . . , rm , in accordance with the component assemblies and component parts. Given each sub-routing ri , there are a number of specific alternatives ri1 , ri2 , . . . , rijri j . Each specific alternative, rij , is formed by a number of operations o1 , o2 , . . . , on . Each of these operations can normally be performed by a number of machines m1 , m2 , . . . , mM . The choice- and decision-scoring routines, which are based on the concept of task decomposition (Turner and Turner 1999), steer the pruning of the DPS by selecting appropriate nodes to add to the partial constraint graph. The pruning process begins with an initial DPS comprising an empty constraint graph. The decision-scoring routine is applied when two or more child nodes are required at an AND node, that is a task must be fulfilled by two or more sub-tasks. For example, the node modelling the production process of product pi demands the presence of four child nodes, r1, r2, ri and rm . All of these sub-routings represented by the four child nodes must be included in the production process to produce pi . The choice-scoring routine is applied at the OR nodes, where there are a number of alternatives for selection. For instance, r11 , r1i and r1jr1 j are three specific sub-routings that can implement r1 . In other words, r11 and r1jr1 j are alternatives to r1i . Figure 4 shows flowcharts of the choice-scoring and decision-scoring routines. Since machines are the potential values of the operations, a choice score is proportional to the number of machines that can perform the same operation. An OR node with a higher choice score indicates that it has more flexibility in terms of fulfilling the task, and should be selected first among sibling nodes. On the other hand, an AND node with the lowest decision score indicates that it is the most constrained and should be added to the constraint graph first.

Figure 3. Decision propagation structure for production configuration.

7158

(a)

Start Yes Stop Is the node list empty? No Get a node Yes

L.L. Zhang et al.

(b)

Start Yes Stop Is the node list empty? No Get a node Assign the domain size as its decision score Yes Assign the domain size as its choice score

Is it a leaf node? No Get a child node

Is it a leaf node? No Get a child node

Assign the minimum decision Is it an AND- Yes score of child node? nodes as its decision score No Assign the sum of decision scores of child nodes as its decision score

Is it an ORnode? No

Assign the maximum choice Yes score of child nodes as its choice score

Assign the minimum of choice score of child nodes as its choice score

Downloaded by [Beijing Jiaotong University] at 00:52 06 June 2014

Figure 4. Flowcharts of choice-scoring and decision-scoring routines. (a) Flowchart of decision-scoring, (b) Flowchart of choicescoring.

5.2 Connectionist approach The power of the DPS method lies in its efficiency in finding a feasible solution, which may only satisfy partial constraints. This solution must be tested against other concerned constraints before it can be validated as a solution that satisfies all constraints. For such a purpose, the connectionist approach (Tsang 1993) is applied to validate the initial solution in this study. The connectionist approach utilises the notions of nodes, arcs, and weights to represent the networked entities where nodes are connected by arcs. Each arc is associated with a weight, which is a positive or negative integer number, representing activation or deactivation states, respectively. The connectionist network state collates the states of all individual nodes and the weights of those connecting arcs, thus representing the constraint problem. A potential solution is considered to be found when the network reaches a stable state. In the connectionist network, each label for a variable is represented by a node, where a label refers to a tuple hvariable, valuei. All the nodes for a variable constitute a cluster. Two nodes are connected by an arc if a constraint exists between the corresponding labels. A node x may assume two states, activated and deactivated, where the former is denoted Sx ? 1 and the latter Sx ? 0. A default value, usually negative (e.g., ‘–1’), is assigned to each of the weights initially. Using the results from the choice- and decision-scoring routines, only one node is ‘activated’ at any one time. Moreover, each node is assigned a value, called the input, based on the following equation: X Wx,y ? Sy , I?Nx ? ?

y neighbouring?x?

where Wx,y is the negative weight value (e.g., ?1) assigned to the connected pair of Nx(nodex) and Ny(nodey), and Sy is the state of Ny(nodey). Sy ? 1 if y is activated, otherwise Sy ? 0. As such, the input value that is assigned to Nx is the sum of the weights on the activated nodes in its neighbourhood. The nodes are in continuous competition to be activated. In every cluster, it is desirable that the node with the largest input be activated, while the rest deactivated. This is because, with all weights assigned negative values, such a node represents a label that violates the fewest constraints. In the event that two or more candidates in the same cluster are eligible to be activated, priority is given to the node that is already activated in the prior cycle. Otherwise, the tie will be broken randomly. When the node with the largest input is activated, the respective cluster is considered to be in a stable state. If all clusters are in stable states, the network is considered to be in a stable state. Furthermore, when all the activated nodes in a stable network have zero input, a solution satisfying all constraints is considered to be found. Otherwise, the stable state of the network represents a local optimum, where some ‘soft’ constraints are violated. Figure 5 illustrates how production configuration is represented as a set of networked nodes and arcs. Figure 6(a) shows a state of production configuration, where an activated node is highlighted and the input to a node is indicated next to it. In Figure 6(a), C#1 (cluster 1) is unstable because node hr1 , 0i, which has a higher

International Journal of Production Research

Products Variables Domains 0 1 p1 p2 pa r1 Routings r2 rb r11 Subroutings r12 Rb|rb| o1 Operations o2 oc

7159

Figure 5. Production configuration network of nodes and arcs.

(a) Variables Domains 0

r1 0 –2 C#1

r2 –2 –1 C#2

r3 –1 –2 C#3

r4 –3

r5

(b) Variables Domains –1 0 1

r1 0 –1 C#1

r2 0 –3 C#2

r3 –1 –2

r4 –2

r5

Downloaded by [Beijing Jiaotong University] at 00:52 06 June 2014

–1 –2 –1 C#3 C#4 C#5

1

–1 –1 C#4 C#5

Figure 6. States of the production configuration network. (a) A state of connectionist network, (b) A stable state of network (local optium).

input (0), is not activated. For similar reasons, C#2 and C#3 are unstable. C#4 is stable because node hr4 , 1i, which has a higher input (?1), is activated. C#5 is stable because when the nodes in a cluster have identical input, an arbitrary node can be selected to activate. Figure 6(b) represents a stable state of the network, which is a local optimum, because the input to the activated nodes, hr3 , 0i, hr4 , 1i and hr5 , 1i, are negative values, instead of 0, indicating that a solution cannot be found without violating some constraints. In the production configuration network, the initial states of the nodes are assigned based on the results of DPS. This indicates that a set of nodes are already selected, and the states of these nodes are fixed and remain activated in subsequent steps. On the other hand, at the initial stage, not all states of the nodes are determined, such that some nodes may change their states. By repeatedly changing the states of nodes, the entire network may converge to a stable state, representing either a solution or a local optimum. In the latter situation, one may remove the local optimum by updating the weights of arcs. A general weight updating rule is represented as W0x,y ? Wx,y ? Sx ? Sy : The above equation indicates that when the states of two nodes x and y are both activated, the weight of the arc that connects them is increased by ‘1’. Thus, if the old weight (W) is ?1, the new weight (W0 ) will be 0. The indication is that some ‘soft’ constraints are relaxed. The process of changing an activated node and the weight of arcs is called a stability check. The objective is to bring the network to a stable state by having zero as input to all nodes. The stability check routine is adapted from the GENET algorithm of Tsang (1993).

6. Case study 6.1 Industrial example The proposed constraint satisfaction approach is applied to the production configuration of a family of textile spindles (TSs). Spindles are used in weaving machines to produce clothes fabric, wool, etc. Each TS consists of two major component assemblies: a shaft assembly (SA) and a rocker arm assembly (RA). For illustrative simplicity, this case study addresses the configuration of the production process for a customised TS by considering these two major assemblies. Accordingly, sub-routings of the SA variant and the RA variant of the customised TS are to be determined. Based on the existing manufacturing capability to produce the TS family and the specifications of the

7160

L.L. Zhang et al. Table 1. The customised TS and the possible sub-routings. Component item An SA variant An RA variant Sub-routing Sub-routing of the SA variant (r1) Sub-routing of the RA variant (r2) Sub-routing alternative Alternative Alternative Alternative Alternative #1 #1 #1 #1 (r11) (r12) (r21) (r21)

Table 2. Sub-routing alternatives and the possible operations. Operation sub-routing #1 (o1) 3 – – – #2 (o2) 3 – – – #3 (o3) – 3 – – #4 (o4) – 3 – – #5 (o5) – – 3 – #6 (o6) – – – 3 #7 (o7) – – – 3

Downloaded by [Beijing Jiaotong University] at 00:52 06 June 2014

r11 r12 r21 r22

Note: ‘3’ indicates that operations are required; ‘–‘not required.

Table 3. Operations and the possible workstations/machines. Multifunction work centre #4 (M4) – – 25 seconds – – – – Multifunction work centre #5 (M5) 10 seconds – – 24 seconds – – – Multifunction work centre #6 (M6) – – – – – 15 seconds –

Operation #1 #2 #3 #4 #5 #6 #7 (o1) (o2) (o3) (o4) (o5) (o6) (o7)

Workstation #1 (M1) – – – – 20 seconds – 25 seconds

Workstation #2 (M2) 20 seconds 12 seconds 22 seconds 25 seconds – 20 seconds

Workstation #3 (M3) – 13 seconds 20 seconds – – – –

Note: ‘–‘indicates that a workstation cannot carry out the corresponding operations; the unit of cycle time is seconds.

customised TS, the possible sub-routing alternatives, operations, machines, and cycle times have been identified for the SA variant and the RA variant, as shown in Tables 1, 2 and 3. The values in the cells of Table 3 are the cycle times incurred using the workstations and the corresponding machines to carry out the relevant operations. (Due to company confidentiality, the real data pertaining to workstations and operations are disguised.) To avoid potential delivery delay, the allowable maximum cycle time of the final production process for the customised TS has been specified by the planner of the case company as 45 seconds.

6.2 Production configuration domain model and variables In accordance with the unique issues and elements in configuring production processes for TSs, the production configuration domain model is constructed, as shown in Figure 7. This domain model not only facilitates the conceptualisation of TSs’ production configuration and the modelling of production configuration as a CSP, but also the subsequent solution search. In the figure, all operations, sub-routings, TSs, and component items are

International Journal of Production Research

Product domain TS family SA family TS #1 SA #1 TS #2 TS #3 SA #2 SA #3 SA_SA #2 SA_SA #3 SA_SA #1 SA Subrouting Component domain Routing domain Operations domain

7161

Operation #1 W#2/CT W#5/CT

VP

p1 = TS #1 p2 = TS #2 p3 = TS #3 ---

VR

r1 = SA subrouing r2 = RA subrouing

VR

*

VO

o1 = Operation #1 o2 = Operation #2 o3 = Operation #3 o4 = Operation #4 o5 = Operation #5 o6 = Operation #6 o7 = Operation #7

r11 = SA subrouing alt. (SA_SA #1) r12 = SA subrouing alt. (SA_SA #2) --r21 = RA subrouing alt. (RA_SA #1) r22 = RA subrouing alt. (RA_SA #2) ---

Downloaded by [Beijing Jiaotong University] at 00:52 06 June 2014

Figure 7. Textile spindle production configuration domain model and variables.

represented as characteristics of the corresponding domains. The configuration of production processes is accomplished through mappings across domains. Also shown in the figure is the definition of variables.

6.3 Production configuration constraints With regard to the TS family and the customised TS, p1 , the constraints and the assignments of values to them are presented as follows. (1) Production capability GC 1 . This category of constraints determines whether or not the TSs ordered by customers belong to the family under consideration. In this case study, the customised TS, denoted as p1 , belong to the TS family P. Thus, the only constraint in this category is represented as GC 1 ? p1 jPj? ? 1. (2) Routing capability GC . This category of constraints indicates whether or not sub-routings in association with 2 component items should be included to produce a TS variant. Since p1 consists of an RA variant and an SA variant, the corresponding sub-routings, r1 and r2 , should be selected. Thus, the representation of the two relevant constraints is GC 2 ?r1 , p1 ? ? 1, GC 2 ?r2 , p1 ? ? 1:

(3) Routing compatibility GC 3 . This category of constraints specifies whether or not two sub-routings can be used together to produce a TS. The inclusion of the TA variant and the SA variant in p1 entails the following constraint assignment: GC 3 ?r1 , r2 j p1 j? ? 1. (4) Implementation capability GC 4 . This category of constraints determines whether or not sub-routings can be implemented by specific alternatives. By referring to the capabilities of sub-routing alternatives given in Table 1, the representation of this category of constraints is GC 4 ?r11 , r1 ? ? 1, GC 4 ?r21 , r2 ? ? 1, GC 4 ?r12 , r1 ? ? 1, GC 4 ?r22 , r2 ? ? 1, GC 4 ?r11 , r2 ? ? 0, GC 4 ?r21 , r1 ? ? 0, GC 4 ?r12 , r2 ? ? 0, GC 4 ?r22 , r1 ? ? 0:

(5) Routing alternative capability GC 5 . This category of constraints specifies whether or not two alternatives can be used together to implement the same sub-routing. Although the selection of different sub-routing alternatives contributes to different production processes that can be configured, when configuring one production process, only one alternative of a sub-routing is considered. That is, two alternatives are not used together to produce a component. The purpose is to reduce the complexity and the resulting possible inappropriate decision making in configuration. In this respect, the specification of this category of

7162

L.L. Zhang et al.

constraints is GC 5 ?r11 , r12 jr1 ? ? 0, GC 5 ?r21 , r22 jr2 ? ? 0, GC 5 ?r11 , r12 jr2 ? ? 0, GC 5 ?r21 , r22 jr1 ? ? 0:

(6) Operations capability GC 6 . This category of constraints indicates whether or not an operation is required to be included in a sub-routing alternative. Based on the possible combinations of sub-routing alternatives and operations in Table 2, this category of constraints (28 in total) is modelled as follows: GC 6 ?o1 , r11 ? ? 1, ??? GC 6 ?o7 , r11 ? ? 0, GC 6 ?o1 , r12 ? ? 0, ... GC 6 ?o7 , r12 ? ? 0, GC 6 ?o1 , r21 ? ? 0, ... GC 6 ?o7 , r21 ? ? 0, GC 6 ?o1 , r22 ? ? 0, ... GC 6 ?o7 , r22 ? ? 1:

(7) Operations compatibility GC 7 . This category of constraints specifies whether or not a sub-routing alternative demands the presence of two operations. In accordance with the specifications of routing alternatives and operations in Table 2, the assignment of this category of constraints (84 in total) is

Downloaded by [Beijing Jiaotong University] at 00:52 06 June 2014

GC 7 ?o1 , o2 jr11 ? ? 1, ... GC 7 ?o6 , o7 jr11 ? ? 0,

GC 7 ?o1 , o2 jr12 ? ? 0, ... GC 7 ?o6 , o7 jr12 ? ? 0,

GC 7 ?o1 , o3 jr11 ? ? 0, ... GC 7 ?o6 , o7 jr21 ? ? 0,

GC 7 ?o1 , o3 jr12 ? ? 0, ... GC 7 ?o6 , o7 jr22 ? ? 1:

(8) Cycle time of a production process GC 8 . Cycle time constraints introduce the allowable maximum time to produce a TS. The belief is that the longer the cycle time, the higher the production cost, as proved by Tielemans (1996). Since the company’s planner specifies the maximum cycle time as 45 seconds for p1 , the cycle time constraint is GC 8 T?oi , rst , rt , p1 ? 45 ?for i ? 1, 2, . . . , 7, s ? 1, 2, t ? 1, 2?:

6.4 Production configuration decision process The production configuration decision process involves a procedural search of the state-space of the CSP. In this study, the DPS is applied first to prune the search space according to the representation of constraint categories GC 1, C C C GC , G , G and G . Subsequently, the connectionist approach is applied to refine the state-space by exerting 5 7 2 3 C constraint categories GC 4 and G6 , where alternative choices are involved. Based on the results of searching the DPS and refining the space based on the connectionist approach, a complete constraint graph is established in the hope of finding candidate solutions. Finally, the candidate solutions are checked against constraint category GC 8. The decision propagation structure is constructed, as shown in Figure 8. The top level indicates the production configuration for p1 , which belongs to the spindle family. The next level models the sub-routings, r1 and r2 ,

Production process of p1 Subrouting of SA (r1) Subrouting of RA (r2)

Subrouting alternative (r11)

Subrouting alternative (r12)

Subrouting alternative (r21)

Subrouting alternative (r22)

Operaiton Operaiton #1 (o1) #2 (o2) ?M2 / 20 ?M3 / 10 ?M2 / 12 ?M3 / 23

Operaiton #1 (o1) ?M2 / 20 ?M5 / 10

Operaiton Operaiton #3 (o3) #4 (o4) ?M2 / 20 ?M4 / 25 ?M5 / 24 ?M2 / 22

Operaiton #5 (o5) ?M1 / 20 ?M2 / 25

Operaiton Operaiton #6 (o6) #7 (o7) ?M6 / 15 ?M2 / 20 ?M1 / 25

Figure 8. Decision propagation structure for the spindle family.

International Journal of Production Research

7163

Downloaded by [Beijing Jiaotong University] at 00:52 06 June 2014

in connection with the SA and RA variants, respectively. There are four sub-routing alternatives to implement r1 and r2 , and they are denoted at the third level as r11 , r12 , r21 and r22 . After determining the sub-routing alternatives, operations and their machines will be specified to be included in an alternative. By referring to the constraints in GC 5, C , and G , some branches of the DPS are pruned, as indicated by the slashes. For example, the branch involving GC 7 6 the sub-routing of SA (r1 ) and the sub-routing of RA (r2 ) is pruned because r22 cannot be used to produce the SA variant. After the pruning of some branches, a state-space search guided by heuristics is applied to the DPS in an attempt to find a solution efficiently. The state-space search process begins from the root to the leaves of the DPS. The choice- and decision-scoring routines are applied according to the rules for OR and AND nodes. As explained ? previously, an AND relation exists between VP and VR , and between VR and VO ; an OR relation exists between VR ? and VR . Figure 9 shows the node selection process along the DPS, where nodes are labeled ‘D’ and ‘C’ representing their decision scores and choice scores, respectively. The arrows indicate the selection of sub-routings and operations, whereas the slashes depict branches that have been pruned. In a top-down manner, the decision-scoring routine chooses the node with the smallest ‘D’ value. This requires determining the sub-routing alternative for the RA variant first. This is shown as path A in the figure. The next step involves the choice-scoring selection process for the next node. It chooses r21 or r22 with the largest ‘C’ value. This is shown as path B, where r21 has the highest ‘C’ value. As o5 is the only child node of r21 , it becomes the first variable to add to the constraint graph C, as shown in Figure 10(a). The DPS is further pruned to remove the non-chosen branch, indicated by D.

Production process of p1 D=4 C=2 r1 D=2 C=2 r11 D=2 C=2 o1 ? M2/20 ? M5/10 D=2 C=2 o2 ? M2/12 ? M3/23 D=2 C=2 o3 ? M2/20 ? M4/25 D=2 C=2 r12 D=2 C=2 o4 ? M5/24 ? M2/22 D=2 C=2 r21 D=2 C=2 o5 ? M1/20 ? M2/25 D=1 C=1 o6 ? M6/15 D=3 C=2 r2 D=1 C=1 r22 D=2 C=2 o7 ? M2/20 ? M1/25

Figure 9. Choice- and decision-scoring on the DPS.

(a)

20 o5 25 M2 M1

(b) M3 23 o2

(c) M3 23 o2 12

20 o5 25

M1 M2 12

20 o5 25

M1 M2

: Variable node : Constraint node

20

o1 10

20

o1 10

xx: Cycle time : Unassigned value

M5

M5

Figure 10. Evolution of the constraint graph.

7164

(a) Variables Domains 0

–1 –2 –2 –1 0 –2 0 –2 –1 -1 –2

L.L. Zhang et al.

(b)

r11

r12

o1

o2

o3

o4

Variables Domains 0

r11

r12

o1

o2

o3

o4

–1 –1

–2 0

0 –2

–1 -1 0

–2 -2 0

0 –3 -3

0 –1 -1

1

1

Figure 11. State change of the connections network. (a) The initial state of partial network, (b) A stable state of the network.

Downloaded by [Beijing Jiaotong University] at 00:52 06 June 2014

A new search state is created. The search process returns to the top of the DPS, and selects the remaining r1 as indicated by path E. As the computed values for the decision-scoring and the choice-scoring for r11 and r12 are identical due to the same number of machines that can perform the operations involved, no preference is given by the choice-scoring routine. Thus, based on the result of searching along the DPS, the sub-routing alternative and operations for the RA variant are determined. The machines to carry out operations will be determined after the complete constraint graph is established in the following steps.

6.5 Production configuration evaluation To determine a sub-routing alternative and operations for the SA variant, the connectionist approach is applied to further refine the search space. Because other categories are void, the connectionist network is constructed with C respect to GC 4 and G6 . The initial state of the network accommodating sub-routings and operations pertaining to the SA variant is shown in Figure 11(a). The activated nodes in the initial network are arbitrarily assigned. The network is unstable because clusters with respect to variables r11 and o3 are unstable. By applying the stability checking algorithm of Tsang (1993), a stable state is achieved, as shown in Figure 11(b). It represents a solution with respect to the selection of sub-routings and operations because all activated nodes have ‘0’ input. The network can be interpreted as the selection of r11 , o1 and o2 for the SA variant. With the selection of r11 , as variables, o1 and o2 are added to the constraint graph, and the complete constraint graph is established, as shown in Figure 10(b). Subsequently, heuristics – the shortest cycle times – is applied to assign machines to operations. With slashes representing unassigned values, Figure 10(c) shows the assignment: M1 to o5 , M5 to o1 , and M2 to o2 . Finally, the cycle time of the production process with the above operations and machines is computed: XXX T?oi , rst , rt , p1 ? ? 20 ? 10 ? 12 ? 42seconds:

t s i

By considering the given allowable maximum cycle time of 45 seconds, the production process consisting of r11 (o1 =m5 and o2 =m2 ) and r21 (o5 =m1 ) is the final solution.

7. Concluding remarks This study has introduced a constraint satisfaction-based approach to production configuration, a major issue in the production of product variety. The importance of satisfying constraints lies in the fact that a large number of product variants is required to be produced quickly and at low cost. In the proposed approach, the elements involved in production configuration are identified and categorised into four domains, including the product, component, routing, and operations domains. Subsequently, constraints and the associated variables in each domain and across domains are identified. Such multi-domain constraint handling sheds light on the reasoning behind configuring production processes. This is accomplished by explicitly capturing and modelling configuration elements of different types and interactions among them. One assumption supporting this study is that there exists a common platform, based on which configuring production processes from the existing elements is carried out. In this regard, the constraints modelled do not address how to obtain the sequence

International Journal of Production Research

7165

Downloaded by [Beijing Jiaotong University] at 00:52 06 June 2014

relationships among operations. They are identified to facilitate the determination of appropriate process elements and production processes from the many alternatives. With respect to the existing work on product family development and CSP, this paper presents the following unique characteristics, contributing to the body of knowledge. First, it identifies production configuration as an effective means of planning production processes by taking advantage of the design and process similarity inherent in product families. Production configuration considers both component assemblies and component parts from a holistic perspective. In essence, it provides inputs (e.g., machines, items) to computer-aided process planning and computer-aided assembly planning so as to ensure the efficiency of these planning activities. Second, it offers a comprehensive framework (i.e. the production configuration domain model) for modelling the major decision factors and their interactions. The domain model enables seamless mappings between products, components, routings, operations and machines, thus allowing the selection of process elements and the configuration of production processes. Third, it formulates production configuration as a constraint satisfaction problem to tackle the numerous, heterogeneous constraints, and sheds light on the reasoning behind configuring production processes by satisfying these constraints. The categories of constraints identified initiate a concise and rigorous representation of the constraints, which, in turn, facilitates convenient constraint handling. Fourth, the decision propagation structure proposed for solving the CSP extends traditional constraint satisfaction techniques by incorporating heuristics in the processing of the various sets of feasible options. This capability, together with the stability checking enabled by the connectionist approach, endorses the solution framework developed as an effective procedure for deriving decisions objectively and efficiently. Some issues that are not considered in the proposed solution approach may merit further research. First, along with the increase in product complexity, the number of components and the complexity of connections among them also increase. In this regard, the formulation and solution framework may not be able to scale up well enough to handle such increased complexity. Thus, a comprehensive solution methodology incorporating nested (or composite) modelling of variables and constraints in accordance with product and process hierarchies may need to be developed. Second, the CSP solution framework is designed for finding a feasible solution instead of an optimal solution. While this is acceptable in view of the potential costs of finding an optimal solution, future work can be carried out to investigate affordable strategies to find an optimal solution. Third, different optional components assumed by different product variants may demand the inclusion of certain process elements in the final production processes to be configured. This confirms one characteristic of constraint satisfaction problems, namely the presence of certain variables may activate other variables. By taking into account such dynamics in activating and satisfying constraints, further research may formulate production configuration as a dynamic CSP and develop appropriate methods to solve it. Fourth, in regard to the assumption concerning the existence of a common platform, future research may be directed to the identification (or construction) of the sequence relationships among operations.

References

Abdi, M.R. and Labib, A.W., 2003. A design strategy for reconfigurable manufacturing systems (RMSs) using analytical hierarchical process (AHP): A case study. International Journal of Production Research, 41 (10), 2273–2299. Abdi, M.R. and Labib, A.W., 2004. Grouping and selecting products: The design key of reconfigurable manufacturing systems (RMSs). International Journal of Production Research, 42 (3), 521–546. Aldanondo, M. and Vareilles, E., 2008. Configuration for mass customization: How to extend product configuration towards requirements and process configuration. Journal of Intelligent Manufacturing, 19, 521–535. Balogun, O., Hawisa, H., and Tannock, J., 2004. Knowledge management for manufacturing: The product and process database. Journal of Manufacturing Technology Management, 15 (7), 575–584. Borenstein, D. and Becker, J.L., 2004. State space representation of manufacturing operation plans in the presence of flexible routing capability. International Journal of Computer Integrated Manufacturing, 17 (5), 451–466. do Carmo-Silva, S. and Alves, A.C., 2006. Detailed design of product oriented manufacturing systems. In: Proceedings of the 3rd international conference on group technology/cellular manufacturing. The Netherlands: Groningen, 1–10. Fohn, S.M., et al., 1995. Configuring computer systems through constraint-based modeling and interactive constraint satisfaction. Computers in Industry, 27, 3–21. Fox, M.S., Sadeh, N., and Bayken, C., 1989. Constrained heuristic search. In: Proceedings of the 11th international joint conference on artificial intelligence, 309–315. Gelle, E. and Faltings, B., 2003. Solving mixed and conditional constraint satisfaction problems. Constraints, 8 (2), 107–141.

7166

L.L. Zhang et al.

Haselbock, A., 1993. Knowledge-based configuration and advanced constraint technologies. Dissertation (PhD). Technical University of Vienna. H’Mida, F. and Vernadat, F., 2009. A constraint approach (flexible CSP) for alternative cost estimation of a mechanical product. International Journal of Production Research, 47 (2), 305–320. Jiao, J., et al., 2008. Association rule mining for product and process variety mapping. International Journal of Computer Integrated Manufacturing, 21 (2), 111–124. Jonsson, A. and Frank, J.D., 2000. A framework for dynamic constraint reasoning using procedural constraints. In: Proceedings of the 14th European conference on artificial intelligence, Berlin, 93–97. Kumar, D., Chen, W., and Simpson, T.W., 2009. A market-driven approach to product family design. International Journal of Production Research, 47 (1), 71–104. Mittal, S. and Falkenhainer, B., 1990. Dynamic constraint satisfaction problems. In: Proceedings of the 8th national conference on artificial intelligence, MIT, 25–32. Mittal, S. and Frayman, F., 1989. Towards a generic model of configuration tasks. In: Proceedings of the 11th IJCAI. Morgan Kaufmann, 1395–1401. Sabin, M., 2003. Towards more efficient solution of conditional constraint satisfaction problems. Dissertation (PhD). University of New Hampshire. Sabin, D. and Freuder, E., 1996. Configuration as composite constraint satisfaction. In: Proceedings of the artificial intelligence and manufacturing research planning workshop, 153–161. Sabin, M. and Freuder, E., 1998. Detecting and resolving inconsistency and redundancy in conditional constraint satisfaction problems. In: Proceedings of the CP-98 workshop on constraint problem reformulation, 26–30 October (1998), Pisa, Italy, 1–6. Sathi, N., et al., 1992. Resource configuration and allocation: A case study of constrained heuristic search. IEEE Expert, 7 (2), 26–35. Schierholt, K., 2001. Process configuration: Combining the principles of product configuration and process planning. Artificial Intelligence for Engineering Design, Analysis and Manufacturing, 15, 411–424. Stumptner, M. and Haselbock, A., 1993. A generative constraint formalism for configuration problems. In: Proceedings of the 3rd congress of the Italian Association for Artificial Intelligence on advances in artificial intelligence, 302–313. Stumptner, M., Haselbock, A., and Friedrich, G., 1994. Cocos: A tool for constraint-based, dynamic configuration. In: Proceedings of the 10th CAIA, San Antonio. Tielemans, P.F.J., 1996. Lead time performance in manufacturing systems. Dissertation (PhD). Rotterdam School of Management. Tsang, E., 1993. Foundations of constraint satisfaction. London: Academic Press. Tsang, E., 1999. A glimpse of constraint satisfaction. Artificial Intelligence Review, 13, 215–227. Turner, E.H. and Turner, R.M., 1999. Constraint-based approach to assigning system components to tasks. Applied Intelligence, 10 (2/3), 155–172. Wortmann, J.C., Muntslag, D.R., and Timmermans, P.J.M., 1997. Customer-driven manufacturing. London: Chapman and Hall. Xie, H., Henderson, P., and Kernahan, M., 2005. Modeling and solving engineering product configuration problems by constraint satisfaction. International Journal of Production Research, 43 (15), 4455–4469. Ye, X., et al., 2009. Using product family evaluation graphs in product family design. International Journal of Production Research, 47 (13), 3559–3585. Youssef, A.M.A. and EIMaraghy, H.A., 2006. Modelling and optimization of multiple-aspect RMS configurations. International Journal of Production Research, 44 (22), 4929–4958. Zhang, L., 2007. Process platform-based production configuration for mass customization. Singapore: Dissertation (PhD). Nanyang Technological University. Zhang, L., Jiao, J., and Helo, P., 2007. Process platform representation based on unified modeling language. International Journal of Production Research, 45, 323–350. Zhang, L. and Rodrigues, B., 2010. Nested colored timed Petri nets for production configuration of product families. International Journal of Production Research, 48 (6), 1805–1833. Zhao, X.B., Wang, J.C., and Luo, Z.B., 2000a. A stochastic model of a reconfigurable manufacturing system, Part 1: A framework. International Journal of Production Research, 38 (10), 2273–2258. Zhao, X.B., Wang, J.C., and Luo, Z.B., 2000b. A stochastic model of a reconfigurable manufacturing system, Part 2: Optimal configurations. International Journal of Production Research, 38 (12), 2829–2842. Zheng, L.Y., et al., 2008. Systematic modeling and reusing of process knowledge for rapid process configuration. Robotics and Computer-Integrated Manufacturing, 24, 763–772.

Downloaded by [Beijing Jiaotong University] at 00:52 06 June 2014

相关文章:

- ...Constraint-based Product Configuration Knowledge....pdf
*with*IT-supported*configuration*for consumer ...*Constraint**satisfaction*problem (CSP) was first ...*domain*and*constraints*in*constraint*-*based**configuration*...

- 基于约束满足和贝叶斯网络的大规模定制产品配置方法.pdf
- (2015)07 - 1005 - 07 Mass Customized
*Product**Configuration*Method*Based*on*Constraint**Satisfaction*Problem and Bayesian Networks ( College of Information ...

- 基于非二元约束满足的配置问题求解方法.pdf
*Based*on Nonbinary*ConstraintSatisfactionS*HANMi-yuan,YUANJi-jun(Management...solvingmethodin accordance*with*the ofthe*configuration*problem. [KeywordsImass...

- Experience based configuration.pdf
- Experience
*based**configuration*_专业资料。This paper aims at presenting a way to integrate Case*Based*Reasoning and*Constraint**Satisfaction*techniques in order ...

- GDSS FOR RE-ENGINEERING OF PRODUCTION SYSTEMS.pdf
*configuration*and layout design of the*production*...Conventionally,*constraint**satisfaction*is applied to...*Constraint*-*based*model for problem*domain*knowledge...

- ...Constraint satisfaction problems - 2016_图文.pdf
- 人工智能:一种现代方法ch06
*Constraint**satisfaction*...For i = 1 : n, assign Xi consistently*with*...*Domain*= {1, 2, 3 … , n} for position ...

- Constraint Satisfaction with Preferences.pdf
*Constraint**Satisfaction**with*Preferences - First works on*constraint**satisfaction*problems (CSP) ...

- CONFIGURATION DESIGN AS CONSTRAINT SATISFACTION.pdf
*CONFIGURATION*DESIGN AS*CONSTRAINT**SATISFACTION*- paralic @ ccsun. tuke. sk...*Constraint**Satisfaction*Algorithms*with*respect to*Configuration*Logic t Programmi...

- Constraint satisfaction.pdf
- variables, each associated
*with*a*domain*of values, and a set of ...Pearl. Network-*based*heuristics for*constraint**satisfaction*problems. Arti cial...

- 基于约束规划的一类排序问题通用求解方法_图文.pdf
*productionconstraints*.*Based*asa ona the*constraint*...*constraintsatisfaction*problem.Arefactoringmodeland gen...separately.*With*cial*domain*isestablished.Accordingto...

- Constraint-Based Agents.pdf
*with*Dynamic*Constraint**Satisfaction*,*Constraint**Satisfaction*Optimization, and ...*domain*of the interval approach is the*constraint*-*based*scheduling, see e....

- Implicit random constraint satisfaction problems.pdf
- Implicit random
*constraint**satisfaction*problems_专业...tuples of a -ary*constraint**with*per*domain*. Hence...Also, a vast majority of experiments*based*on ...

- Books Constraint Satisfaction in Logic Programming.pdf
*Domain*-independent extensions to GSAT: Solving ...Semiring-*based**Constraint**Satisfaction*and ...*Constraint**Satisfaction**with*Preferences H. Rudová,...

- Iterative focusing for finding faults in.pdf
- bases in the
*domain*of*product**configuration*. We...*based*on*Constraint**Satisfaction*, have shown to be...In cases where the configurator*with*an updated ...

- A constraint-satisfaction approach for 3D visiontou....pdf
- A
*constraint*-*satisfaction*approach for 3D visiontouch-*based*object recognition_...each model object in turn, the*domain*of the tactile nodes is S m , ...

- Constraint Satisfaction for Case Adaptation.pdf
- In COMPOSER, the case-
*based*reasoner was augmented*with*CSP techniques in ...cient case adaptation framework for the*domain*of*constraint**satisfaction*...

- Solving Methods for Conditional Constraint Satisfaction.pdf
- Methods for Conditional
*Constraint**Satisfaction*_专业...Typical real world tasks such as*configuration*or...has 5 variables*with*a maximum*domain*size of ...

- An Agent-Based System Framework for Mine Scheduling....pdf
*configuration*approach that integrates a multi-agent...*constraint**satisfaction*problem formalism, simulated ...(2001). Agent*based*scheduling in*production*...

- ENCODE PROJECT- ENVIORNMENT FOR CONFIGURATION DESIGN.pdf
- ( Keywords: knowledge-
*based*system,*configuration*...complexthetaskneedsalargeamountof*domain*specific ...Using the CSE*constraint**satisfaction*problems be ...

- problems as Constraint Satisfaction Problems the en....pdf
- problems as
*Constraint**Satisfaction*Problems the ...*domain*in which you have as the initial state ...The common approach for CP-*based*planners is to...

更多相关标签:

- Interactive configuration using constraint satisfaction techniques
- Domain Transmutation in Constraint Satisfaction Problems
- Numerical Constraint Satisfaction Problems with Non-isolated Solutions
- 蛋白域之间作用的预测Predicting domain-domain interaction based on domain profiles with feature
- Dynamics of ferromagnetic nanomagnets with vortex or single-domain configuration
- Backjump-based Backtracking for Constraint Satisfaction Problems
- Finite Domain Relaxation and Tractable Constraint Satisfaction Problems.
- Plane-based Calibration of a Camera with Varying Focal Length the Centre Line Constraint
- Constraint satisfaction problems with infinite templates
- Constraint Satisfaction with Countable Homogeneous Templates