Scalable and Optimal QoS-Aware Manufacturing Service Composition via Business Process Decomposition

Abstract

With the adoption of service-oriented manufacturing modes, more and more manufacturing services are released over manufacturing service platforms. As it is known, the problem of the QoS (Quality of Service)-aware manufacturing service composition is NP-hard. Thus, the optimization remains a challenging research issue, especially in the situation of large-scale manufacturing service data which arouse a scalability problem as well. To improve both the optimization performance and scalability of the QoS-aware manufacturing service composition, this paper proposes a scalable and optimal QoS-aware manufacturing service composition approach via business process decomposition. Specifically, the service composition process is decomposed by using a refined process structure tree (RPST). Moreover, an optimized service composition is achieved layer by layer based on the refined process structure tree in a bottom-up manner. For the atomic tasks or the compound tasks in the same layer of RPST, the corresponding QoS-aware service selection is optimized by calculating Skyline services, which can be carried out in parallel if necessary. When the optimization arrives at the root node, the complete service composition plans are derived. In our approach, the optimal manufacturing service candidates are picked out stage by stage. In this way, both the optimality and scalability of the whole approach can be guaranteed. Extensive experiments are conducted to verify the optimality and scalability of our approach.

1. Introduction

Industrial Internet is a promising technology combining the industrial system with Internet connectivity to significantly improve the product efficiency and reduce production cost by collaborating with intelligent devices, in which the advanced computing technologies are involved, such as cloud computing, edge computing, mobile computing, big data analysis, artificial intelligence, Internet of Things (IoT), and so on [1]. Thus, it is widely accepted that the Industrial Internet is the product of the deep integration of the new generation of information technologies and manufacturing. Due to the tremendous economic value of the Industrial Internet, numerous Industrial Internet platforms have been established, such as Predix from GE company, AWS IoT from Amazon, Azure IoT from Microsoft, MindSphere from Siemens, etc. [2]. As a result, manufacturing enterprises are able to publish their manufacturing resources as manufacturing services to Industrial Internet platforms from the perspective of industrial information sharing and integration. Further, with the service-oriented manufacturing paradigm, borrowed from service computing under a traditional Internet environment, each enterprise can participate in an entire manufacturing process by becoming a service provider, and can customize manufacturing operations online by becoming a customer [3]. This manufacturing paradigm accelerates the transformation from traditional large-scale production to customized production.

To meet the rich and diversified personalized requirements of users, the manufacturing processes of customized products are usually large and complex. That is, a manufacturing process may contain many tasks and multiple basic process structures. Consequently, a manufacturing process has to invoke multiple manufacturing services to complete the whole production of the customized product. Figure 1, for example, shows a composite service used in warehouse fire alarms, in which multiple services have to be combined to establish the powerful alarm service (based on [4]). Particularly, a warehouse fire alarm consists of different tasks, including temperature sensors, smoke detectors, infrared sensors, liquid immersion sensors, alarm bells, camera, scupper valves, and water sprinklers. These tasks will be accomplished by invoking various manufacturing services. As illustrated in Figure 1, there are more than ten tasks in the process. Each task should be bound to various manufacturing services with the same functionality but different QoS (Quality of Service) properties (such as cost, response time, reliability, and the like). Note that in our work, we assume that the QoS of service candidates have been obtained accurately and the estimation of QoS could be referred to other works, such as [5]. To generate a complete composited service, only one will be selected for each task from the corresponding service candidate pool. This procedure is referred to as the problem of the QoS-aware manufacturing service composition (QMSC). Nevertheless, the problem of the QoS-aware manufacturing service composition optimization is non-trivial due to the large number of manufacturing services with varying QoS. As stated in many studies, the service composition optimization problem is NP-hard in a strong sense [6]. Furthermore, the complex manufacturing process and tremendous service candidates render the problem even more difficult in reality compared with the service composition in the traditional service computing field. The complex manufacturing process will generate complex manufacturing service compositions, and the tremendous service candidates would expand the searching space of service composition solutions.

To solve the QoS-aware manufacturing service composition optimization problem, usually meta-heuristic algorithms are used by borrowing the rich research outcomes from traditional Web service composition approaches [7]. The main differences of these approaches mainly focus on taking different factors into account. However, their effectiveness and scalability are still limited. Therefore, they need to be further improved due to the complex manufacturing process and tremendous service candidates. In this work, we propose a Scalable QoS-aware Manufacturing Service Composition optimization approach via business process decomposition, named SQMSC, by which the problem is solved stage by stage. Specifically, the given manufacturing process is decomposed by using a refined process structure tree (RPST). Moreover, the optimized service composition is achieved layer by layer based on the refined process structure tree in a bottom-up manner. For a node (i.e., an atomic task or a composite task) in the RPST, the corresponding QoS-aware service selection is optimized by calculating Skyline services. When the optimization arrives at the root node of the RPST, the complete service composition optimization plans are derived. In our approach, inferior manufacturing service candidates are filtered out step by step. To summarize, this work makes the following three-fold contributions:

−

