Decomposition rules of cloud machining orders

Owing to the complexity of parts’ structure and process, cloud machining orders cannot be conducted on a single machine tool. When a machining order arrives to the workshop from cloud manufacturing platform, it will be decomposed into machining subtasks that can be completed independently by a single machine tool. For part-level machining orders, the decomposition rules can be described as follows:

1. (1) Hierarchical decomposition principle. For machining orders, a three-layer task tree is formed, including the part layer, the feature layer, and the process layer.

2. (2) Granularity control principle. The decomposition granularity of machining orders must be appropriate. A larger granularity may lead it difficult to execute the orders on the resources; while a smaller granularity may lead that the time and costs increase dramatically between machining subtasks.

3. (3) Coupling principle. For subtask nodes with high interdependence at the same level and those with similar machining objectives, they can be integrated into a subtask node.

According to the above rules, the structure tree of part-level machining subtask is shown in Figure 2, where Part_T denotes the machining orders in the part layer; Feature_T denotes the machining subtasks in the feature layer; and M_T denotes the machining subtasks in the process layer.

Fig. 2. The decomposition tree of cloud machining order.

After the part-level cloud machining order is decomposed into process-level machining subtasks, the set of machining subtasks can be formulated as:

(1)$${MT} = \{ {{ MT}_1, \;{ MT}_2, \;\ldots , \;{MT}_i, \;\ldots , \;{ MT}_n}\}, $$

where MT_i denotes ith subtask of cloud machining order MT and n is the total number of subtasks.

The part-layer and feature-layer machining subtasks can be deduced from the process-layer machining subtasks and decomposition tree, so the research pays much more attention to process-layer machining subtasks.

Formal description of machining subtasks

After the process-level machining subtasks are built, their materials, geometric characteristics, and technical parameters need to be formally described. From the perspective of machining, typical features include plane (general plane, step surface, etc.), outer circle (cylinder, platform, cone, etc.), hole (center hole, through hole, blind hole, step hole, thread hole, etc.), groove (T-groove, U-groove, V-groove, swallow-tail groove, straight groove, circular groove, rectangular groove, etc.), special features (chamfering, cavity). The comprehensive information of machining subtasks can be described by relational algebra and set theory as follows:

(2)$${ MT}\unicode{x2237}=\{ {T \_{ID},\,T\_ {Basic},\,T \_{Object},\,T \_ {Requirement},\, T \_ {Extra}}\},$$

where T_ID denotes the number of subtasks; T_Basic denotes the basic attributes of subtasks, including name, content, etc. T_Object denotes the target information for subtasks; T_Requirement denotes the production requirements, including the batch and due date of subtasks; T_Extra denotes other requirements for subtasks.

A detailed definition of the basic information of machining subtasks is shown in the following formula:

(3)$$T_{Basic} = \{ {T\_name, \;T\_customer, \;T\_content}\}, $$

where T_name is the name of the machining subtask; T_customer is the publisher of the machining subtask; and T_content is the content of machining subtask.

The object of machining subtask includes size, batch, due date, cost, etc. They can be formulated as follows:

(4)$$T_{{ Requirement}} = \{ {{size, \;batch}, \;{ duedate}, \;{cost}}\}, $$

where size denotes the production size; batch denotes the production batch; duedate denotes the due date; cost denotes the cost of the machining subtask.

Other requirements including the special equipment and special tools required for the machining subtasks, which can be formulated as follows:

(5)$$T_{{ Extra}} = \{ {{special\;equipment}, \;{special\;tools}}\}. $$

Generation of sequential machining subtasks

After the cloud machining orders were decomposed into finer granularities, it is essential to determine the sequence between the various machining subtasks to be processed. The rules for determining the processing sequence is listed as follows: (1) The main process route is obtained based on the process data. (2) The process constraint relationship is determined by the processing sequence between machining subtasks.

At first, it is assumed that the typical main process route of a part is A ₁, A ₂, …, A_i, …, A_n. A_i is ith process. If the machining subtask t is the same as the ith process of the main process route, the priority coefficient of machining subtask t is:

(6)$$f (t) = \displaystyle{{n-i + 1} \over n}.$$

