Multi-service collaboration and composition of cloud manufacturing customized production based on problem decomposition

As shown in Fig. 1, the CMfg service system consists of three roles: provider, cloud service center, and user. A system includes multiple providers, which provide physical manufacturing resources and capabilities to the cloud service center. Manufacturing resources include soft, hard, and human resources [37]. Manufacturing capabilities are expressed by combinations of manufacturing resources. Manufacturing capabilities reflect the ability to complete a manufacturing task supported by related manufacturing resources. Cloud service center encapsulates resources and capabilities of providers into cloud services, and then efficiently manages and operates cloud services. Different providers with different manufacturing resources and capabilities may offer some cloud services with identical functionality and different QoS, including time, cost, etc.

Cloud services are delivered to users on demands. Users consume different services as needed with the support of the cloud service center. Knowledge enables virtual access to manufacturing resources and capabilities through service-oriented encapsulation and categorization, along with efficient management and intelligent search of cloud services. In addition, for special cases or simple manufacturing tasks, users can directly request services from providers, while the latter can directly offer services to the former.

Definition 1 [2] (Order) An order in CMfg is a four-tuple $O=(id,type,$ $quant\!\!\>it\!\!\>y)$, where $id$ represents the id of order, $type$ represents the type of products, and $quant\!\!\>it\!\!\>y$ represents the quantity of products.

The design phases of customized production output digital intermediate products instead of physical products. These digital products can be efficiently managed through the cloud service center and delivered to be processed by subsequent services in real time. This opens up more possibilities for the service composition of customized production. As shown in Fig. LABEL:fig:Fig.3, the customized production framework with service collaboration in mind consists of three layers. The first layer is the user layer, which collects customization requirements and generates orders. An order is considered as one task. The middle layer is the cloud service center layer, which receives the user orders, decomposes the tasks into sub-tasks, and matches the sub-tasks with the candidate services to generate service compositions as well as service usage schemes. The bottom layer is the service application layer, which performs product design and manufacturing to meet the customization requirements. For ease of being understood, the following concepts are described:

1) Task decomposition: A task, denoted by $Task$, can be decomposed into multiple sub-tasks $ST$. That is, $Task=\{{ST}_{1},\ {ST}_{2},\>\cdots,\ {ST}_{\!i},\>\cdots,\ {ST}_{\!I}\}$.

2) Service matching: Each sub-task ${ST}_{\!i}$ corresponds to a candidate service set ${CSS}_{i}$ containing services with identical functionality but different costs and times of a single use. That is, ${CSS}_{i}=\{{CS}_{i,1},\ {CS}_{i,2},\>\cdots,\ {CS}_{i,j},\>\cdots,\ {CS}_{i,\,J}\}$ where ${CS}_{i,j}$ denotes a candidate service, $j=1,\ 2,\>\cdots,\ J$.

3) Collaboration: Services can collaborate on a sub-task. The framework allows services with the same functionality to collaborate.

4) Service composition: For each sub-task ${ST}_{\!i}$ and the corresponding candidate service set ${CSS}_{i}$, $i=1,\ 2,\>\cdots,\ I$, there exists a selected service set ${SSS}_{i}=\{{CS}_{i,k},\>\cdots,\ {CS}_{i,m},\>\cdots,\ {CS}_{i,n}\}$, where ${SSS}_{i}$ is a non-empty subset of ${CSS}_{i}$. A service composition can be denoted as a set $\{{SSS}_{1},\ {SSS}_{2},\>\cdots,\ {SSS}_{i},\>\cdots,\ {SSS}_{I}\}$.

5) Service usage scheme: The services in ${SSS}_{i}$ for the sub-task ${ST}_{\!i}$ have the same functionality, $i=1,\ 2,\>\cdots,\ I$. The service usage scheme indicates how many times each of these services will be used.

6) Optimization: When conducting a service composition and its usage scheme, there are always some constraints such as time, cost, and limited resources. Under various constraints, in order to satisfy the requirements as much as possible, the service composition and service usage scheme should be optimal.

Compared with general frameworks for cloud service composition such as those presented in [15] and [22], the framework proposed in this paper allows multiple services with the same functionality to collaborate on the same sub-task. As a consequence, our proposed framework lays a solid foundation for improving productivity and reducing resource idleness.

The optimal CMCP service composition and the associated service usage scheme should be of high efficiency and low consumption, and use a minimal amount of service resources. Therefore, the optimization goal consists of three objectives: the minimum total completion time, the lowest total production cost, and the minimum number of selected services. The total completion time (resp., total production cost) refers to the total time (resp., cost) required to complete a task. The number of selected services indicates how many services are selected to complete a task.

