Application of knowledge-based artificial immune system (KBAIS) for computer aided process planning in CIM context

In the present era, several manufacturing philosophies like lean manufacturing, total quality management (TQM), etc., have the goal of providing a quality product at reduced cost. In this research paper the process planning problem of a CIM system has been discussed where minimisation of cost of the finished product is considered as the main objective. For determining the cost of the finished product, scrap cost, forgotten by most of the previous researchers, has been considered along with other costs like raw material cost, processing cost, etc. In the present environment of concurrent engineering, optimisation of process planning is an NP-hard problem. To solve this complex problem a noble search algorithm, known as knowledge-based artificial immune system (KBAIS) has been proposed. The nobility of the proposed algorithm is that the inherent capability of AIS has been gleaned and incorporated with the property of the knowledge base. In this problem, the power of knowledge has been used for three stages in the algorithm: initialisation, selection and hyper-mutation. To demonstrate the efficacy of the proposed KBAIS, a bench mark problem has been considered. Intensive computational experiments have also been performed on randomly generated datasets to reveal the supremacy of the proposed algorithm over other existing heuristics.

Keywords: CAPP; flexible manufacturing system; artificial immune system; KBAIS

In the present era of globalisation, the competitiveness of any manufacturing industry is determined by its flexibility, customer satisfaction and product varieties, while the production cost is the predominant factor affecting the manufacturers' perception. Therefore, manufacturers have to meet the aforementioned market requirements and customers at lower prices since failure to do so might result in a considerable loss of goodwill and eventually market share. This is done mainly through the use of automation, new technologies and new manufacturing concepts. Among all the systems, computer integrated manufacturing (CIM) is one that permits the manufacturing firms to operate under high quality production requirements. It is necessary for the manufacturing industry to provide good quality products at consistently low production cost, in order to increase their market share. The main and attractive feature of any CIM system is that it has several resources with different capacities, capabilities and facilities. Although CIM comprises various resources and efficient mechanisms, its smooth and economic functioning is not guaranteed because it has some critical decision making issues, such as allocation of resources, planning, scheduling, etc. Process planning is one of the most intricate decision-making problems. Due to its crucial and deep impact on the process capability and quality, it needs to be addressed thoroughly. Bearing in mind the above aspects, in this article, the significance of process plan selection is chosen for analysis in a CIM environment.

Process planning is used for selecting the appropriate routeing in a manufacturing process of parts that are needed in order to transform raw materials into the finished product. In other words, it refers to the set of instructions that is exercised to make the parts meet the design specifications. Process planning works as a bridge between design and the manufacturing process. It plays a vital and crucial role in the design-to-manufacturing chain of processes. Therefore, it is essential to develop a process plan that has adequate knowledge of both upstream (design) and downstream (manufacturing) processes. In the present manufacturing era, various machines, tools, etc., are available to manufacture any product. Therefore, there may be different processing routes consisting of several alternative machines, tools, fixtures, etc., for the manufacturing of part types. In addition, the requirement of production volume and cost of processing have a decisive role in the selection of a process plan.

In most of the prominent researches, a process plan has been optimised according to two criteria: cost of manufacturing and mean flow time. Some researchers like Palmer ([26]) and Husbands and Mill ([13]) have worked on the time aspects of alternative machines and tools during the optimisation process. Others, like Zhang et al. ([35]) and Ma et al. ([16]), have worked on cost optimisation, because cost is a major determinant of profitability of the product. Most of the researchers have concentrated only on minimisation of processing cost and processing time of the part type but they have not taken into account scrap/rejection cost. However, in the real shop floor environment rejections at each machine are generally taken as a guideline for developing a new process plan. Therefore, by considering the scrap factor, this paper attempts to put forward a more realistic insight into the computer-aided process planning (CAPP) problem. CAPP originated in the 1960s (Niebel [21]) to reduce lead time and manufacturing cost. In the following decades, it has been categorised into two different approaches: variant type and generative type. The variant type process plan is engaged with recalling, identification of part type (based on product design) and retrieving of an existing plan for a similar part and modifying it according to the new part type; whereas in the generative type, a process plan is generated by means of decision logics, formulas, technology, algorithms and geometry-based data. It has gained significant attention in recent times because it provides a competitive edge to manufacturers by incorporating new changes in a planning system and making it responsive to the changes in product design, introduction of new products, changes in resource capabilities, etc. Roh and Lee ([28]) have explored 3D CAD modelling in ship building and on the basis of that they provide the process plan. Ciurana et al. ([4]) have applied computer-aided process planning in the sheet metal industry.