A QoS-aware manufacturing service composition optimization approach is proposed via business process decomposition, so that optimized service compositions are achieved layer by layer based on the refined process structure tree in a bottom-up manner.

−

This is the first time to introduce business process decomposition for manufacturing service composition. In this way, both the optimality and scalability can be ensured under large-scale manufacturing services.

−

Extensive experiments are conducted to verify both the optimality and scalability of our approach. Furthermore, the experimental results show the superiority of our approach compared with baselines.

The rest of this paper is organized as follows: Section 2 surveys the related work on both the traditional Web service composition approaches and manufacturing service composition approaches under an Industrial Internet environment. Section 3 proposes the framework of the QoS-aware manufacturing service composition. Section 4 introduces the details of the proposed QoS-aware manufacturing service composition optimization approach. At last, we conclude this paper and outline the future work in Section 5.

2. Related Work

Service composition is a procedure that individual services are choreographed into a complex and value-added composite service process [8]. The QoS-aware service composition is to select a service for each task in the composition process to form a composite service with the optimized overall QoS. It is often modeled as a composition optimization problem, which is known as a NP-hard problem [6].

In fact, the QoS-aware service composition has been widely explored for Web services or cloud services in the service computing field [9,10,11,12,13,14]. By reviewing the literature, the techniques for QoS-aware service composition can be classified into four categories: local maximization approaches, linear optimization approaches, approximation approaches, and Pareto-optimization approaches [15]. Next, we will briefly introduce them one by one and present a selection of corresponding representative literature. (1) Local Maximization Approaches. A popular local approach is dynamic programming through breaking down a process plan into separate divisible and indivisible parts. Furthermore, optimal solutions are searched for the individual parts [16]. Another local approach is to use the learning-depth-first search algorithm [17]. Some other local techniques are based on simple weighted summation for selecting the service with the optimal QoS utility for each abstract service. (2) Linear Optimization Approaches. These approaches apply linear optimization to model the QoS-aware service composition problem. Usually, linear integer programming is used by integrating the weighted summation technique, such as in [18,19]. Linear optimization is only feasible for a small set of service candidates. Nevertheless, it may take too much time to find the optimal composition in large-scale services. Sometimes, the best solution may never be returned. (3) Approximation Approaches. These approaches try to find the approximate solutions in a comparatively faster way [20]. Generally, some meta-heuristic algorithms are used, such as GA (Genetic Algorithm) [21], PSO (Particle Swarm Optimization) [11,22], ACO (Ant Colony Optimization) [23], ABC (Artificial Bee Colony Algorithm) [24], etc. (4) Pareto-optimization approaches. This category tries to find multiple optimal solutions with respect to one or more objective functions based on the approximation approaches by applying the Skyline technique for candidate service selection and optimal solution selection, such as [6,25]. Besides, Wu et al. [26] took the difference between non-functional attributes into account, and subsidiary functions between different candidate services as well. They propose to group candidate services with the same subsidiary function into the same category so that the number of candidates can be further reduced after Skyline computation. Alhosaini et al. [27] proposed a hierarchical Skyline-based approach to improve the efficiency of service composition by reusing varying levels of the Skyline service for the scenario that requests regarding the same or similar service as the subgraphs may occur frequently. Gavvala et al. [28] proposed an QoS-aware cloud service composition approach by integrating the eagle strategy with the whale optimization algorithm to ensure the proper balance between exploration and exploitation. Tarawneh et al. [16] proposed an intelligent cloud service composition method, in which Multistage Forward Search (MSF) is used to enhance the processes of service selection and composition via minimizing the number of integrated could services; the Spider Monkey Optimization (SMO) algorithm was employed for the overall QoS optimization.

Based on the rich research outcomes from service computing, service-oriented architecture is adopted in industrial manufacturing. As a result, the concept of cloud manufacturing has emerged in recent years. At the same time, many QoS-aware service composition approaches in the traditional service computing paradigm are borrowed for the manufacturing service composition due to the similarity of application scenarios. In cloud manufacturing, manufacturing processes or resources are virtualized as manufacturing services in the Industrial Internet, just like Web services which can be called over the Internet. Thus, manufacturing services can be managed and configured in an intelligent and unified way in the cloud. Furthermore, ubiquitous and on-demand network access is allowed [29]. By reviewing the works on QoS-aware manufacturing service composition, usually approximation approaches and Pareto-optimization approaches are borrowed, while some special factors in cloud manufacturing may be considered. Next, we will review some recent works on this. Chen et al. [4] formulated the QWSC problem as a multi-objective optimization model where either QoS performance or QoS risk is the objective. Furthermore, a $\epsilon$-dominance multi-objective evolutionary algorithm was developed to address the proposed model. Liu et al. [3] used clustering-based collaborative filtering algorithm to quantify the customer preference attributes. Furthermore, then an improved personalized-oriented non-dominated sorting genetic algorithm is introduced for multi-attribute manufacturing service composition optimization. Considering that the unstable QoS may affect the reliability of service composition, Xie et al. [7] proposed an efficient two-phase approach by integrating clustering and Chaos–Gauss-based PSO to derive service compositions with reliable and optimized QoS. Wang et al. [30] considered the historical collaborative relationship between manufacturing services to recommend manufacturing service compositions with high collaboration frequency in the past. The authors think that service composition with collaboration in the past will collaborate more effectively in the future. In the case study, SPEA-II and NSGA-II are used to generate manufacturing service compositions with both effect and high collaboration frequency indicators. Jin et al. [31] proposed a novel hybrid teaching–learning-based optimization algorithm to solve QoS-aware manufacturing cloud service composition problems, in which the advantages of uniform mutation, adaptive flower pollination algorithm, and the teaching–learning-based optimization algorithm are integrated. Besides, there are still some other works on manufacturing service composition, while their core idea still focuses on meta-heuristic algorithms by taking different factors into account.