For example, there is a simple custom order with the $quant\!\!\>it\!\!\>y$ equal to 10. The order is treated as a production task, which contains two sub-tasks: design sub-task ${ST}_{d}$ and manufacturing sub-task ${ST}_{m}$. There are two candidate services ${CS}_{d,1}$ and ${CS}_{d,2}$ for ${ST}_{d}$, and two candidate services ${CS}_{m,1}$ and ${CS}_{m,2}$ for ${ST}_{m}$. Assume that the four services are with the same time of a single use. The service ${CS}_{d,1}$ (resp., ${CS}_{m,1}$) has a lower cost per use than the service ${CS}_{d,2}$ (resp., ${CS}_{m,2}$). There are the following nine service compositions for this task: $\{{CS}_{d,1},\ {CS}_{m,1}\}$, $\{{CS}_{d,1},\ {CS}_{m,2}\}$, $\{{CS}_{d,2},\ {CS}_{m,1}\}$, $\{{CS}_{d,2},\ {CS}_{m,2}\}$, $\{{CS}_{d,1},\ {CS}_{m,1},\ {CS}_{m,2}\}$, $\{{CS}_{d,2},\ {CS}_{m,1},\ {CS}_{m,2}\}$, $\{{CS}_{d,1},\ {CS}_{d,2},\ {CS}_{m,1}\}$, $\{{CS}_{d,1},$ $\ {CS}_{d,2},\ {CS}_{m,2}\}$, and $\{{CS}_{d,1},\ {CS}_{d,2},\ {CS}_{m,1},\ {CS}_{m,2}\}$. Each service composition has one or more usage schemes. A complete customized production solution consists of a service composition and a service usage schemes. To minimize the total production cost and the number of selected services, the service composition $\{{CS}_{d,1},\ {CS}_{m,1}\}$ would be selected, and services ${CS}_{d,1}$ and ${CS}_{m,1}$ should be used 10 times each. To minimize the total completion time of the task, the service composition $\{{CS}_{d,1},\ {CS}_{d,2},\ {CS}_{m,1},\ {CS}_{m,2}\}$ should be selected, and each service would be used 5 times.

For a large-scale task, it is difficult to compute the total completion time accurately. In the sequel, a fast recursive approach is proposed to approximate the total completion time. Meanwhile, the formulas for calculating the total production cost and the number of selected services are also given. We assume that several services with the same functionality are selected for sub-task ${ST}_{\!i}$, and the set ${SSS}_{i}$ contains selected services for ${ST}_{\!i}$, $i=1,\ 2,\>\cdots,\ I$. The theoretical minimum completion time of ${ST}_{\!i}$ is denoted by ${Time}_{i}$. The cumulative usage time of the service ${CS}_{i,j}$ in ${SSS}_{i}$, $j\in\{1,\ 2,\>\cdots,\ J\}$, is denoted as follows:

where $K$ is the usage number of ${CS}_{i,j}$ and ${time}_{k}$ is the $k$th usage time of ${CS}_{i,j}$, $k=1,\ 2,\>\cdots,\ K$.

For each $i\in\{1,\ 2,\>\cdots,\ I\}$, let ${LCS}_{i}$ represent the selected service with the longest cumulative usage time in ${SSS}_{i}$. The maximum time of a single use for service ${LCS}_{i}$ is denoted by ${UT}_{i}$. The cumulative usage time of ${LCS}_{i}$ is denoted as:

The sub-tasks are executed sequentially. The theoretical minimum completion time ${Time}_{i}$ of ${ST}_{\!i}$ is determined by ${Time}_{i-1}$, ${UT}_{i-1}$, ${LT}_{i}$ and ${UT}_{i}$, as follows:

where ${LT}_{i}$ is calculated using Eq. (2), $i=1,\ 2,\>\cdots,\ I$.

The cost of completing sub-task ${ST}_{\!i}$ is :

where cost$({CS}_{i,j})\$represents total cost of using the service ${CS}_{i,j}$.

The number of selected services in ${SSS}_{i}$ is:

where num$({SSS}_{i})$ represents the number of selected services in the set ${SSS}_{i}$.

Recall that $Task=\{{ST}_{1},\ {ST}_{2},\>\cdots,\ {ST}_{\!i},\>\cdots,\ {ST}_{\!I}\}$. For $Task$, let ${Time}_{total}$ represent its total completion time, ${Cost}_{total}$ be the total production cost, and ${Num}_{total}$ indicate the number of services selected for $Task$. We have:

where ${Time}_{I}$, Cost$\left({ST}_{\!i}\right)$, and Num$({ST}_{\!i})$ are calculated using Eqs. (3-5), respectively.