While scrutinising the literature dealing with CAPP issues, it can be easily revealed that there exist a plethora of studies concerned with CAPP problems. In the present scenario, the generative CAPP is admired because of its responsiveness to the rapid changes in product varieties and its design. To optimise the processing cost in a process planning problem, genetic algorithms (GA) have been explored by Zhang et al. ([35]), Li et al. ([15]) and Salehi and Moghaddam ([29]). The solution, generated by these approaches, consists of various decision-making problem and precedence relationship among the operations. Ben-Arieh and Chopra ([2]) have modelled a process plan selection problem on the basis of a case-based reasoning approach. A graph theoretical approach with minimum cost constraints, for minimisation of number of tools and auxiliary devices, has been proposed by Kusiak and Finke ([14]). In this approach, all the formulations and computational work have been done with the help of integer programming which needs to prohibit computational time to arrive at a near optimal solution. Nassehi et al. ([20]) have proposed an agent-based technique to solve the computer-aided process planning. Xu and Li ([34]) have modelled the parameter selection first then they have proposed a mathematical logical model for process planning.

In the manufacturing environment most information is imprecise and vague. Because of this, Tiwari and Vidyarthi ([32]) and Rai et al. ([27]) have applied the fuzzy-based model to select a process plan considering machining time and cost, processing sequence, setup, etc. To incorporate the various similarities like machine similarity, operation sequence similarity, in the given approach, first, the alternative process plans are generated then some are consolidated. A neural network-based approach for set up planning has been exercised by Ming and Mak ([17]), whereas Ming and Mak ([18]) used a Hopfield neural network with a genetic approach for an optimal process plan selection problem. Ben-Arieh et al. ([3]) have used a generalised travelling salesman problem (TSP) to select the process plan for a rotational part considering the tolerance analysis.

From the aforementioned literature review, it is observed that many of the researchers reported that the process planning problem consists of several decision-making problems such as appropriate machine selection, tool selection, and selection of tool approach direction (TAD). It is a well known computational complex problem (Morad and Zalzala [19]) and warrants the application of random search technique. From the contribution of past researches, it can be acknowledged that artificial immune system has not been explored as random search techniques for solving such combinatorial problems in a flexible environment. Keeping in mind, here the application of AIS has been explored for CAPP problem in FMS. Simultaneously, very few researchers have been taking care of the improvement of the algorithm.

In the present paper, a new paradigm of application of AIS for system performance improvement and the performance improvement of AIS using the strength of knowledge has been explored. The KBAIS has been applied in the CAPP problem of FMS to enhance the system performance and algorithm concurrently. The proposed algorithm has been tested on the benchmark problem from the literature. The KBAIS has also been tested on the moderate size of the problem to show the efficacy over the classical AIS problem. The computational results show the effectiveness of the proposed algorithm.

The remainder of the paper is arranged in the following sequence: Section 2 delineates about the problem environment whereas mathematical modelling of the problem has been shown in Section 3. Section 4 describes the background of classical AIS. The background of knowledge management has been described in Section 5. The proposed algorithm has been discussed in Section 6. Section 7 reveals the procedure of KBAIS for CAPP problem. To demonstrate the efficacy of the proposed heuristic, an illustrative example, adopted from literature along with randomly generated data sets have been explained in Section 8. To validate the performance of the proposed algorithm results and discussions are presented in Section 9. Finally, the summary and conclusions with a note about its future scope is reported in Section 10.

In CIMS, several resources persist with different capabilities, capacities and functions. The selection of appropriate resources such as machines, cutting tools, fixture, TAD etc, are the fundamental elements of a process planning problem. The process plan has generally been tackled using one of two approaches. The first approach seeks a solution that minimises the total manufacturing cost. The second approach tackles the problem by minimising the total manufacturing time. In this article, finished product cost has been considered as criterion. Most of the earlier researchers have considered only machining cost, tooling cost, machine changing cost, tool changing cost, and set up changing cost but forgotten about the scrap or rejection cost. The raw material will undergo several machining processes and each process it undergoes will be subjected to certain design requirements. The parts that do not meet the design specification or the parts below and above the tolerance limit will be rejected and known as scrap. For example, in the manufacturing of a part, the process involves several operations that can be performed in alternative machines. Each process like milling, drilling etc. is subjected to certain design specifications. After inspection, if some parts do not meet the tolerance limit, then the same is rejected as shown in Figure 1.