From the above literature review, it can be known that although some service composition approaches based on the QoS have been proposed to fulfill the user’s requirement, their performance is still limited and needs to be further improved due to the following reasons: (1) the convergence of meta-heuristic algorithms may take too much time or cannot be insured in a limited time under large-scale manufacturing services; (2) these approaches may fall into a local optimal solution or the approximate solution is far from the optimal solution under the large solution space. Therefore, if the two problems could be alleviated, the performance of the QoS-aware manufacturing service composition can be improved further. The above observations motivate our work.

3. Framework of QoS-Aware Manufacturing Service Composition Optimization Approach

The objective of the QoS-aware manufacturing service composition is to select appropriate services fulfilling the user’s overall QoS constraints in a manufacturing process to derive the service composition with the optimized overall QoS. The preferences of users are usually described as constraints over QoS properties, for example, the cost should be no more than USD 20, the response time should be less than two minutes, and the like. However, theoretically, it is commonly accepted that the QoS-aware manufacturing service composition cannot be solved within a reasonable time [32] because the size of the possible service composition plans derived by service selection for tasks may be, in general, exponentially enlarging.

In this work, we propose a QoS-aware manufacturing service composition optimization framework via business process decomposition, which is scalable to complex manufacturing processes and large-scale manufacturing service candidates. Figure 2 illustrates the proposed framework for the QoS-aware manufacturing service composition. Note that our work primarily focuses on QoS-aware service composition optimization, so we assume that the service discovery in the framework has been carried out. Thus, our framework mainly contains three components: QoS Normalization, Decomposition of Business Process, and Service Composition Layer by Layer based on RPST. It is worth mentioning that QoS normalization and decomposition of business process can be preprocessed offline in advance to accelerate the overall service composition procedure.

Here, we introduce the proposed framework in detail. Firstly, based on the discovered manufacturing service candidates for each task, QoS normalization can be achieved by the widely used min–max normalization method [33]. At the same time or before that, the manufacturing business process provided by the active user or by the Industrial Internet platform can be decomposed by the technique of refined process structure tree (RPST). As a result, a corresponding refined process structure tree is derived, which is employed by a service composition component. In Figure 2, the composition component is a loop. Specifically, for each layer in RPST, if a node is a compound task, then QoS aggregation should be calculated. Further, for each node in this layer, the Skyline services are calculated. Furthermore, the Skyline services will be selected to compose a compound service. This process will be carried out again and again, and more coarse-grained compound services will be generated step by step, until the whole service composition is derived, i.e., the final compound service is just the required service composition. As for the toy example in the framework, the business process is decomposed into a RPST with three layers. Consequently, the service composition component will loop for three times to generate the final optimized service composition plans, i.e., this component is used iteratively for different layers. Generally, the final compound service is a sequential structure since the root of the RPST is a sequence node.

4. Scalable QoS-Aware Manufacturing Service Composition Optimization via Business Process Decomposition

This section presents the details of the proposed scalable QoS-aware manufacturing service composition optimization approach. First, the QoS properties of manufacturing services are normalized and the given manufacturing process is decomposed into a process structure tree description. Then, the service composition can be achieved by iteratively selecting optimal services for each (compound) task based on the RPST and Skyline services.

4.1. QoS Normalization

There are mainly two reasons for QoS normalization. To begin with, different QoS properties have different measurement units and scales. For instance, response time is measured by the time that a service takes to react to a given input, and the unit is usually a second or a minute; the cost is measured by how much it takes to invoke the service, and the unit may be U.S. dollar, RMB, or the like. Moreover, there are usually two types of QoS properties, positive and negative. As for positive QoS properties, the larger the value, the better the quality (e.g., availability); as for the negative QoS properties, however, the large the value, the worse the quality (e.g., response time). Consequently, it will cause serious problems when two different QoS properties are compared with each other or aggregated to derive an overall QoS value for evaluation. Based on the above observations, different QoS properties should be normalized to the same range without explicit units. In this work, QoS normalization is achieved by the max–min normalization technique, as used in the previous literature [34]. To be more specific, the max–min normalization formulas are shown in Formula (1) and (2), and used for the normalization of positive and negative QoS properties, respectively.