The problem decomposition can reduce the difficulty of solving complex problems by decomposing them into multiple parts. More precisely, a problem is decomposed into several parts and each part is optimized separately. Let $O$ represent an order. We assume that the production task of $O$ contains $I$ sub-tasks $\{{ST}_{1},\ {ST}_{2},\>\cdots,\ {ST}_{\!i},\>\cdots,\ {ST}_{\!I}\}$ with ${ST}_{\!i}$ being the $i$th sub-task. As shown in Fig. 3, a service composition and its usage scheme for $O$ can be encoded as a chromosome set $X_{O}$ with its size equal to the number of sub-tasks. The set $X_{O}=\{X_{O}^{1},\ X_{O}^{2},\>\cdots,\ X_{O}^{i},\>\cdots,\ X_{O}^{I}\}$ is a complete solution, and any chromosome in $X_{O}$ is a partial solution corresponding to a sub-task. For each sub-task, a population will be generated to find the optimal partial solution. Thus, the complex problem of finding the optimal service composition and usage scheme for a task is decomposed into sub-problems of finding service composition and usage scheme for each sub-task.

For each $i\in\{1,\ 2,\>\cdots,\ I\}$, a chromosome $X_{O}^{i}$ with respect to sub-task ${ST}_{\!i}$ for order $O$ satisfies the following conditions:

1) $X_{O}^{i}$ is a non-zero vector with non-negative integer components. Assume that there are $J$ candidate services for the sub-task ${ST}_{\!i}$. Then, the dimension of $X_{O}^{i}$ is $J$, that is, $X_{O}^{i}=[x_{O}^{i,1},\ x_{O}^{i,2},\>\cdots,\ x_{O}^{i,j},\>\cdots,\ x_{O}^{i,\,J}]$.

2) The component $x_{O}^{i,j}\geq 0$ in $X_{O}^{i}$ corresponds to the $j$th candidate service ${CS}_{i,j}$, $j=1,\ 2,\>\cdots,\ J$. If $x_{O}^{i,j}$ is equal to zero, then ${CS}_{i,j}$ will not be selected; otherwise, ${CS}_{i,j}$ will be selected and used. Furthermore, the usage number of ${CS}_{i,j}$ is equal to $x_{O}^{i,j}$.

3) $\sum_{j=1}^{J}x_{O}^{i,j}=quant\!\!\>it\!\!\>y$, where $quant\!\!\>it\!\!\>y$ indicates how many products are in the order $O$.

4) Additional restrictions. For example, if a candidate service can only be used a maximum of 20 times, then the corresponding component cannot be greater than 20.

The basic process of the problem decomposition based genetic algorithm (PDGA) is shown in Algorithm  1. First, the service composition and associated service usage scheme can be encoded as a set of chromosomes by the problem decomposition. For each chromosome, create a population to search for the necessary individuals. Then, combine individuals from multiple populations to obtain the solutions that are the optimal service compositions and associated service usage schemes. In addition, the elite selection, the fast non-dominated sorting method, and the crowding distance assignment are used during the population iterations. Specifically, elite selection helps to maintain the best individuals. Fast non-dominated sorting method is used to quickly find superior individuals in populations. Crowding distance assignment improves the search capability of the algorithm.

Usually, it is necessary to solicit the opinions of users and the advice of experts before searching for the optimal cloud service composition. Based on the results of the solicitation, multiple service indexes are combined by weighted sum approaches to obtain the final evaluation index: quality of service (QoS). However, it is not easy to determine the weights of each index in the task [20]. Opinions and advice are highly dependent on personal experience, and the solicitation process takes additional time and cost. Thus, the stratified sequencing approach is used to prioritize the following three objectives (as previously presented in Section 3.3): 1) the primary objective is the minimum total completion time; 2) the secondary objective is the lowest total production cost; and 3) the final objective is the minimum number of selected services. The efficiency of the solution search is also improved by the stratified sequencing approach.

However, the stratified sequencing approach may lead the PDGA to focus too much on reducing total completion time at the expense of other objectives. This does not necessarily correspond to actual demands. Thus, a search bootstrap function is designed in the PDGA to obtain more diverse solutions. The specific pseudo-code of the function is shown in Algorithm  2. A search limit, denoted by $Limit$, is set by the user requirements for the objective of total completion time. This limit is used in the search bootstrap function. As the total completion time of a solution approaches this limit, Algorithm  1 will focus on reducing the total production cost and the number of selected services.

Definition 2 [38] (Non-dominated solution) Let $X_{1}$ and $X_{2}$ be two solutions in the current solution set. Solution $X_{2}$ is dominated by solution $X_{1}$ if all objective values of $X_{1}$ are not worse than the corresponding objective values of $X_{2}$, and one or more objectives of $X_{1}$ are better than the corresponding objective values of $X_{2}$. Solution $X_{1}$ is a non-dominated solution if $X_{1}$ is not dominated by any other solution in the current solution set.