Graph: Figure 1. Transformation process of a part from raw material to finished product.

To ease the solution strategy undertaken, the CAPP problem is modelled as the travelling salesman problem (TSP) with precedence relationship. In this model travelling distance between the two nodes corresponds to operation cost between the operations. The travelling sales man problem is also a combinatorial optimisation problem or NP hard problem and this problem is also an NP hard problem. As the TSP, here operations are considered as nodes or cities visited. Any of the operations will not be repeated as in TSP no city or node visited twice. Therefore it can be said that this problem can be modelled as TSP. Selection of machines and tools for each operation is not trivial due to the availability of alternative machines, tools, fixtures and TAD and these are selected on the basis of their operation cost. Tool approach direction (TAD) is the set-up of fixture and tooling, i.e. in which direction the tool will cut the material. There are six possible directions of tool cutting: +X, −X, +Y, −Y, +Z and −Z. Therefore, according to TAD, the setup will be changed which will affect or increase the overall processing cost. In order to minimise the overall processing cost, TAD should be minimised. The mathematical model of process planning problem is described in the following section.

The cost of the finished product is associated with the processing cost of each operation, raw material cost and scrap cost. The processing cost is the primary concern and includes machining cost, tooling cost, machine changing cost, tool changing cost and set-up changing cost. At this stage, any detailed information about tool paths and machine parameters is not available, therefore, only operation type and their sequences are determined. The mathematical formulations of aforementioned costs are given below in more detail.

• i. _B__I_Machining cost (MC)_i_

To perform the operations, the cost of required machining is known as machining cost. It is mathematically defined as:

Graph

where MCIi is the machining cost index of machine i and n is the total number of operations.

• i. _B__I_Tooling cost (TC)_i_

Tooling cost is the cost of tools required to perform all the machining operations. The mathematical formulation is as follows:

Graph

where TCIi is the tooling cost index of tool i.

• i. _B__I_Machine changing cost (MCC)_i_

The cost of changing of machines between two operations is known as machine changing cost. Machine change cost between machine Mi and Mi+1 is mathematically defined as:

Graph

when

Graph

where MCCI is the machine changing cost index.

• i. _B__I_Tool changing cost (TCC)_i_

The cost of the changing of tools between two operations on the same machine is known as tool changing cost. Tool change cost between tool Ti and Ti+1 is defined as follows:

Graph

when

Graph

where TCCI is the tool changing cost index.

• i. _B__I_Set-up changing cost (SCC)_i_

This cost is taken in account when two operations are performed on the same machine but having the different tool approach direction (TAD). TAD change cost between TADi and TADi+1 is mathematically defined as:

Graph

where

Graph

The overall processing cost is the sum of all the aforementioned costs and it is defined as:

Graph

It is the main objective of this paper. This cost is associated with overall processing cost, scrap cost and raw material cost. For calculating the output cost, other factors like the scrap fraction, input coefficient, scrap coefficients etc. should be taken into account. The calculation of these factors along with the objective function is given below.

It is the ratio between the number of rejected units and number of input units at each operation. It is given as follows:

Graph

where

• scrap fraction at i th operation;
• number of part rejected at i th operation;
• number of input units of i th operation.

It is a technological coefficient and represents the requirement of input per unit of output. It can be expressed as follows:

Graph

where = input coefficient of ith operation.

It is the ratio of generated scrap and number of output unit. It is defined as:

Graph

where

• number of output units of i th operation;
• scrap coefficient of i th operation.

For any production system, the total number of inputs are not converted as the output, as some are rejected as scrap due to some variability on the machines. The cost of the output is the sum of raw material cost and the cost incurred during the processing (overall processing cost). If some parts are rejected, the cost occurred on the processing of those parts should also be considered for balancing the currency flow. So as per the material flow for ith operation, it can be stated as:

Graph

If all the aforementioned costs are changed in the currency flow system, the cost flow balance equation will be as follows:

Graph

where

• average input cost per unit for operation i
• average output cost per unit for operation i
• average scrap cost per unit for operation i
• operation cost per unit for operation i

This formula can be written as

Graph

And the overall objective function will be:

Graph

The main objective of this paper is to minimise the value of function F.