$$Q_{ij}^{{}^{\prime }}=\left\{\begin{array}{cc}\frac{Q_{ij}-Q_j^{min}}{Q_j^{max}-Q_j^{min}}& Q_j^{max}\ne Q_j^{min}\\ 1& Q_j^{max}=Q_j^{min}\end{array}\right.$$

(1)

$$Q_{ij}^{{}^{\prime }}=\left\{\begin{array}{cc}\frac{Q_j^{max}-Q_{ij}}{Q_j^{max}-Q_j^{min}}& Q_j^{max}\ne Q_j^{min}\\ 1& Q_j^{max}=Q_j^{min}\end{array}\right.$$

(2)

where $Q_{ij}$ represents the $j^{th}$ original QoS property value of manufacturing service $s_i$, $Q_{ij}^{{}^{\prime }}$ is the corresponding QoS property value after normalization, $Q_j^{max}$ and $Q_j^{min}$ are the maximal value and minimal value of a QoS property, respectively. After normalization, the value of a QoS property ranges from 0 to 1, and the larger the better for all the QoS properties.

4.2. Decomposition of Manufacturing Business Process

A service composition is often reflected as or driven by a business process at the demand application layer. Thus, from the perspective of the graph description, a service composition process is just like a workflow. Here, we introduce decomposing a workflow graph into a hierarchy of sub-workflows. The sub-workflows are the subgraphs with a single entry and a single exit of control. Since the control flow of a business process can often be modeled as a workflow graph, we also refer to workflow decomposition as business process decomposition. In this work, they are used interchangeably.

Before introducing the algorithm of computing the refined process structure tree, we present some related notions. Workflow graphs are based on two-terminal graphs, which are a directed graph G without self-loops such that there is an unique source node s and a unique sink node $t\ne s$, and each node v is on a direct path from s to t. Let W be a subset of nodes of G. Two nodes $u,v\notin W$ are connected without W if there is a path that contains u and v but no node $w\notin W$. Consequently, a graph without self-loops is k-connected, $k>0$, if it has at least $k+1$ nodes, and for every set W of $k-1$ nodes, any two nodes $u,v\notin W$ are connected without W.

Based on the above notions and in reference to [35], we introduce the main procedure of computing the refined process structure tree, as follows: Step 1: Detect the triconnected components. Step 2: Analyze each triconnected component to determine whether the respective component subgraph is a fragment. Step 3: Create the missing canonical fragments and merge the triconnected components that are not fragments. As the canonical fragments do not overlap with each other, they form a hierarchy structure. Thus, the refined process structure tree is the tree of canonical fragments of a process model G, such that the parent of a canonical fragment F is the smallest canonical fragment of G that properly contains F. It is proved in [35] that the decomposition is unique and modular, and it can be computed in linear time.

Take the workflow in Figure 3 as an example, several canonical fragments can be derived by performing the algorithm for computing the RPST, i.e., Seq1, Seq2, Xor1, and And1, which are shown in Figure 4. Furthermore, a RPST description corresponding to the workflow model in Figure 3 is illustrated in Figure 5 in the form of a tree hierarchy. It is worth mentioning that the workflow decomposition theory can be also generalized to arbitrary process models, as the extended work [36] states. The decomposed RPST has the same structure semantics as the business process model in BPMN but with a different description. Thus, they can be converted into each other without a loss of semantics. With the process structure tree, an effective and efficient service composition algorithm can be achieved, which will be presented in Algorithm 1 in Section 4.3 later.

4.3. QoS-Aware Service Composition Based on RPST

After QoS normalization and decomposition of the manufacturing service process, our approach goes to the service composition based on RPST, as mentioned in Figure 1. This part involves QoS aggregation, the Skyline calculation, and the service composition algorithm based on QoS aggregation and the Skyline calculation. Thus, before introducing the service selection optimization for composition service, we will introduce QoS aggregation and the Skyline calculation first in the following section.

QoS Aggregation. To derive the QoS value for a compound task (i.e., composite service), appropriate QoS aggregation is required. However, it is not appropriate to use one unified QoS aggregation function, since there may be different composition structure patterns, such as sequential, parallel, conditional, or loops. Let $CS$ be a composite service denoted by $CS=(s_{1,i},s_{2,j},\cdots ,s_{m,k},\cdots ,s_{n,l})$ where $s_{m,k}$ is the $k^{th}$ concrete candidate service of the $m^{th}$ abstract service. Service composition is to select a concrete service for each abstract service (i.e., task) in the target manufacturing process to form a compound service under the QoS constraints. The QoS aggregation of $CS$ is the overall QoS of all the selected services. The QoS vector of $CS$ is described as $QoS\left(CS\right)=(Q_1\left(CS\right),Q_2\left(CS\right),\cdots ,Q_d\left(CS\right))$, where d is the dimension size of the QoS vector, and $Q_i\left(CS\right)$ indicates the $i^{th}$ QoS property value of $CS$, which is obtained by the aggregation function of the $i^{th}$ QoS property values from all the selected services. In this work, four basic process structures and their QoS aggregation functions are considered: (1) Sequence, (2) Switch, (3) Parallel, and (4) Loop, which are illustrated in

Table 1. QoS Aggregation Functions.

QoS Properties/Structures	Response Time	Cost	Availability
Sequence (Seq)	${\sum }_{i=1}^{n}T\left(s_i\right)$	${\sum }_{i=1}^{n}C\left(s_i\right)$	${\prod }_{i=1}^{n}A\left(s_i\right)$
Switch (Xor)	${\sum }_{i=1}^n{p}_i\times T\left(s_i\right)$	${\sum }_{i=1}^n{p}_i\times C\left(s_i\right)$	${\prod }_{i=1}^n{p}_i\times A\left(s_i\right)$
Parallel (And)	$Ma{x}_{i=1}^{n}T\left(s_i\right)$	${\sum }_{i=1}^{n}C\left(s_i\right)$	$Mi{n}_{i=1}^{n}A\left(s_i\right)$
Loop (Loop)	$T\left(s_i\right)\times k$	$C\left(s_i\right)\times k$	${\prod }_{i=1}^{k}A\left(s_i\right)$

, where $p_i$ denotes the probability of service $s_i$ being selected in the process structure, and k indicates the number of executions in a loop structure. As shown in Table 1, different QoS properties have different aggregation methods. To summarize, there are mainly four types of aggregation functions: Summation, Multiplication, Minimum, and Maximum [7].

Skyline Calculation. Due to the large number of service candidates for each task, it would be more efficient for service selection if the number could be reduced while not comprising the quality. Consequently, we use the Skyline query technique from database theory to select the optimal services preliminarily [34], thus, the service number for service selection could be reduced greatly. Since the Skyline services are the ones that are not dominated by any other services from the QoS perspective, they are the better ones on QoS. Referring to [37], we present the definition of dominance relation between two services and Skyline services as Definition 1 and Definition 2, respectively, as follows.

Definition 1. (Dominance). 

Given two services, $s_i,s_j\in S$ characterized by d-dimension quality values, $s_i$ dominates $s_j$, denoted by $s_i\succ s_j$, iff $\forall p\in [1,d]:Q_p\left(s_i\right)\ge Q_p\left(s_i\right)$ and $\exists p\in [1,d]:Q_p\left(s_i\right)>Q_p\left(s_i\right)$.

Definition 2. (Skyline Services). 

The Skyline of S, denoted by $S_{SL}=\{s_i\in S|\nexists s_j\succ s_i\}$, consists of the services in S that are not dominated by any other services in S.

The process of the Skyline service calculation is presented in Algorithm 1 with the candidate service set C as the input. The Skyline services set $S_{SL}$ is initialized as an empty set in line 1. Lines 4–9 determine whether a service is a Skyline service or not based on a dominance relationship. If the service is a Skyline service, then it will be appended into $S_{SL}$, as described in lines 10–12. Finally, $S_{SL}$ is returned as the output. In Algorithm 1, pairwise comparisons are needed for the determination. Thus, the time complexity of Algorithm 1 is $O(\mid C{\mid }^2)$, where $\mid C\mid$ is the number of candidate services.

Service Composition Algorithm. Based on Skyline services, we select the optimal service candidates for atomic tasks. The preliminary service selection for different atomic tasks can be achieved in parallel. Based on QoS aggregation methods and the Skyline calculation, next we select the optimal compound service candidates for compound tasks. Furthermore, the overall service composition can be achieved by service selection for compound tasks according to the RPST in a bottom-up manner. In such a way, more and more complex compound services can be derived gradually. Similarly, the preliminary service selection for different compound tasks at the same level of the RPST can be achieved in parallel as well. Finally, the largest or most complex compound services can be generated by service selection for the root node. The proposed service composition algorithm is presented in Algorithm 2. Specifically, lines 2–3 and 8–10 can be achieved in parallel as mentioned above. The main computation cost is taken by the Skyline calculation. The average number of service candidates for each task is N, M for each compound task, the number of atomic tasks in the manufacturing business process is T, and there are K layers with the compound task in the RPST. Then, the overall complexity of Algorithm 2 is $O(N^{2}T+M^{2}K)$, where $N>M$ and $T>K$ hold in practice. Thus, the final complexity of Algorithm 2 should be $O\left(N^{2}T\right)$. Furthermore, the actual running time can be greatly alleviated further in practice by applying parallel computing techniques.

Algorithm 1 Skyline Service Calculation

Require:  Candidate Services Set C Ensure:  Skyline Service Set $S_{SL}$   1: $S_{SL}\Leftarrow \varnothing$;   2: for$s_i\in C$do   3:    $is Skyline Service\Leftarrow True$;   4:    for $s_j\in C$ do   5:      if $s_j\succ s_j$ then   6:         $is Skyline Service\Leftarrow False$;   7:         break;   8:      end if   9:    end for 10:    if $is Skyline Service=True$ then 11:      $S_{SL}\Leftarrow S_{SL}\cup \left\{s_i\right\}$; 12:    end if 13: end for 14: return$S_{SL}$;

Algorithm 2 Service Composition

Input:  Candidate service set $S_i$ for task $T_i$; QoS data for all the service candidates; RPST derived from manufacturing business process model Output:  Optimal service composition plans   1: QoS normalization for all the service candidates;   2: Calculate Skyline services for each atomic task in the RPST;   3: Select Skyline services for each atomic task in the RPST;   4: for each level in RPST do   5:    if $N_{st}\ge n_0$ then   6:      Apply a meta-heuristic algorithm for the service selection of the compound task;   7:    else   8:      Calculate QoS aggregation for the compound task;   9:      Calculate Skyline compound services for compound tasks in the level of RPST; 10:      Select Skyline compound services for compound tasks in the level of RPST; 11:    end if 12: end for 13: return Optimal service composition plans;

Usually, there are only two or three subtasks for a compound task. However, there also may be exceptions. Considering such a situation, there may be many candidates for a compound task if there are many subtasks. As a result, the computation overhead would be high when calculating the Skyline compound services for the compound task. Under such a situation, a meta-heuristic algorithm is also a good alternative for the service selection of the compound task since there is only a small number of tasks. Thus, we add a priori rule in the service selection of a compound task. If the number of subtasks is greater or equal to $n_0$, then a meta-heuristic algorithm is applied for the service selection of the compound task. Otherwise, we calculate the Skyline compound services for selection. Therefore, we add a condition judgment before the service selection of a compound task, as shown in lines 5–10 in Algorithm 1. In this work, we set $n_0=5$ as the default. However, $n_0$ should be adjusted according to the actual computation condition. As for the example process model in Figure 3, the final compound task, i.e., the root node, has just five subtasks as shown in Figure 5. Thus, we consider employing a meta-heuristic algorithm to achieve the service selection of the compound task Seq1. However, a compound task with several subtasks can also be decomposed into several substructures of the same kind. For example, Seq1 can be decomposed into four sequence structures, as shown in Figure 6. In this way, the service selection for the compound task can be accelerated. Similarly, Xor1 in Figure 5 can be further decomposed into two switch structures if necessary, as shown in Figure 7.

5. Evaluation

This section evaluates the proposed approach from two perspectives: optimality and scalability. Several representative baselines are included for comparison in the experiments. All experiments are implemented on a PC with AMD Ryzen 5, CPU 2.38 GHZ, and 16 G RAM, running on Windows 10 x64 with Python 3.9.

5.1. Experimental Setup

Dataset. In the research field of manufacturing service composition, there is no publicly available dataset. Thus, simulated datasets are usually generated for evaluation, which have been used in many studies [7]. However, to make the experimental results more solid, we utilized a public real-world dataset, named QWS [38], which is often used for the evaluation of traditional QoS-aware Web service compositions or recommendation approaches [27]. The dataset involves eight QoS properties on 2507 Web services. In practice, only two or three QoS properties are usually considered. Thus, we consider four QoS properties at most in the experimental setting. The characteristics of the resulting QWS dataset are presented in

Table 2. Characteristics of the Resulting QWS Dataset.

#	QoS Property	Minimum	Maximum	Average	+/−
1	Response Time	37.00	4989.67	383.83	−
2	Availability	0.07	1.00	0.81	+
3	Throughput	0.10	43.10	9.03	+
4	Reliability	0.33	0.89	0.69	+

+: positive attribute, −: negative attribute.

. Specifically, the four QoS properties are Response Time, Availability, Throughput, and Reliability. Response Time is a negative attribute, while the others are positive attributes. However, all QoS properties will become positive attributes after QoS normalization. Therefore, in our work, the QoS data of Web services are taken as the QoS data of manufacturing services, and are randomly assigned to the tasks of the given manufacturing process.

The example abstract manufacturing process in Figure 3 will be used in our experiments. Since there are five subtasks for the root node, a meta-heuristic algorithm is also used with a small number of tasks and service candidates according to Algorithm 1. Note that each QoS property of the whole target service composition can be taken as an objective to be optimized in the service composition optimization. Furthermore, multiple objectives may conflict or correlate with each other. Therefore, this work derives the Pareto service composition solutions instead of generating a single solution.

Evaluation Metrics. The objective of the manufacturing service composition approach is to find optimal service composition plans under the QoS constraints in an efficient way. Thus, we evaluate the proposed approach from its optimality and scalability. More specifically, optimality is estimated by the average optimization ability of multiple objectives. Thus, all the objectives are taken as equal importance in our work, while, of course, personalized weights can also be set by users if necessary. Furthermore, scalability is estimated by the efficiency of solving process, i.e., the computing overheads. Thus, the scalability can be estimated by the running time with the vary of data size. As for the experimental results, they will be the average value of 30 rounds if there is randomness involved in some comparative baselines. Furthermore, we also investigate which component takes up more running time by estimating the running time of each component in the proposed approach.

Comparative Approaches. As reviewed in Section 2, the state-of-the-art approaches for manufacturing service composition usually use meta-heuristic algorithms with single or multiple objectives. Furthermore, different factors may be considered for different application scenarios. However, the essence of these approaches is multi-objective optimization. Therefore, we select three representative meta-heuristic algorithms used for QoS-aware manufacturing service composition as baselines, i.e., GA (Genetic Algorithm) [3], PSO (Particle Swarm Optimization) [7], and TLBO (Teaching–Learning-Based Optimization) [31]. Since the Skyline technique is used in our approach, we also compare meta-heuristic algorithms with Skyline services in the preliminary service selection of atomic tasks. Thus, the usefulness of Skyline services for service composition can be estimated. As a result, we obtain three variant approaches based on the three meta-heuristic algorithms, i.e., Skyline+GA, Skyline+PSO, Skyline+TLBO. Besides, there is another variant approach without using a meta-heuristic algorithm in SQMSC, namely, SQMSC-MH. In the experiment, we use GA in SQMSC, while other meta-heuristic algorithms can also be the alternatives. To summarize, the representative baselines used in our comparison experiments are listed in

Table 3. The Baselines for Comparison Experiments.

#	Baselines	Description
1	GA	This approach uses a genetic algorithm.
2	PSO	This approach uses a particle swarm optimization algorithm.
3	TLBO	This approach uses a teaching–learning-based optimization algorithm.
4	Skyline+GA	This approach uses a genetic algorithm with initial Skyline services for each task.
5	Skyline+PSO	This approach uses a particle swarm optimization algorithm with initial Skyline services for each task.
6	Skyline+TLBO	This approach uses a teaching–learning-based optimization algorithm with initial Skyline services for each task.
7	SQMSC-MH	This approach is a variant of SQWSC by not using a meta-heuristic algorithm, i.e., select the Skyline (compound) services.

.

5.2. Performance Evaluation

We investigate the performance of our approach in comparison with several representative baselines. The given manufacturing process for experiments in our work has been illustrated in Figure 3. For the sake of simplicity, we suppose all the service candidates have satisfied the QoS constraints. Thus, QoS constraints are neglected in our experiments. By default, we set the number of QoS properties as 3, the number of service candidates for each task as 40, and the number of populations for meta-heuristic algorithms as 100. Thus, two series of experiments are designed, as shown in

Table 4. Parameter Settings.

Parameter	Serie A	Serie B
# QoS Properties	$\{2,3,4\}$	40
# Service Candidates	3	$\{20,40,60,80,100\}$

. Specifically, the number of QoS properties varies from 2 to 4, and the number of service candidates for each task is set as 20, 40, 60, 80, and 100, respectively. When one parameter varies, the other parameters are set as the default.

Optimality. We evaluate the optimality by the average optimization ability of multiple objectives. The optimality of our approach and the baselines are shown in Figure 8 and Figure 9. As can be seen from Figure 8, the optimality of all the approaches slightly decreases with the increase in the number of QoS properties because the number of QoS properties would increase the difficulty of searching for the optimal solutions. However, there is little impact on the optimality of SQMSC-MH, since it can always find the best optimal solutions. The optimality of SQMSC-MH is most close to that of SQMSC. On the whole, SQMSC and SQMSC-MH have better optimality constantly compared with other baselines. Compared with meta-heuristic algorithms (GA, PSO, and TLBO), meta-heuristic algorithms with Skyline (Skyline+TLBO, Skyline+PSO, Skyline+GA) have the better optimality even though their performance may be very close sometimes, which demonstrates that the Skyline technique is helpful in improving the optimality of meta-heuristic algorithms. As can be seen from Figure 9, the optimality of all the approaches slightly increases with the increase in the number of service candidates. This is because more service candidates will generate more optimal solutions. Simultaneously, the solution space is also enlarged to some extent. In general, SQMSC-MH has the best optimality, followed by SQMSC, and other baselines show the worse optimality. Even though the order of optimality in Figure 8 is similar to Figure 9, the superiority of the proposed approach in Figure 9 is more obvious than that in Figure 8, which verifies that our approach is adaptive to large-scale datasets in terms of optimality. Furthermore, among the meta-heuristic algorithms, GA shows a little better compared with PSO and TLBO on the whole. GA has more parameters for adjustment. Therefore, it is more likely to find the optimal solutions by fine-tuning parameters. However, this is also the disadvantage of GA. In contrast, there is no parameter setting in TLBO, so it is easily used in reality. Furthermore, PSO has fewer parameters than GA.

Scalability. The running time of a meta-heuristic algorithm is measured by the duration to the convergence time. The scalability of our approach and the baselines are illustrated in Figure 10 and Figure 11. As shown in Figure 10, the runtime of most approaches slightly increases with the increase in the number of QoS properties, while SQMSC-MH has a rapid increase. Furthermore, SQMSC shows the smallest increase. More specifically, SQMSC has the shortest runtime, followed by meta-heuristic algorithms and their variants. Moreover, the scalability gap among the comparative approaches becomes more obvious with the increase in the number of QoS properties. As shown in Figure 11, the runtime of all approaches increases with the increase in the number of service candidates. Furthermore, the increasing trend and order are similar to that in Figure 10. With the increase in service candidates, the solution space is enlarged. As a result, it would take more time to find the optimal solutions in the larger solution space. In general, SQMSC has the best scalability compared with the other baselines. Even though the runtime of SQMSC increases with the increase in the number of service candidates, just like the other baselines, the increasing rate is much lower, which can be neglected almost. The runtime of SQMSC-MH shows a rapid increase as the number of QoS properties increases. Compared with meta-heuristic algorithms (GA, PSO, and TLBO), meta-heuristic algorithms with Skyline (Skyline+TLBO, Skyline+PSO, Skyline+GA) have better scalability, which demonstrates that the Skyline technique is helpful in improving the scalability of meta-heuristic algorithms. Furthermore, among the meta-heuristic algorithms, GA has the best scalability, followed by TLBO and PSO on the whole. Since GA has more parameters for adjustment, it could find the optimal solutions earlier.

Beside the scalability study of the comparative approaches, we also investigate the runtime of each component in SQMSC. Since QoS normalization and the decomposition of business process can be computed offline, we mainly investigate three sequential components in Algorithm 1, i.e., the runtime of service selection for atomic tasks, the runtime of service selection for compound tasks, and the runtime of service selection by using the meta-heuristic algorithm. The runtime variation of each component in Algorithm 1 is shown in Figure 12 and Figure 13. As can be seen from the figures, the runtime of each component increases with the increase in the number of QoS properties or the number of service candidates. The increasing rate in Figure 13 is larger than that in Figure 12. As for the example manufacturing process, the runtime of service selection with the meta-heuristic algorithm GA is the longest, followed by the runtime of service selection for compound tasks, and the runtime of service selection for atomic tasks. In this example process, there are nine atomic tasks and four compound tasks, in which one task is applied with the meta-heuristic algorithm and three tasks are applied with Skyline service selection. Since parallelism can be used in the service selection for atomic tasks and compound tasks in our approach, their runtimes are relatively much lower. Typically, the runtime in service selection for atomic tasks can nearly be neglected because it is too low, close to zero. As can be seen from Figure 12 and Figure 13, the blue parts (at the bottom) nearly disappear. To summarize, the runtime of the proposed approach is desirable, and it is scalable to large-scale datasets.

Typically, we present the results of comparative approaches under both optimality and scalability with the default parameter settings. The mean and variance of 30 rounds are illustrated in

Table 5. Performance Comparison with Baselines Under the Default Parameter Settings.

Approaches	Optimality	Scalability
GA	63.5257 ± 7.1428	43.7523 ± 4.1821
PSO	42.9009 ± 2.4821	62.7209 ± 4.9327
TLBO	55.2482 ± 3.4008	50.8838 ± 3.2382
Skyline+GA	66.4522 ± 3.5141	28.1245 ± 2.9564
Skyline+PSO	55.7582 ± 1.8293	51.0326 ± 3.1694
Skyline+TLBO	62.5074 ± 2.1741	25.3899 ± 2.6176
SQMSC-MH	91.7786 ± 0	36.1615 ± 0
SQMSC	82.2184 ± 2.7958	12.9858 ± 2.1093

. The optimality of GA, PSO, TLBO are relatively close, but the performance of GA is relatively better than PSO and TLBO. Furthermore, both optimality and scalability can be improved to some extent by integrating the preliminary service selection for atomic tasks based on Skyline services before employing meta-heuristic algorithms. Moreover, the results of SQWSC are stable comparatively. Furthermore, if no meta-heuristic algorithm is included in SQMSC, the variance would be zero, i.e., the results are totally deterministic, which can be proven by the results of SQMSC-MH. As for SQWSC and SQMSC-MH, they have much better optimality than other baselines. However, the efficiency of SQMSC is much better than that of SQMSC-MH because SQMSC-MH would take more time relatively for the calculation of Skyline services when a compound task has more than $n_0$ subtasks. The fact that a compound task contains more subtasks indicates that there will be more compound service candidates for the Skyline calculation. Based on the experimental results and analysis, it can be summarized that the proposed approach can obtain more optimal service composition plans with predominant scalability compared with the baselines.

6. Conclusions

In this work, we propose a scalable QoS-aware manufacturing service composition optimization approach via business process decomposition. With the decomposed process structure tree, optimal service composition can be achieved locally. Consequently, more and more large compound service compositions can be derived step by step until the overall service composition has derived. This paper is the first attempt to use the process structure tree to accelerate the optimization of service compositions. Simultaneously, the optimality can be ensured. More importantly, our approach can be also applied in large-scale datasets. Extensive experiments are conducted to verify both the optimality and scalability of the proposed approach by comparisons with the representative baselines. Furthermore, the experimental results demonstrate that the proposed approach can greatly improve the overall QoS of the resulting service composition plans with much less running time, indicating that reducing the number of service candidates—with the Skyline technique and service composition for compound tasks with RPST—can enhance both the optimality and scalability of the QoS-aware manufacturing service composition optimization.

In our work, $n_0$ is set as 5 in Algorithm 2, considering the used dataset and computation configuration. However, it should be adjusted if there is a different dataset and computation configuration. Thus, understanding how to set an appropriate value for $n_0$ automatically could be a problem to be solved in our future work. Moreover, in future work, we would consider more flexible manufacturing processes, in which multiple or a certain number of services are needed for implementing an atomic task collaboratively.