Note that a non-dominated solution does not necessarily perform better in all objectives than any other solutions. It only means that there is no other solution that performs better in all objectives than the non-dominated solution $X_{1}$. For example, there is a solution set $\{X_{1}$, $X_{2}$, $X_{3}$}. For two objectives (e.g., the cost and the number of services required), $X_{1}=(3,2)$, $X_{2}=(3,3)$, and $X_{3}=(2,3)$. The solution $X_{2}$ is dominated by either of solutions $X_{1}$ and $X_{3}$. The solution $X_{1}$ (resp., $X_{3}$) is not dominated by solution $X_{3}$ (resp., $X_{1}$). As a consequence, solutions $X_{1}$ and $X_{3}$ are non-dominated solutions in the solution set.

For each sub-task, a population is created to search for the optimal partial solutions so as to generate complete solutions. The process is as follows. First, in each population, select an individual using the search bootstrap function (i.e. Algorithm  2). Second, among these individuals, select the one with the longest theoretical minimum completion time, denoted by $X_{i}$, $i\in\{1,\ 2,\>\cdots,\ I\}$. That is, $i$ indicates that $X_{i}$ is from the $i$th population for ${ST}_{\!i}$. The theoretical minimum completion time of $X_{i}$ is denoted by $MaxT$. Third, in each population except the $i$th population, calculate the dominance relationship between any two individuals by the fast non-dominated sorting method using Eqs. (3-5). Fourth, search for a particular individual having the lowest cost, the fewest number of selected services, and the theoretical minimum completion time less than $MaxT$. Finally, combine these individuals with $X_{i}$ to form a complete solution, and calculate the total completion time, the total production cost, and the number of selected services of the complete solution by Eqs. (6-8).

The specific pseudo-code of the complete solution generation is shown in Algorithm  3, where the variable $index$ is used to guide the population iteration operation. Specifically, the value of $index$ is equal to $i$, which indicates that the individual $X_{i}$ with the theoretical minimum completion time $MaxT$ is from the $i$th population for ${ST}_{\!i}$.

After generating a complete solution, all populations are iterated once. Simulated binary crossover and polynomial mutation are used in each iteration. We assume that there are two arbitrary paternal individuals whose respective genes at a particular position are $x_{1}$ and $x_{2}$. After the simulated binary crossover, the offspring genes are $c_{1}$ and $c_{2}$ as follows:

where $\beta$ is the spread factor that represents a ratio difference between parent and offspring individuals. The factor $\beta$ is calculated as follows through a random value $r$ in the range [0,1].

where $\eta_{c}$ is the spread factor distribution index as a custom parameter. The larger the value of $\eta_{c}$, the more similar the offspring individuals are to the parent individuals.

For a gene $x$, the gene $m=x+\delta\ast(u-l)$ is obtained by the polynomial mutation of $x$, where $u$ is the upper bound of $x$, $l$ is the lower bound of $x$, and $\delta$ is the perturbation factor calculated as follows through a random value $r$ in the range [0,1].

where $\delta_{1}=(x-l)/(u-l)$, $\delta_{2}=(u-x)/(u-l)$, and $\eta_{m}$ is the perturbation factor distribution index as a custom parameter. The larger the value of $\eta_{m}$, the greater the degree of mutation.

Suppose there are $I$ populations, each with size $Size$. The specific iteration process is as follows. First, cross-mutate each of the $I$ populations by Eqs. (9-11) to obtain $I$ offspring populations of size $Size$. Second, according to elite selection, combine each offspring population with its corresponding parent to constitute $I$ current populations of size $2\ast Size$. Third, calculate fitness values for individuals in the current populations using Eqs. (3-5). For the individuals in the $i$th population (where $i$ equals to $index$ output by Algorithm  3), the fitness includes the theoretical minimum completion time calculated by Eq. (3), the cost calculated by Eq. (4), and the number of selected services calculated by Eq. (5). Fitness for other populations includes the cost calculated by Eq. (4) and the number of selected services calculated by Eq. (5). Finally, for each current population, use the fast non-dominated sorting method with crowding distance assignment to select individuals so as to obtain a new population of size $Size$. The specific pseudo-code of the above iteration is shown in Algorithm  4.

Instead of updating the maintenance of the complete solution set during the iteration of approach execution, we choose to filter it at the end, in order to reduce the computational cost. When the maximum number of iterations is reached, a fast non-dominated sorting is performed on all complete solutions to select and output optimal solutions (specifically, non-dominated solutions). After that, the PDGA is finished. The specific pseudo-code of the optimal solution selection is shown in Algorithm  5.