The next section delineates the background of the population-based algorithm which is known as an artificial immune system.

The immune system of a living creature is a very complex system like the brain and its mechanism is remarkable not only from a biological point of view but also for complicated computation perceptions. An artificial immune system (AIS) is an adaptive system, provoked by the theoretical immunology, observed immune functions, principles and models and it is now widely used to unravel the various complexities in current engineering paradigms. From the literature review, it is comprehended that various researchers have been allured towards the implementation of AIS. Some of the researchers like DeCastro and VonZuben (2002), Cutello and Nicosia ([5]), Cutello et al. ([6]), DeCastro and Timmis (2002), De-Castro and VonZuben (2001), etc., have successfully implemented the concept of AIS for solving various complicated engineering and optimisation problems. However, in the present article AIS is employed for a multi-objective function to determine the total transportation cost and transportation time.

An immune system has different varieties of organs and cells and the whole mechanism is not directed by a single organ alone, but all the organs and cells perform various activities in a complementary manner. The key role of an immune system is to identify the harmful and disease causing cells and in this way it protects the body from external living creatures. All the cells which are thus recognised by the immune system are known as antigens. The harmless antigens are known as self antigens whereas disease causing or harmful antigens are called non-self antigens. The process of recognition for self/non-self antigens is known as self/non-self discrimination. The immune system has two main groups of cells: B-cells and T-cells. The most alluring feature of an immune system is the presence of receptor molecules on the surface of B-cells, known as antibodies (Ab) which have the capability to recognise the antigens. The antigens are covered with some molecules known as epitopes. These epitopes allow them to be recognised by antibodies. An AIS is encouraged by the capability of the immune system of recognition and elimination of antigens.

Some decisive factors like affinity, binding and affinity threshold direct the antigenic recognition. Any receptor molecule or antibody recognises the antigens on the basis of their certain affinity values. The activation condition of the immune system is that the affinity value should be greater than a threshold value known as affinity threshold. Another factor, binding, takes place between the antigen and antibody. Binding is proportional to the affinity value, i.e. if the affinity value is higher, the binding will be strengthened otherwise weakened.

On encountering the non-self antigen by B-cell receptor molecules, the mechanism of the immune response system can be explained by clonal selection theory. According to this theory, B-cell, which encounters the non-self antigen, is selected for proliferation and affinity maturation process to produce a high volume of antibodies. The proliferation process is a mitotic process, i.e. the cells divide themselves without any crossover occurring among them. For the reproduction process, the proliferated cells are hyper mutated under a selective pressure. After the hyper mutation process, B-cell presents the higher affinities with selective antigens. The whole process of hyper mutation and selection is called the maturation of immune response.

From the standpoint of computation in an AIS, some salient features of clonal selection theory should be discussed. Several antibodies are selected to proliferate by an antigen. The proliferation rate is proportional to the affinity value while hyper mutation rate is inversely proportional to the affinity value. It represents a sense of balance between searching and exploiting. The whole process of proliferation, hyper mutation and selection process is depicted in Figure 1.

The whole process can be summarised in the following steps:

• 1. Random populations of individuals are initialised.
• 2. For each individual of current population, the affinity value is estimated.
• 3. A predetermined number of individuals are selected on the basis of their affinity values.
• 4. These selected individuals are proliferated according to their proliferation rate which is proportional to the affinity value.
• 5. The proliferated antibodies are undergoing a hyper mutation process whose rate is inversely proportional to the affinities of their respective antigens.
• 6. The proliferated and mutated solutions are added into the initial population and the best solution is added to the memory for quick recall later.
• 7. Step 1 to step 5 will be repeated until the termination criterion is satisfied.

As Francis Bacon said: 'Knowledge is power.' To learn new things, maintain valuable heritage, create core competences, and initiate new situations, the power of knowledge is a very important resource for both individual and organisations now and in the future. According to Nonaka ([23]), knowledge has been defined as 'justified true belief' that increases an organisation's capacity for effective action. It has two dimensions: explicit and tacit knowledge. Davenport and Prusak ([8]) define knowledge as a fluid mix of framed experience, values, contextual information, and expert insight that provides a framework for evaluating and incorporating new experiences and information. They suggest that it originates and is applied only in the mind of knower and holders of tacit knowledge in organisations. It is embodied in documents, repositories, organisational routines, processes, practices and norms. To respond to competitive challenges, otherwise-independent firms have become more closely coupled than in the past, often working in parallel to complete assignments spanning traditional boundaries and functional areas. Knowledge management (KM) provides processes to capture a part of tactic knowledge through informal methods and pointers and a fairly high percentage of explicit knowledge, reducing the loss of organisational knowledge (Nonaka and Takeuchi [24]).