In addition, there are various constraints on the machining subtasks of parts. The machining sequence of a part is as follows: the benchmark precedes the others, the roughing precedes the finishing, the main feature precedes the minor feature, and the surface precedes the hole. All constraints which must be satisfied for machining subtask sequencing are defined as constraint sets, which is represented by matrix A_{n ×n}. The element a_ij in the matrix denotes the sequence between machining subtasks, and its value is:

(7)$$a_{ij} = \left\{{\matrix{ 1, \hfill & {{\rm Maching}\;{\rm subtask}\;i\;{\rm precedes}\;{\rm maching}\;{\rm subtask}\;j,} \hfill \cr 0, \hfill & {{\rm Others}}. \hfill \cr } } \right.$$

Taking benchmark as an example, machining subtasks are divided into benchmark sets and non-benchmark sets through searching for all matching tasks. According to the principle that benchmark precedes others, the machining subtasks in benchmark set take precedence over the machining subtasks in non-benchmark set. Assign a priority matching task to 1, such as machining subtasks 1 and 4 are in benchmark set, while machining subtasks 2 and 3 are in on-benchmark set. Then, a ₁₂ = a ₁₃ = a ₄₂ = a ₄₃ = 1.

The machining subtask sequence can be defined as follows:

(8)$$\sum\limits_{i = 1, j\in S}^n { (n-i) f_j (i) }, $$

where f_j(i) denotes the priority coefficient of ith machining subtask in the jth machining subtask sequence, which can be formulated in formula (6). Here, n is the total number of machining subtasks and S is a collection of all machining subtask sequences.

The generation procedure of sequential machining subtasks is shown in Figure 3. The main procedure is (1) to obtain priority coefficients by comparing the machining subtasks with the main process routes; (2) to obtain the constraint set of machining subtasks by using process rules; (3) to find the maximum value of formula (8) through the optimization algorithm. The machining subtasks constraint matrix is taken as the constraint condition of optimization. That is, the sequence obtained in the optimization procedure can be adjusted by the machining subtask constraint matrix.

Fig. 3. The generation of sequential machining subtasks.

Sequential machining subtasks can be obtained by sorting the machining subtasks of the parts. In order to better describe the sequential machining tasks, a directed graph is adopted, namely

(9)$$D = (V (D) , \;A (D) ), $$

where V(D) denotes a node set in a directed graph, that is, a machining subtask. A(D) denotes a directed arc set, which is used to indicate the sequence between the various machining subtasks. For any directed arc a ∈ A, it is represented by an ordered pair of machining subtasks u, v. The ordered pair (u, v) indicates that the subtask u should be executed before the subtask v.

Workshop-level resource allocation model

Workshop-level resource allocation is the matching between machining subtasks and available resources. Usually, a machining subtask corresponds to multiple resources (called candidate resources). It is supposed that a cloud machining order is decomposed into n machining subtasks and the ith machining subtask has x_i candidate resources. There is $\prod\nolimits_{i = 1}^n {x_i}$ resource allocation scheme for the cloud machining order. The optimization model of resource allocation problem is shown in Figure 4.

Fig. 4. The optimization model of resource allocation problem.

Although the candidate resources can meet the technical requirements of machining subtasks, the consumed time and cost of resources allocation scheme are different.

Objective function

There are many parameters to evaluate resource allocation schemes, such as processing time, processing cost, processing quality, carbon emissions, and loading rate (Zhang et al., Reference Zhang, Liu, Chen, Zhang and Leng2017a; Zhang and Li, Reference Zhang and Li2018; Zhou et al., Reference Zhou, Yuan, Lu and Xiao2018a, Reference Zhou, Zhou, Lu, Tian and Xiao2018b). Taking into account the characteristics of cloud manufacturing, processing time T, processing cost C, qualified rate Q, and resource utilization rate H are selected as the optimized parameters.

1. (1) The total processing time of resource allocation can be formulated as follows:

   (10)$$T = T_{{\rm IN}} + T_{{\rm TR}} = \sum\limits_{i = 1, j\in v}^n {T_i (j) } + \sum\limits_{i = 1, k\in v}^{n-1} {T_{i, i + 1} (j, \;k) }, $$

where T _IN is the total processing time of machining subtasks; T _TR is the transportation time between different resources; T_i(j) denotes the processing time for subtask i on resource j; T_{i,i +1}(j,k) denotes the transportation time between resource j and k for subtask i; v is the resources set; and n is the machining subtasks set.

• (2) The total processing cost can be formulated as follows:

  (11)$$C = C_{{\rm IN}} + C_{{\rm TR}} = \sum\limits_{i = 1, j\in v}^n {C_i (j) } + \sum\limits_{i = 1, k\in v}^{n-1} {C_{i, i + 1} (j, \;k) }, $$

where C _IN is the total processing cost of machining subtasks; C _IR is the transportation cost between different resources; C_i(j) is the processing time for subtask i on resource j; C_{i,i +1}(j,k) is the transportation cost between resource j and k for subtask i; v is the resources set; and n is the machining subtasks set.

• (3) Processing quality rate can be formulated as follows:

  (12)$$Q = 1-\prod\limits_{i = 1, j\in v}^n {Q_i (j) }, $$

where Q_i(j) is the qualified rate of ith subtasks processed on j_th resource; v is the resources set; and n is the machining subtasks set.

• (4) Resource utilization rate can be formulated as follows:

  (13)$$H = h_{{\rm max}}-h_{{\rm min}},$$

where h _max is the machining time corresponding to the specific resource with the longest machining time in a certain time period and h _min is the machining time corresponding to the resource with the shortest machining time in a certain time period.

Due to the difference of the dimensions, the above four parameters are standardized and the objective function can be formulated as follows:

(14)$$f (x ) = \omega _c\displaystyle{{C_{{\rm max}}-C (x ) } \over {C_{\rm max}}} + \omega _T\displaystyle{{T_{{\rm max}}-T (x ) } \over {T_{{\rm max}}}} + \omega _Q\displaystyle{{Q_{{\rm max}}-Q (x ) } \over {Q_{{\rm max}}}} + \omega _H\displaystyle{{H_{{\rm max}}-H_x} \over {H_{{\rm max}}}},$$

where C _max is the maximum processing cost for each generation solution; T _max is the maximum processing time for each generation solution; Q _max is the maximum Q for each generation solution; and H _max is the maximum resource utilization for each generation solution.

Referring to the resource allocation problem, there is a sequential constraint between machining subtasks; besides, there is a delivery-time constraint [T], total cost constraint [C], and quality requirement constraint [Q]. When the above three constraints are met, the resource utilization should be made as small as possible. The relationships between them are listed as follows:

Processing cost constraints for machining subtask i:

(15)$$\left\{{\matrix{ {\mathop {\max }\limits_{1 \le i \le n, j\in v} C_i (j) \le [{C_i}] }, \hfill \cr {\mathop {\max }\limits_{1 \le i \le n,j\in v} \left({\sum\limits_{i = 1,j\in v}^n {C_i (j) } + \sum\limits_{i = 1, j, k\in v}^{n-1} {C_{i, i + 1} (j, \;k) } } \right)\le [C] }. \hfill \cr } } \right.$$

Processing time constraints for machining subtask i:

(16)$$\left\{{\matrix{ {\mathop {\max }\limits_{1 \le i \le n, j\in v} T_i (j) \le [{T_i}] }, \hfill \cr {\mathop {\max }\limits_{1 \le i \le n,j\in v} \left({\sum\limits_{i = 1,j\in v}^n {T_i (j) } + \sum\limits_{i = 1, j, k\in v}^{n-1} {T_{i, i + 1} (j, \;k) } } \right)\le [T] }. \hfill \cr } } \right.$$

Processing quality constraints for machining subtask i:

(17)$$\left\{{\matrix{ {\mathop {\min }\limits_{1 \le i \le n, j\in v} Q_i (j) \ge [{Q_i}] }, \hfill \cr {\mathop {\min }\limits_{1 \le i \le n , j\in v} Q_i (j) \ge [Q]}. \hfill \cr } } \right.$$

FAHP is used to turn the above multi-objective model into a single-objective model. The weighted value of processing time T, processing costs C, processing quality Q, and resource utilization rate H are denoted as w_T, w_C, w_Q, and w_H, respectively, and w_T + w_C + w_Q + w_H = 1. The procedure of determining weights is described as follows:

1. (1) Establish the triangular fuzzy number complementary judgment matrix

Experts use 0.1–0.9 to evaluate the above four parameters. The meanings of 0.1–0.9 are shown in Table 1. Take K experts to evaluate the above problems and get the triangle fuzzy number judgment matrix of each expert, marked as $\tilde{A}_k = (\tilde{a}_{ij}^k ) _{n \times n}$, respectively.

Table 1. Meaning of 0.1–0.9

$\tilde{a}_{ij}^k = (a_{ij}^{kL} , \;a_{ij}^{kM} , \;a_{ij}^{kN} )$ is the triangular fuzzy number of the importance degree for index i relative to index j given by expert k. The three components are denoted as: conservative evaluation, favorite evaluation, and optimistic evaluation.

The following formula is used to collect the evaluation of all experts and to get $\tilde{A}_k = (\tilde{a}^k_{ij} ) _{n \times n}$.

(18)$$\tilde{a}_{ij} = \left({\sum\limits_{k = 1}^K {\omega_ka_{ij}^{kL} , \;\sum\limits_{k = 1}^K {\omega_ka_{ij}^{kM} , \;\sum\limits_{k = 1}^K {\omega_ka_{ij}^{kU} } } } } \right), \;\;\quad i, \;j = 1, \;2, \;\ldots , \;n,$$

where K is the number of experts; w_k is the kth expert's authority.

• (2) Calculate the triangle fuzzy weights

Based on the triangular fuzzy number complementary judgment matrix A% = (a%)_n×n, the fuzzy weight of each indicator q _i% can be calculated as follows:

(19)$$q_i\% = \left({\displaystyle{{\sum\nolimits_{\,j = 1}^n {a_{ij}^L } } \over {\sum\nolimits_{i = 1}^n {\sum\nolimits_{\,j = 1}^n {a_{ij}^L } } }}, \;\displaystyle{{\sum\nolimits_{\,j = 1}^n {a_{ij}^M } } \over {\sum\nolimits_{i = 1}^n {\sum\nolimits_{\,j = 1}^n {a_{ij}^M } } }}, \;\displaystyle{{\sum\nolimits_{\,j = 1}^n {a_{ij}^U } } \over {\sum\nolimits_{i = 1}^n {\sum\nolimits_{\,j = 1}^n {a_{ij}^U } } }}} \right).$$

The following formula is used to de-fuzzy the fuzzy weights.

(20)$$q_i = \displaystyle{{q_i^L + 2q_i^M + q_i^U } \over 4}.$$

The following formula is used as the normalization, and the weighted value is as follows:

(21)$$\omega _i = \displaystyle{{q_i} \over {\sum\nolimits_{i = 1}^4 {q_i} }}.$$

• (3) Check the consistency

To avoid the lack of scientific evaluation and ensure the consistency of data/information, it is essential to check and confirm the consistency of the triangular fuzzy judgment matrix. Consistency index is given in the following equation:

(22)$${\rm CI} = \displaystyle{{\lambda _{{\rm max}}-n} \over {n-1}},$$

where λ _max is the maximum eigenvalue of the fuzzy reciprocal judgment matrix (E(a _ij%)/E(a _ji%))_n×n; E(a _ij%) is the expectation of the triangular fuzzy number a _ij% that can be determined by $E (a_{ij}\%) = (a_{ij}^L + 2a_{ij}^M + a_{ij}^N /4)$. The coefficient of consistency judgment is given as follows:

(23)$${\rm CR} = \displaystyle{{{\rm CI}} \over {{\rm RI}}},$$

where RI is the average random consistency index that is used to revise CI. The RI of 4th order matrix is 0.89. If CR < 0.1, it can be considered that the triangular fuzzy number judgment matrix passes the consistency checking. Otherwise, it needs to re-establish the matrix.

Standard firefly algorithm and problem description

At present, various swarm intelligence algorithms, such as ant colony optimization (ACO), genetic algorithm (GA), particle swarm optimization, artificial bee colony algorithm (ABC), and artificial fish swarm algorithm (AFSA), have been used to solve the combination optimization problem. As a member of the swarm intelligence family of algorithms, FA was proposed by Professor Xin-She Yang, University of Cambridge in 2009 (Yang, Reference Yang2010). It is derived from the phenomenon of clustering activity of fireflies at night. Since FA is a stochastic algorithm using a kind of randomization to search for a set of solutions, it has the advantages of less parameters and easy realization compared with the traditional swarm intelligence algorithms. Therefore, it is used to solve the resource allocation scheme.

The standard firefly algorithm follows the below principles: (1) a firefly with higher brightness attracts the lower brightness of the firefly to its movement; (2) the intensity of higher fireflies’ attraction to other fireflies is proportional to their brightness; and (3) the brightness value of the firefly is determined by the fitness.

Based on this, the model of standard firefly algorithm is established. The relative fluorescence brightness of fireflies can be formulated as follows:

(24)$$I = I_0 \times {\rm e}^{-\gamma r_{ij}},$$

where I ₀ is the maximum fluorescence of firefly, that is, the fluorescent brightness when r = 0; the greater the fitness is, the greater the brightness can be; γ is the light absorption rate ∈ [0,+∞); r_ij is the distance between the ith and jth fireflies.

The attraction of firefly can be formulated as follows:

(25)$$\beta (r ) = \beta _0\,{\rm e}^{-\gamma r_{ij}^2 },$$

where β ₀ denotes the attraction when r = 0.

The distance between any pairs of fireflies in space can be formulated as follows:

(26)$$r_{ij} = X_i-X_j = \sqrt {\sum\limits_{k = 1}^l {{ ({x_{i, k}-x_{\,j, k}} ) }^2} }, $$

where X_i and X_j denote the positions of firefly i and j, respectively; l is the coordinate dimensions; x_i,k is the kth dimensional component of space coordinate X_i; x_j,k is the kth dimensional component of space coordinate X_j.

The position of firefly j attracted by firefly i can be formulated as follows:

(27)$$x_{i, k}^{t + 1} = x_{i, k}^t + \beta \times ({x_{\,j, k}^t -x_{i, k}^t } ) + \alpha \vert {{ rand}-0.5} \vert, $$

where $x_{i, k}^t$ is the k-dimensional components of firefly i at tth iteration; α is the step factor; rand is a random factor that is uniformly distributed on [0,1].

According to the characteristics of resource allocation optimization, integer is used to describe the position coding rules corresponding to the coordinate component of fireflies. The specific rules are described as follows:

• Rule 1: Code the machining subtask, and the coordinate dimension of the firefly equals the number of subtasks.

• Rule 2: A coordinate component of firefly denotes a machining subtask.

• Rule 3: The candidate resources for each machining subtask are coded, in sequence of 0, 1, 2, 3, …, n_i–1.

• Rule 4: The kth coordinate component of the firefly ranges from 0 to the resources number of kth candidate machining subtask minus one.

• Rule 5: A coordinate value of a firefly represents a candidate resource.

The optimized algorithm IFA-PSA for the resource allocation

The standard firefly algorithm is not sufficient to solve the optimization of resource allocation because the space of the solution belongs to the real domain; while the space of resource allocation optimization belongs to the discrete integer domain. At the same time, three parameters of standard firefly algorithm (including step length factor α, attraction degree β, and light absorption coefficient γ) have a great influence on the effectiveness of algorithm. Among them, γ has the greatest effect on absorption, which determines firefly individual moving distance size. Too small γ may lead the algorithm into local optimum, and the oversize γ easily effect the convergence speed and even lose the characteristics of the group algorithm. In general, γ ∈ [0.01,100]. Step length factor α may increase levels of uncertain of position updates and extend the search capabilities to avoid premature convergence. Generally, α ∈ [0,1]. Therefore, in this paper, the IFA-PSA is proposed. In IFA-PSA, the coordinate updating formula is discretized to make the solving space to be discrete integer, and PSO is combined to optimize the three parameters α, β, and γ of firefly.

The position updated formula for the firefly is improved as follows:

(28)$$x_{i, k}^{t + 1} = x_{i, k}^t + \beta \otimes (x_{\,j, k}^t {\rm \Theta }x_{i, k}^t ) \oplus \alpha \vert {{ rand}-0.5} \vert, $$

where $x_{j, k}^t {\rm \Theta }x_{i, k}^t$ is the subtraction operation between positions, used to represent the main movement direction of the firefly. The operation rule is

(29)$$x_{\,j, k}^t {\rm \Theta }x_{i, k}^t = \left\{{\matrix{ {x_{\,j, k}^t ,} \hfill & {x_{i, k}^t \ne x_{\,j, k}^t }, \hfill \cr {0, } \hfill & {{\rm Others}}. \hfill \cr } } \right.$$

β and α|rand − 0.5| are used in conjunction to control the movement distance calculation between firefly i and firefly j, $S_{i, k}^t = \beta \otimes x_{j, k}^t {\rm \Theta }x_{i, k}^t \oplus \alpha \vert {{rand}-0.5} \vert =$; $S_{i, k}^t$ is the distance from the firefly i to the firefly j at the k dimension, the values are calculated as follows:

(30)$$S_{i, k}^t = \left\{{\matrix{ {x_{\,j, k}^t {\rm \Theta }x_{i, k}^t , } \hfill & {{\rm \alpha }\vert {{ rand}-0.5} \vert < \beta }, \hfill \cr {0,} \hfill & {{\rm Others}}. \hfill \cr } } \right.$$

This paper uses a particle corresponding to the α, β ₀, and γ of the firefly algorithm; the position of particle is p _i = (p _i1, p _i2, p _i3), and particles have three directions of movement speed, marked as V _i = (V _i1, V _i2, V _i3). The corresponding parameters of particle are input into the firefly algorithm. Each particle has an optimal solution in the firefly algorithm, and the corresponding parameter of particle represents the position of particle in the solution space.

The optimal position experienced by the individual particle i is P _best,i, and the optimal position of the whole population is Q _best. The fitness of P _best,i and Q _best is the optimal fitness of the firefly algorithm corresponding to the particle.

Particle velocity and position updating formula are described as follows:

(31)$$V_i^{t + 1} = \omega V_i^t + c_1r_1 (P_{{\rm best}, i}-p_i^t ) + c_2r_2 (Q_{{\rm best}}-p_i^t ), $$

(32)$$p_i^{t + 1} = p_i^t + V_i^{t + 1}, $$

where w stands for the inertial weight value; c ₁ is a weight constant which adjusts the particle to the best position; c ₂ is a weight constant that regulates the movement of particles to the best global position; r ₁ and r ₂ are set as two independent random numbers; $V_i^t$is the velocity of tth generation of particle i; $p_i^t$ is the position of tth generation of particle i.

The running procedure of improved firefly algorithm based on the IFA-PSA algorithm is shown in Figure 5. The specific steps are described as follows:

• Step 1: Set the population size m, iteration times G ₁ and w, c ₁, c ₂ of the PSO; set the population size n, iteration times G ₂ of the firefly algorithm.

• Step 2: Initialize m particles.

• Step 3: Input the particle's corresponding parameter value α, β ₀, and γ to the firefly algorithm.

• Step 4: Use the data of particle to initialize n fireflies.

• Step 5: According to the position of the firefly, the fitness value represented by each firefly is calculated by formula (14).

• Step 6: According to the size of the fitness value of the firefly and the formula (28), the position of the firefly is updated, and the iterations number of the firefly algorithm is plus one.

• Step 7: If the firefly algorithm iterates less than G ₂, go to Step 4; otherwise, go to Step 8.

• Step 8: According to the calculation results of the firefly algorithm, the advantages and disadvantages of the particle position are judged; P _best,i and Q _best are updated.

• Step 9: The position of the particles is updated according to formulas (31) and (32), and the iterations number of particle swarm optimization algorithm is plus one.

• Step 10: If the iteration time of PSO is less than G ₁, go to Step 3; otherwise, output the optimal fitness value and the position of the corresponding firefly.

Fig. 5. Flowchart of IFA-PSA.