KM is the formalization of and access to experience, knowledge and expertise that create new capabilities, enable superior performance, encourage innovation and enhance customer value.

(Beckman [1])

According to Tiwana ([30]), KM is the ability to create and retain greater value from core business competencies. Beckman ([1]) realises that knowledge management is the systematic, explicit and deliberate building, renewal and application of knowledge to maximise an enterprise's knowledge-related effectiveness and returns from its knowledge assets knowledge management is the formalisation of and access to experience, knowledge, and expertise that create new capabilities, enable superior performance, encourage innovation, and enhance customer value. Whereas Tiwana and Balasubramanyam ([31]) feel that knowledge management addresses business problems particular to business – whether it's creating and delivering innovative products or services or managing and enhancing relationships with existing and new customers, partners and suppliers, or administrating and improving work practices and processes. Nietok ([22]) examines that knowledge has a connotation of 'potential for action' and is different from information in terms of its more immediate link with performance. It is linked to the values and experience of the user, and therefore takes many forms. One may have knowledge of certain facts. A KM strategy can help tear down traditional cross functional boundaries. KM entails helping people share and put knowledge into action by creating access, context, infrastructure, and simultaneously reducing learning cycles (Davenport et al. [7], Davenport and Prusak [8], O'Dell and Grayson 1998).

In the present paper, the knowledge-based tool is motivated by the ideas proposed by Wadhwa and Saxena (2006). The creation of today's knowledge base requires blending of knowledge from diverse disciplinary and personal skills based on perspectives where creative cooperation is critical for innovation (Handfield and Nichols [12]). An integrated framework of KM has been shown in the Figure 2. It shows the conversion of information to knowledge and integration of knowledge base with knowledge utilisation. To convert the information to knowledge, the process follows the various activities as verification, acquiring the filtered information, classification and creation of the knowledge from this information. All the acquired knowledge is stored in the knowledge base. After accumulation, the knowledge has been distributed to the knowledge users by following the steps like adaptation, attraction, engaging the people and teaches them how to use this knowledge. The knowledge synergy-based thinking shown in Figure 3 can significantly benefit the KM guided manufacturing endeavours.

Graph: Figure 2. Clonal selection, expansion (proliferation) and affinity maturation.

Graph: Figure 3. An integrated framework of knowledge management.

To tackle the limitations of classical AIS, a concept for improving the performance of algorithm has been introduced by exercising the knowledge-based system by using the tacit and explicit knowledge and it will develop a faster algorithm for better performance of the system. By employing the knowledge of the environment like FMS and the complexities, i.e. flexibilities, we can get a better result in less time than AIS. As it works with the knowledge base, it is identified as KBAIS. The proposed algorithm works not only for improving the performance measures of the system like traditional genetic algorithm but the performance of the algorithm. The generic working procedure of the proposed algorithm has been illustrated in Figure 4. For successfull implementation of the knowledge, the knowledge-based initialisation, knowledge-based proliferation, knowledge-based hyper-mutation, and knowledge-based selection have also been incorporated in the algorithm. The proposed algorithm works not only for improving the performance measures of the system like traditional genetic algorithm but the performance of the algorithm. To enhance this idea, the knowledge-based initialisation, knowledge-based crossover, knowledge-based mutation and knowledge-based selection have also been incorporated in the algorithm. The procedure of the algorithm has been described in the next section.

Graph: Figure 4. Flowchart of KBAIS.

As stated earlier, the various steps of KBAIS will be discussed in this section. The first and important step of the algorithm is knowledge-based initialisation and it is followed by the knowledge-based selection (KBS), and knowledge-based hyper-mutation (KBHm) to provide the wider search space in less time. The procedure has been described in the context of process planning in FMS which is one of the flexible systems that has been taken into consideration for this research. All the steps of the proposed algorithm (KBAIS) are as follows:

It is the first step of the algorithm. During the initialisation process, the form of antibodies or the individuals of solutions are defined. In this algorithm these antibodies have been generated with the help of the knowledge base. Initially, the information associated with the system component like information about machines, part geometry, features, operations, tools, tool approach directions and various routes have been collected and sorted out according to our objective or performance measure.

To initialise the problem, we use the tacit knowledge and take the knowledge from the human being or planning manager to provide the process plan which works the best. These process plans will be analysed and the results reviewed. If it will work better, these process plans will be the initial population of the algorithm and these are also used to enrich the knowledge base. The working procedure of this step has been demonstrated in Figure 5.

Graph: Figure 5. Initialisation process of KBAIS.

The affinity should be evaluated during this step. The affinity value has been evaluated for each antibody generated. The affinity is the objective of the problem. The value of affinity is changed according to the optimisation. The affinity can be expressed in mathematical form as follows:

Graph

The proliferation is known as the cloning of antibodies. It works according to its affinity values. The antibodies are selected randomly on the basis of their affinities. The selection probability of that antibody, which has a high affinity score, will be greater. In other words, the antibody with more affinity will be more proliferated and vice versa, i.e. the proliferation rate is proportional to affinity with their antigen. The number of proliferated solutions should be pre-determined.

After the proliferation process, the antibodies will go under the hyper-mutation process. In this process the new off-spring are generated from one antibody and it is not a bi-sexual operation. In the proposed algorithm, a knowledge base has been created to store the knowledge about the performance of various hyper-mutation operators in the different system environments with a variety of objective functions. The hyper-mutation rate also depends on the affinity values. It also has the knowledge about the outcomes with the different range of the hyper-mutation probability. Hence, knowledge (explicit or implicit) can help to determine the value of probability. The KBHm has been illustrated in Figure 6.

Graph: Figure 6. Knowledge-based hyper-mutation.

The proliferated and mutated population will be added to the initial population. In the whole population, the same number of individuals as the initial population will be selected for the next generation. In the knowledge base system, all types of selection schemes with their characteristics and their performance in different systems have been placed. The knowledge base has been developed by the extensive literature review. For example, the roulette wheel selection is the most used by the researchers in the process planning problems. Whereas the scale section schemes are simpler and takes less time, the performance of the roulette wheel selection scheme is better than a natural scale selection scheme. In the same way, all the features of other selection schemes have been put in the knowledge base which helps the user to select the appropriate selection scheme. According to this knowledge, the suitable selection scheme has been applied for the selection of a subset of the proliferated and hyper-mutated population, which will be the same as the number of the initial population, for the next stage of the algorithm. The procedure has been shown in Figure 7.

Graph: Figure 7. Knowledge-based selection.

It is an important function in this algorithm. For termination, two types of criteria are used. In the first criteria optimality remains unchanged for defaulted generations and in the second criteria the process will terminate after reaching the maximum number of generations. Repeat steps 7.1 to 7.5 until all the antibodies are the same or the optimal/near-optimal value is found.

To exhibit the efficacy and robustness of the proposed model and investigate the capability of KBAIS, dataset with increasing complexity have been considered as the benchmark. These test problems are outlined as follows.

The first case study maps the scenario described by Zhang et al. ([35]) and has been considered with an intention to reveal the efficacy of the proposed algorithm. In this case, the manufacturing unit produces a multi feature prismatic part having 19 design features. Here, eight different types of tools are assigned to three different types of machines and three types of TAD are taken into account. Each machine and tool has a different processing cost. The information related to the operations, machines, tools, and TAD and precedence relations between different operations are given in Zhang et al. ([35]).

In this case, the dataset incorporating the feature of the proposed model (process plan selection problem considering scrap cost) has been generated randomly. The case study consists of a part having 15 different operations. The precedence relation between the operations, due to different technological rules such as filterability, tolerance factor, operation stages requirement, for machining is listed in Table 1. All these operations are performed on the four different machines. The available machines are CNC lathe (M-01), CNC milling (M-02), drilling machine (M-03) and a boring machine (M-04). Nine different tools can be engaged on these machines for performing all the operations. The available tools (T1, T2, T3, ... , T9) are turning tool, milling cutter, drills, reamers, etc. For each operation, the percentage of generated scrap is fixed at each machine. The information related to the scrap, operations, machines, tools, and TAD is shown in Table 2. The cost indices such as machine and tool cost index are listed in Tables 3 and 4. The other cost index of machine (MCCI), tool (TCCI), setup (SCCI) changes is shown in Table 5. The raw material cost, scrap cost and the number of input units for this case study have been represented in Table 6.

Table 1. Precedence relationship among the different operations for case study II.

Table 2. Available resources for the different machining operation for case study II.

Table 3. Machining cost index (for case study II).

Table 4. Tooling cost index (for case study II).

Table 5. Changing cost index (for case study II).

Table 6. Some other parameters (for case study II).

To demonstrate the strength of the proposed approach, 10 process plan selection problems with increased complexity have been considered. The dataset for each problem is generated randomly to reproduce arbitrarily complex scenarios. Detailed description of the test problems such as: number of features, number of machines, number of tools, number of operations, are given.

In past literature, a lot of decision-making problems in FMS such as scheduling, planning, etc., have been addressed. To solve such types of NP-hard problems, various heuristics have been used as a powerful tool but the main endeavour is to minimise the number of generations to obtain the near optimal or sub-optimal results. Thus, it is essential to develop a type of algorithm which can decipher the large sized combinatorial problem within very few numbers of generations by utilising less CPU time. In the AIS, there is no interaction or controlling by the human being during the processing of the algorithm or in other words, human knowledge cannot be used to improve the performance of the system as well as algorithm. To consider all of the above, a new algorithm has been proposed known as knowledge-based artificial immune system (KBAIS).

The proposed KBAIS used the knowledge-based initialisation, selection, hyper-mutation instead of randomisation. This provides a better initial solution seed rather than any random solution. Thus it can converge at a faster rate than the simple AIS. Some other knowledge-based operators are also used to minimise the computational hurdles to achieve the sub-optimal results within a few generations.

KBAIS achieves the optimal/near optimal solutions for the objective considered in a process planning problem and emphasises it as a powerful meta-heuristic algorithm. Performance of the proposed KBAIS algorithm is found to be superior in comparison with AIS, considering a well known dataset adopted from literature. From extensive computational experiments it is found that for the first case study (mentioned in Section 8) results obtained by the proposed algorithm is an optimal one and is in tune with the result obtained by Zhang et al. ([35]). Table 7 represents the results obtained from AIS while the results obtained from KBAIS have been represented in Table 8. It is evident from the results that the proposed approach can perform efficiently on a process plan selection problem. The other alluring property of the proposed heuristic is that it can find the best process plan with reduced cost and other alternative solutions with a fewer number of iterations. Alternative process plans are very important because if any machine or tool breaks down, an alternative process plan without that machine or tool can be efficiently used. The comparative study has also been done between KBAIS and AIS. The comparison criterion is the number of generations in which both are converged to near optimal result. This study shows that KBAIS provides the better result within a fewer number of generations. The computational time is also another dimension of the comparison of the efficiency of the algorithms. The computational time for KBAIS is 0.97 seconds whereas the computational time for AIS is 1.36 seconds. Therefore, this study also proves the efficacy of KBAIS over the classical AIS. The comparative study has been illustrated in the graph which is shown in Figure 8.

Graph: Figure 8. Comparison of KBAIS and AIS on the convergence rate for case study I.

Table 7. Process plan obtained from AIS for case study I.

Table 8. Process plan obtained by the KBAIS for case study I.

Case study II is more complex as it is applicable with scrap value. The lower bound value for this case is 6284.26. After executing all the steps of KBAIS as stated in Section 7 the cost of the finished product is found to be 2103.78 in 43 numbers of iterations. The computational time for such a complex problem is only 1.15 seconds. The final operation sequences with selected machine, tool, TAD, and scrap are shown in Table 9.

Table 9. Process plan obtained by proposed heuristic KBAIS for case study II.

The performance of AIS is also experienced for the same dataset and the cost obtained by AIS is 2457.20 and its process plan is represented in Table 10. The number of iterations which it required is 127. The computational time taken by AIS for this case study is 1.89 seconds.

Table 10. Process plan obtained by AIS for case study II.

A comprehensive analysis of the proposed approach, both in terms of objective function and their convergence trend for this case study has been carried out and are delineated in the following subsections. The performances of the KBAIS are finally compared with those obtained by the AIS. Figure 9 compares the evolution of the best solutions of the proposed algorithm with classical AIS. From this comparison, it is evident that the performance of classical AIS is not very fine. According to the computational time, other dimensions of comparison, KBAIS works better than AIS. However, it is also marked that the proposed algorithm is significantly faster in reaching satisfactory solutions.

Graph: Figure 9. Comparison of KBAIS and AIS on the convergence rate for case study II.

To show the robustness of the proposed approach, 10 randomly generated process plan selection problems with increased complexity have been considered. Comparative studies of the results for these problems are shown in Table 11. From the results, it is clear that both the algorithms provide better solutions than the lower bound values. Therefore, it can be said that the achieved results are the near optimal results. It is evident from the table that for each case, KBAIS outperforms the classical AIS.

Table 11. Comparison of KBAIS and AIS for 10 random problems.

The proposed heuristic KBAIS has been coded in C++ programming language and the experiment has been carried out on an IBM PC with a Pentium IV CPU-1.9 GHz processor. To sum up, all the aforementioned results not only authenticate the supremacy of the proposed algorithm over existing heuristics but also provides a new dimension to the solution of complex combinatorial problems in real time.

The main contribution of this paper is to develop an efficient and consistent algorithm taking ideas from the existing ones for solving a computer-aided process planning (CAPP) problem in a randomised CIM environment. In the proposed model, an inevitable but forgotten factor known as scrap or rejection has been accounted that affects the overall cost of a finished product in an adverse manner. The main objective of this paper is to minimise the output unit cost by considering precedence relationships, availability of machines, tools, TAD and scrap. It can be concluded from the prominent literature that a CAPP problem is a NP-hard problem and mathematically complicated to solve. Encouraged by the successful implementation of random search techniques to tackle such complex combinatorial problem, a less explored meta-heuristic known as AIS has been examined to solve the intricacies of process planning problems. Simultaneously, a new algorithm which works on the inherent capability of AIS and power of knowledge, KBAIS has been proposed. The proposed algorithm has worked on three basic steps: initialisation, selection and hyper-mutation. The KBAIS simultaneously satisfies several goals, viz. minimise the output unit cost, processing cost, generated scrap and maximise the number of output units. First, a mathematical model has been formulated by accounting the various technological constraints. Thereafter, a feasible process plan has been generated by implementing the knowledge base. The proposed algorithm is examined over several datasets with increasing complexity. Extensive computational experiments reveal the robustness and supremacy of the proposed algorithm.

In the future this research can be stretched out to various problems of the flexible system environment that cover the balancing or allocation of resources. This research can also be employed for the multi-criterion decision-making problems in an FMS environment as well as a flexible supply chain environment. As now, the present problem is taken from the literature but this model can also address the real industrial problem with some changes according to the managers and it will provide a new insight to the practitioners as well as academicians.

The work described in this paper was substantially supported by a grant from the Research Gants Council of the Hong Kong Special Administrative Region, China (Project No. PolyU 510410). The authors would also like to thank Hong Kong Polytechnic University Research Committee for the financial support.

The set of D of all possible process plans is computed by examining the description of all operations and identifying the machines and tools with setup directions along with percentage of scraps. To calculate the lower bound of the process planning problem, all the cost with the maximum value will be considered.

Suppose, there is a set of all possible features in a part and the set O is the set of all operations. (). The set is a null set at the initial. It is the set of the operation chosen by the user. Therefore, and the operations will be added and the maximum set of all the operations in the sequence is and the operations are added according to the precedence relationship. The precedence operations for each operation are in defined in the set Pi () and . The operations which are not chosen are collected in another set . The operations are selected repeatedly until the set becomes a null set or . The available machines for each operation are collected in another set Mi. () and . The available tools for each operation are collected in another set Ti. () and . All the value of scrap for each operation for each machine is given in the set SC (). The cost value for the machining is defined by a set Cm. (). The tooling cost is for each operation is stored in set Ct. The raw material cost is defined as Rm. The changes of machines, tools and set-ups are counted in set [s]. The changing costs are defined by a set CC. (). The are the machine changing cost, tool changing cost and set-up changing cost respectively. To calculate the lower bound all the lower bound values of the cost or the maximum values of the costs are selected. The set has all the possible maximum values of various costs. To find the lower bound, the algorithm has the three steps:

• 1. Initialise the process plan in set S in which the sequence of operations are coming from set and machines are selected from set Mi, Cm and SC whereas the tools are selected from the set Ti and Ci. The cost can be calculated as follows:

Graph

• 1. Test , and if not
• 2. the set S will be extended up to the maximum or until all the operations are selected. The process plan with alternative operations but having the highest cost is the lower bound solution or process plan.