Serial reduction optimization research of complex product workflow’s accuracy under the time constraint

Abstract

Model complex production business contains the attributes of completion time, accuracy, and so on; these factors influence each other; and pursuing the balance of these factors is the core idea of the article. Due to the problems of low accuracy or more completion time which may be caused by the traditional algorithm, the research group proposed the serial reduction algorithm which can achieve higher accuracy under deadline for the business. The algorithm sets the active portion for each task and uses the inverse iterative way to obtain a path that can balance both the completion time and the accuracy. By the case analysis, compared with the traditional unidirectional objective algorithm, serial reduction algorithm can optimize the accuracy under the deadline. Finally, the article analyses the parameters that can affect the algorithm performance; the experiment shows that serial reduction algorithm applied to the workflow is feasible and effective, which has the simple advantage.

Keywords

Workflow schedule temporal consistency accuracy optimization deadline

Introduction

Modern business workflow technology is based on network flow which uses service as the basic elements to framework and uses collaborative services to complete the business. Business process is abstracted by workflow system which divides the process into many steps; combined with the service attributes, finally, the system determines the best completion path. In the workflow system, selecting the service in each task is extremely important because it determines the efficiency and completion quality of the entire business. Selecting a reasonable service in the task plays an important role on the effective implementation of the entire business process.^1,2

To balance completion time and accuracy is the goal of modern workflow optimization.³ The project process as a whole is divided into several steps, usually since the problems exist in one or several steps, such as pursuing the efficiency but neglecting the quality of service or pursuing the quality of service but delaying the completion time, which make the completion time and the completion quality of the entire project imbalanced.^4,5 Therefore, pursuing efficiency unilaterally will result in low accuracy rate; on the contrary, pursuing service accuracy unilaterally will affect the completion time of complex products. To solve this problem, this article provides a high-quality algorithm that can be applied to ensure the workflow of complex products in time as well as the highest quality, which implements serial reduction optimization of completion path quality. Comparing with other algorithms that aim to minimize the completion time or maximize the completion accuracy, serial reduction algorithm makes a balance between both of them. Serial reduction algorithm maps the whole process task and its relevant services to a directed acyclic graph (DAG). Passing the hierarchical strategy, it divides activity section to each task, gets the most accuracy rate of each task iteratively when the task starts at different times, and gets the optimization path by the previous calculation process finally.

Relevant works

The workflow model contains tasks and services; the services carry the attributes of time, cost, and quality in the workflow model; a reasonable link among the services plays a key role to optimize the operation of the task. With the continuous expansion of the workflow structure, optimizing the workflow no longer regards completion time as fundamental, but has a higher demand for its cost or quality. Buyya et al.^6,7 proposed three kinds of heuristic algorithm to reduce the cost of constraint time; V Khajehvand et al.⁸ proposed a scalable cost-time trade-off (SCTT) model for scheduling workflow tasks; P Czarnul⁹ selected a capable service for each task so that a global criterion is optimized such as a product of workflow execution time and cost, a linear combination of those, or minimization of the time with a cost constraint; Rodenburg et al.¹⁰ minimized the cost of workflow execution under deadline constraints in the a mathematical programming language (AMPL) model. Kim et al.¹¹ used a resource consolidation in a parallel manner to decrease the cost with the deadline assurance and maximized the service quality.

Based on the problem of realizing goals under constraint time, Chinese researchers also carried out corresponding research. Liu et al.¹² adopted the priority factor technology to optimize time and cost in the workflow and analyzed the differences in several algorithms. Wu et al.¹³ proposed the method of the management for the multi-tenant uses of SaaS and created the cost optimization strategy with Markov chain; Liang et al.¹⁴ proposed a new dynamic scheduling method; Zhang and Qi¹⁵ proposed a bi-directional scheduling algorithm; and Cao et al.¹⁶ proposed optimal scheduling method based on particle swarm optimization.

Visibly, when making the scheduling for the business workflow, multiple factors need to be considered; how to optimize the completion quality in constraint time is also a hot research area.

Problem descriptions

Definition of workflow model

The workflow model is a reasonable arrangement for business process; it can effectively arrange the service to the corresponding set and make the complex product process to a DAG. Simply put, workflow model is a process of using all information in the business to compose the graph.

Definition 1: Task pool

It refers to a set of all tasks in a given business process. If indicated by P, then P = (p₁, p₂, …, p_i, …, p_n).

Definition 2: Service pool

It refers to the set of all services corresponding to task p_i in set P. If represented by S_i, then S_i = (s₁, s₂, …, s_j, …, s_m).

Definition 3: Rank of service pool

Refer to the number of services in set S_p for any p in set P, represented by r_p.

Definition 4: Workflow model

If the model is represented by W, then W can be formalized as a binary group W = (P, S_p), p∈P, P is the task pool, and S_p is the service pool of task p. In a specific business process, ordering relation exists between tasks p_i and p_j (i ≠ j), and each task p corresponds to a service pool S_p, and through the services it coordinates with each other reasonably between tasks to implement the entire workflow.¹⁷

A typical complex product workflow model is shown in Figure 1. In the model, task set P represents all the tasks of the business, service set S_p (p∈P) represents the corresponding database resources, and s_pk indicates that task p is completed by the kth service in set S_p. Start indicates the start of the process, p_s represents the virtual task, and S_s represents the set of services; then p_s and S_s point to Start. End indicates the end of the process, p_e represents the virtual task, and S_e represents the virtual set of services; then p_e and S_e point to End.

Figure 1.

Workflow model.

Definition 5: Workflow graph

The graph that uses the DAG for combining with task pool R and service pool S is used to describe the business process clearly. It is shown as G = {s_pk, E}, p∈P, 0 < k ≤ r_p; s_pk indicates that task p is completed by the kth service in set S_p; E represents a directed edge and indicates the order between tasks; the next task can begin only when the previous task is completed. In the workflow graph (WFG), the node which does not have a precursor is the start node, represented as Start; p_s represents a virtual task, S_s represents a virtual set of services, then p_s and S_s point to Start; the node which does not have a successor is the end node, represented as End; p_e represents a virtual task, S_e represents a virtual set of services, then p_e and S_e point to Start.¹⁸

Definition 6: Service attribute

It refers to the attribute parameter that service s_pk owns in WFG G, represented as pt_pk = (t_pk, a_pk), p∈P, 0 < k ≤ r_p; t_pk represents the time of using service s_pk to complete task p and a_pk represents the accuracy of using service s_pk to complete task p.

Generation algorithm of WFG

The WFG can effectively simulate the business process with its tasks and services; it plays a vital role for safety personnel to own the entire working path in detail. On the basis of previous studies,^19,20 combining with workflow attributes, it gives the generation algorithm of WFG as follows:

For the business process, divide the task set P, arrange all the tasks in order, and plan out service set S_p which corresponds to task p.

Start at the beginning node, add the services of the first task into the same layer, and connect Start with the services in order.

Discover the next task, add all the corresponding services into the same layer, and connect with the services of the previous layer in order.

Repeat step (3) until no task and make the services of the last layer connect to the final state End in order.

Add attributes pt_pk to all services s_pk.

Complete the WFG.

According to the above policy, it can design the pseudo-code of generation algorithm of WFG as follows:

Input: parameters: s_pk; pt_pk; Start; End; len; r_p; //len is the number of the task set P

Output: WFG G

Algorithm 1.
Service_queue = NULL, G = NULL, len = P.length;
For (int p = 1; p < = len; i ++) {
For (int k = 1; k < = r_p; k ++) {
Insert (Service_queue, s_pk)}}; // all services were added into queue in sequence;
p = 1;
For (k = 1; k < = rp; k++) {
Delete (Service_queue, s_pk);}
//the services of task 1 dequeue;
ADD spk TO G;//add the services spk to G;
Connect (Start, s_pk);} // connect the Start with the services spk of the first task;
For (p = 2; p < = len; p++) {
For (k = 1; k < = r_p; k++) {
Delete (Service_queue, s_pk);}}//the services of different tasks dequeue in order;
ADD s_pk TO G;//add the corresponding
Return G;
The time complexity of the algorithm is O (mⁿ).

Example of generation algorithm of WFG

Assume task set P in the workflow model is {α, β, γ, δ}, and each task has a corresponding service pool S_α, S_β, S_γ, S_δ; then using generation algorithm of the WFG and inputting parameters, the WFG, for instance, and the corresponding parameters are shown in Figure 2:

Figure 2.

Example of the workflow graph.

In Figure 2, for each task p, it has a corresponding service pool S. For each service s_pk in set S_p, it has corresponding attribute pt_pk = (t_pk, a_pk), by the tasks to generate the workflow.

Constraint analysis of workflow

Definition 7: Completion time

It means using services s_pk (p∈P, 0 < k ≤ r_p) of different tasks p to build a working path; the time the path spends is represented as T.

Definition 8: Completion accuracy

It means using services s_pk (p∈P, 0 < k ≤ r_p) of different tasks p to build a working path; the accuracy the path reaches is represented as A.

Definition 9: Completion deadline

It refers to the latest time to complete complex product and is represented as ψ.

In the WFG G, it needs specified constraints’ policy to complete the business. The formal formulas for the process are as follows

A = \prod l_{p k} a_{p k}, p \in P, 0 < k \leq r_{p}

(1)

where l_pk uses the service s_pk to complete the task p. Formula (1) means the accuracy of a path that can complete the complex product

s . t . \sum_{k = 1}^{r_{p}} l_{pk} = 1, p \in P

(2)

Formula (2) means the path can only select one service when completing one task

T = \sum l_{pk} t_{pk} \leq ψ, p \in P, 0 < k \leq r_{p}

(3)

Formula (3) means the time complex products spend must be less than or equal to the deadline

l_{pk} \in {0, 1}, p \in P, 0 < k \leq r_{p}

(4)

Formula (4) means l_pk is a variable.

Under deadline ψ, the article uses formula (1) as the heuristic function and uses formulas (2)–(4) as the constraint conditions to work out the accuracy of a path that it can complete the complex product, and then uses different algorithm strategies to obtain the accuracy corresponding different paths.

Traditional unidirectional objective algorithms

In a complex production process, it carries the attributes of completion time and completion accuracy; the traditional unidirectional objective algorithm means only ensuring the minimum completion time but neglecting the completion time or only ensuring the maximum completion accuracy but neglecting the completion time.

The unidirectional objective algorithm based on minimizing the completion time

Minimizing the completion time in a business process can save more time; the algorithm selects the services which spend minimum time completing each task to build a workflow path, according to formula (5) to calculate the accuracy of the path

{\begin{matrix} T_{min} = \sum min (t_{pk}) \\ A = Π a_{pk}, 0 < k < = r_{p} \end{matrix} p \in P

(5)

In formula (5), T_min is the constraint condition, and the completion time is minimized; A is the accuracy of the path.

The unidirectional objective algorithm based on maximizing the completion accuracy

Maximizing the completion accuracy in a business process can make the path with optimal quality, so each task in the path needs the service which has maximum accuracy to complete, according to formula (6) to calculate the completion time of the path

{\begin{matrix} A_{max} = Π max (a_{pk}) \\ T = \sum t_{pk}, 0 < k < = r_{p} \end{matrix} p \in P

(6)

In formula (6), A_max is the restrictive condition, and the completion accuracy is maximized; T is the time of the path.

From the analysis of these two unidirectional objective algorithms, the disadvantages of these two policies are as follows:

Minimizing the completion time results in the minimum completion accuracy of the path.

Maximizing the completion accuracy causes a problem that the completion time may exceed deadline ψ; it cannot meet the business requirements that complete the process on time.

Based on serial reduction optimization strategy in the time–accuracy

The core idea of serial reduction technology is fully considering the completion time and accuracy of the business process, within deadline ψ, assigning each task with an activity section, translating complex production process into the implementation of the local node, through an iterative manner, and to find a path that can balance both completion time and accuracy.

Definition

Definition 10: Task freedom WF_p

It refers to the active portion of task p in workflow model; the portion is represented as [ST_p, EN_p], p∈P, ST_p means the earliest start time for the task, and EN_p means the latest start time. ST_p and EN_p of WF_p are obtained by formula (7)

{\begin{matrix} S T_{p} = \sum_{i = 1}^{p - 1} min (t_{ik}), 0 < k \leq r_{p}, S T_{1} = 0 \\ E N_{p} = ψ - \sum_{i = n}^{p} min (t_{ik}), 0 < k \leq r_{p} \end{matrix}

(7)

Theorem 1

In WFG G, any task p has only one task freedom WF_p.

Authentication

Existing the tasks p, p′, and they are in order, p′ is the precursor of p.

Prove that the earliest start time ST_p is only one. Suppose the running time of the kth service for task p′ is shortest, namely, $t_{p' k}$ , task p’s earliest start time $S T_{p} = S T_{p'} + t_{p' k}$ , in turn, it is the earliest start time of each task, and therefore the earliest start time of the task p is only one.

Prove that the latest start time EN_p is only one: suppose the latest start time of task p′ is $E N_{p'}$ , p′ is the last task, then assume existing $E N'_{p'} < E N'_{p'}$ , for the maximum service time t_pk in task p, then the time $E N'_{p'} + t_{pk} < ψ$ , and this time will be not the latest start time for p′. Conversely, if $E N'_{p'} > E N_{p'}$ , then the time $E N'_{p'} + t_{pk} > ψ$ , the completion time exceeds the deadline, so the assumption does not hold.

In summary, the earliest start time of task p is only one and the latest start time of task p is also only one, so the task freedom WF_p also has one and only one.

Q.E.D.

Arithmetic statement

Serial reduction hierarchy algorithm is an algorithm that can choose the appropriate services in the activity section and balance the completion time and the accuracy. The traditional algorithm may produce some time segments because of the service’s inadequate use of time in the service of the activity section. Serial reduction algorithm can make full use of time and gather the time fragment to achieve a local optimal solution. Based on the freedom of the task, there is a WF_p = [ST_p, EN_p] for any task p in the set of task P; this article solves the maximum accuracy from back to front that each task can obtain when it starts at different times and determine the optimal path by the comparison of final completion accuracy.

Suppose the business process contains n tasks, f(p,t) represents the maximum accuracy that task p can achieve when it starts at time t, t∈[STp, ENp], that is, the activity freedom of task p. Within task freedom WF_p, task p in the last layer must be able to get a maximum accuracy when it starts at different times; the process can be obtained by formula (8)

{\begin{matrix} f (p, t_{p}) = max {a_{pk}}, p = n, 0 < k \leq r_{p} \\ t_{p} \in [S T_{p}, E N_{p}], t_{p} + t_{pk} \leq ψ \end{matrix}

(8)

Existing task p′ which is the precursor of task p. After the reduction of all tasks, based on the results of task p which is in the last layer, the algorithm obtains the maximum accuracy of each task when it starts at different time iteratively, the process can be obtained by formula (9)

{\begin{matrix} f (p', t_{p'}) = max {f (p, t_{p'} + t_{p' k}) \times a_{p' k}} \\ t_{p'} \in [S T_{p'}, E N_{p'}] \end{matrix}

(9)

With the iteration, when traversing to the initial task, the combination of services which has the maximum accuracy of business processes is the optimal path.

From the above, the steps of the algorithm are as follows:

Call the algorithm WFG to generate WFG.

Use the business deadline and formula (7) to obtain the freedom WF_p for each task.

Use formula (8) to obtain the maximum accuracy of the task in the last layer when the task starts at different times.

Use formula (9) to obtain the maximum accuracy of each task when it starts at different times iteratively.

Compare the final accuracy to achieve the optimal path which has the maximum accuracy.

According to the above strategies, the pseudo-code of the algorithm SRO (based on serial reduction optimization strategy in the time–accuracy) is as follows:

Input: parameters: P; s_pk; pt_pk; len//len is the number of the task set R

Output: the optimal path

Experimental results and analysis

Case design

By the research, the business process of the boiler plant in a power plant can be divided into application, examine and approve, execution, record, debug, and completion of the six areas; after the analysis, the processes of application and completion can be set to virtual task. These task links form task set P, which can be represented in the abstract as follows: examine and approve is p₁, execution is p₂, record is p₃, debug is p₄, the virtual task of application is p_s, and the virtual task of completion is p_e; each task p corresponds to a service pool S_p, the service set of examine and approve p₁ is S₁ = {s₁₁, s₁₂, s₁₃}; the service set of execution p₂ is S₂ = {s₂₁, s₂₂}; the service set of record p₃ is S₃ = {s₃₁, s₃₂, s₃₃}; the service set of debug p₄ set is S₄ = {s₄₁, s₄₂}; the virtual service set of application is S_s; and the virtual service set of completion is S_e. Any elements in each service set have attributes pt_pk; combined with the service, it can be expressed as s_pk (t_pk, a_pk); s₁₁(3,0.96) means the time of using service s₁₁ to complete task p₁ is 3, and the accuracy is 0.96. Other services in each task and their working time and accuracy are shown in Table 1.

Table 1.

Task and service attributes.

Task pool (R)	Service pool (S)
p ₁	s ₁₁(3,0.96); s₁₂(4,0.98); s₁₃(6,0.99)
p ₂	s ₂₁(2,0.97); s₂₂(4,0.99)
p ₃	s ₃₁(5,0.96); s₃₂(7,0.97); s₃₃(9,0.98)
p ₄	s ₄₁(6,0.96); s₄₂(8,0.97)

Through the above tasks and service pool S_p of each task p, combined with the WFG (generation algorithm of WFG), the workflow can be established as shown in Figure 3.

Figure 3.

Workflow graph.

Figure 3 shows four tasks of the boiler plant and their service pools, and the corresponding attributes of the services for each task are marked in the figure. By this, we call different algorithms to calculate different test results.

Algorithm analysis

Based on the WFG in Figure 3, specifying the completion deadline of this business process ψ = 19, the article uses the traditional unidirectional objective algorithm with the SRO (based on serial reduction optimization strategy in the time–accuracy) to compare, reflecting the optimized effect of SRO.

Traditional unidirectional objective algorithm

1. The unidirectional objective algorithm based on minimizing the completion time

Based on minimizing the completion time, then calling formula (5) to obtain the corresponding path which is s₁₁ → s₂₁ → s₃₁ → s₄₁, at this time, the constraint condition is T_min = t₁₁ + t₂₁ + t₃₁ + t₄₁ = 3 + 2 + 5 + 6 = 16; the T_min meets the condition that it is less than 19, then the corresponding workflow accuracy is A = a₁₁ × a₂₁ × a₃₁ × a₄₁ = 0.96 × 0.97 × 0.96 × 0.96 = 0.858.

2. The unidirectional objective algorithm based on maximizing the completion accuracy

Based on the strategy, the paper uses the formula (6) to obtain the corresponding path which is s₁₃ → s₂₂ → s₃₃ → s₄₂, at this time, the constraint condition is A_max = a₁₃ × a₂₂ × a₃₃ × a₄₂ = 0.99 × 0.99 × 0.98 × 0.97 = 0.931, the corresponding completion time is T = t₁₃ + t₂₂ + t₃₃ + t₄₁ = 6 + 4 + 9 + 8 = 27, because the completion time is greater than the deadline 19, so that the path does not meet the condition.

Based on serial reduction optimization strategy in the time–accuracy

By the task pool and the service pool in Table 1, the paper uses algorithm 2 to obtain the earliest start time of p₁, p₂, p₃, p₄ are 0, 3, 5, 10 respectively, the latest start time are 3, 6, 8, 13, respectively. Then the freedom of task p₁ is [0, 3], the freedom of task p₂ is [3, 6], the freedom of task p₃ is [5, 8], and the freedom of task p₄ is [10, 13]; within the freedom of each task, the maximum accuracy of each task that starts at different times can be obtained:

p₄(debug):

f(4,10) = max{0.96,0.97} = 0.97; f(4,11) = max{0.96,097} = 0.97;

f(4,12) = max{0.96} = 0.96; f(4,13) = max{0.96} = 0.96.

p₃(record):

f(3,5) = max{f(4,10) × 0.96; f(4,12) × 0.97} = 0.931;

f(3,6) = max{f(4,11) × 0.96; f(4,13) × 0.97} = 0.931;

f(3,7) = max{f(4,12) × 0.96} = 0.921;

f(3,8) = max{f(4,13) × 0.96} = 0.921.

p₂(execution):

f(2,3) = max{f(3,5) × 0.97,f(3,7) × 0.99} = 0.912;

f(2,4) = max{f(3,6) × 0.97,f(3,8) × 0.99} = 0.912;

f(2,5) = max{f(3,7) × 0.97} = 0.894;

f(2,6) = max{f(3,8) × 0.97} = 0.894.

p₁(examine and approve):

f(1,0) = max{f(2,3) × 0.96,f(2,4) × 0.98; f(2,6) × 0.99} = 0.894;

f(1,1) = max{f(2,4) × 0.96,f(2,5) × 0.98} = 0.876;

f(1,2) = max{f(2,5) × 0.96,f(2,6) × 0.98} = 0.876;

f(1,3) = max{f(2,6) × 0.96} = 0.858.

Algorithm 2.
len = P.length;
Call (WFG, s_pk, pt_pk, len);
//use the WFG (generation algorithm of workflow graph);
By G;
//generate the workflow graph G
For (int p = 1; p < = len; p++)
{List (formula (7), WF_p);}
//using the formula (7) to obtain the freedom WF_p for each task
p = len;
Figure (formula (8), a_pk);
//use formula (8) to obtain the maximum accuracy of the//task in last layer when the task start at different times
for (p; p > 0; p -)
{Figure (formula (9), a_pk);};
//use the formula (9) to obtain the maximum accuracy of each task when it start at different times iteratively
if (p = 1) {A_t = f (p, t);}
Search max (A_t).
//Find the best path which has the maximum accuracy
The time complexity of the algorithm is O (mⁿ).

The f(1,0) = 0.894 is maximum, so the optimal path for the serial algorithm is as follows: p₁ starts at time 0, and f(2,4) × 0.98 = 0.894, so p₁ is completed by service s₁₂ and the time that s₁₂ uses is 4; p₂ starts at time 4, and f(3,8) × 0.99 = 0.912, so p₂ is completed by service s₂₂ and the time that s₂₂ uses is 4; p₃ starts at time 8, and f(4,13) × 0.96 = 0.921, so p₃ is completed by service s₃₁ and the time that s₃₁ uses is 5; p₄ starts at time 13, and f(4,13) = 0.96, so p₄ is completed by service s₄₁ and the time that s₄₁ uses is 6. The completion time was 19, it is equal to the deadline, and the completion accuracy obtained by the path is 0.894.

Algorithms’ comparison

Aiming at traditional unidirectional objective algorithm and serial reduction algorithm, we combined with the data in section “Algorithm analysis” and made a comparison between algorithms, using the MATLAB to describe the differences and the path of different algorithms, as shown in Figure 4. Figure 4(a) shows the accuracy the path reaches and the time the path spends when the process reaches different layers of tasks in different algorithms, and Figure 4(b) shows that different algorithms have different completion paths.

Figure 4.

(a) Accuracy and time of different tasks and (b) the path of different algorithms.

From Figure 4(a), when the process takes on to task p₄, its accuracy is the completion accuracy A; it can be seen that the accuracy of the unidirectional objective algorithm based on maximizing the completion accuracy is maximum, but the completion time exceeds the deadline, so the method is abandoned. The completion time of the other two strategies is less than or equal to the deadline, so the accuracy of these two strategies can be obtained; the accuracy of the unidirectional objective algorithm based on minimizing the completion time is A₁ = 0.858; the accuracy of the SRO (based on serial reduction optimization strategy in the time–accuracy) is A₂ = 0.894, using the above data to calculate the increase rate K = (A₂ − A₁)/A₁ × 100% = 4.20%. Visibly, serial reduction optimization strategy compared to the traditional unidirectional objective algorithm has played a promoting effect, and the optimal path can be obtained by Figure 4(b): s₁₂ → s₂₂ →s₃₁ → s₄₁.

The influence of other parameters on the algorithm performance

Size of the deadline ψ

Deadline ψ is the latest workflow completion time; as a general rule, increasing the deadline will improve the completion accuracy of the optimal path. In this article, serial reduction algorithm is based on confining the time; through changing the deadline, the freedom of some tasks also makes some changes. If the freedom increases, the task can select the higher accuracy service; on the contrary, if the freedom decreases, the task can only select the smaller accuracy service. Taking {5, 10} as the number of tasks to form two workflow structures, for each task p_i in the structure corresponding to a service pool S_i, its number is a value of the interval [2, 4], and the service has attribute pt_pk. Based on time T_min which the strategy based on minimum time costs, increasing 10%, 20%, 30%, 40% as the deadline respectively, and calculate the time T_max and the accuracy that the strategy based on maximum accuracy cost. Through the below constraint times, Table 2 shows the influence of changing deadline on the algorithm performance.

Table 2.

Influence of different deadlines.

Deadline	Tasks
	5	Increasing	10	Increasing
		K (%)		K (%)
T_min	0.768	0	0.602	0
(1 + 10%)T_min	0.792	3.1	0.648	7.6
(1 + 20%)T_min	0.834	8.6	0.694	15
(1 + 30%)T_min	0.876	14	0.732	21
(1 + 40%)T_min	0.898	17	0.784	30
T_max	0.924	20	0.812	35

From Table 2, when the increase rate is 0, the strategy is based on the minimum time. In these different workflow structures, with the increase in the deadline, the increasing rate becomes higher; it means the optimization performance is getting better and better. Therefore, in the actual business process, increasing the deadline appropriately will increase the completion accuracy and improve the optimization performance of the serial reduction algorithm.

Number of tasks

The completion accuracy of a path is obtained by the product of the accuracy rates which belong to the services in the path. With the increasing number of tasks, it will influence the completion accuracy and the optimization performance. Taking {5, 10, 15, 20} as the number of tasks to form four workflow structures, for each task p_i in the structure corresponding to a service pool S_i, its number is a value of the interval [2, 4], and the service has attribute pt_pk. Based on time T_min, that is, the strategy based on minimum completion time, increasing 20% as the deadline, through the comparison of the strategy based on minimum time and the serial reduction algorithm, Table 2 shows the influence of the tasks’ number on the algorithm performance.

From Table 3, obviously, with the increasing number of tasks, each link has a deviation, so the completion accuracy will be reduced, but the optimization performance of serial reduction algorithm will be better.

Table 3.

Influence of task’s number.

Task’s number	Minimum time (T)	Serial reduction	K (%)
5	0.768	0.834	8.6
10	0.602	0.694	15
15	0.512	0.618	21
20	0.408	0.522	28

Conclusion and outlook

Aiming to optimize the accuracy under the deadline, an algorithm which combines the task, service with the directed acyclic graph (DAG) is used in this paper firstly, namely WFG algorithm which can obtain the workflow structure. Based upon that, the research group first proposed a unidirectional objective algorithm based on the minimum time and the maximum accuracy of the workflow; aiming at the potential disadvantages of lower completion accuracy or exceeding the deadline, the researchers proposed a serial reduction optimization algorithm under the constraint deadline, adopted a hierarchical strategy in this algorithm, by taking an iterative approach, and confined the time for every task to obtain the maximum accuracy of the task when it starts at different times, and determined the optimal path by the maximum completion accuracy when all tasks are completed. The experiment shows that the performance of the serial reduction optimization algorithm was enhanced 4.2% than the traditional unidirectional objective algorithm. But there still remain some problems like not putting the business processes’ operational cost into this algorithm which require further discussion and study with people concerned. Future research direction is to take the relative properties of the service in the business process into consideration and truly find an optimal path which is efficient, accurate, and cost-saving; the group will further improve and refine it.

Footnotes

Academic Editor: Ramoshweu Lebelo

Declaration of conflicting interests

The author(s) declared no potential conflicts of interest with respect to the research, authorship, and/or publication of this article.

Funding

The author(s) disclosed receipt of the following financial support for the research, authorship, and/or publication of this article: This work was supported by the National Natural Science Foundation of China (grant no. 61403109).

References

Kumar

Dijkman

Song

Optimal resource assignment in workflows for maximizing cooperation. Int J Bus Process Manag 2013; 8094: 235–250.

Singh

Chana

QRSF: QoS-aware resource scheduling framework in cloud computing. J Supercomput 2015; 71: 241–292.

Deldari

Naghibzadeh

Abrishami

CCA: a deadline-constrained workflow scheduling algorithm for multicore resources on the cloud. J Supercomput 2016; 22: 1–26.

Surianarayanan

Ganapathy

Ramasamy

MS.

An approach for selecting best available services through a new method of decomposing QoS constraints. Serv Oriented Comput Appl 2015; 9: 107–138.

Varalakshmi

Ramaswamy

Balasubramanian

. An optimal workflow based scheduling and resource allocation in cloud. Comm Com Inf Sc 2011; 190: 411–420.

Buyya

Giddy

Abramson

. An evaluation of economy-based resource trading and scheduling on computational power grids for parameter sweep applications. In: Proceedings of the 2nd international workshop on active middleware services, vol. 583, Pittsburgh, PA, pp.221–230. New York: Kluwer Academic Press, 2000.

Buyya

Abramson

Giddy

. Economic models for resource management and scheduling in grid computing. Concurr Comp Pract E 2002; 14: 1507–1542.

Khajehvand

Pedram

Zandieh

Scalable cost-time trade-off scheduling for workflow application in grids. KSII Trans Internet Inf Syst 2013; 7: 3096–3117.

Czarnul

Modeling, run-time optimization and execution of distributed workflow applications in the JEE-based BeesyCluster environment. J Supercomput 2013; 63: 46–71.

10.

Rodenburg

Mirhosseini

Magaña-Loaiza

. Cost optimization of execution of multi-level deadline-constrained scientific workflows on clouds. Lect Notes Comput Sc 2014; 8384: 251–260.

11.

Kim

W-J

Kang

D-K

Kim

S-H

. Cost adaptive VM management for scientific workflow application in mobile cloud. Mobile Netw Appl 2015; 20: 328–336.

12.

Liu

C-c

Zhang

W-m

Luo

Z-g.

Time and cost trade-off heuristics for workflow scheduling based on bottom level. J Natl Univ Def Technol 2013; 35: 61–66.

13.

Zhuo

S-j

Zhang

Wu.

Cost optimization workflow-driven SaaS for collaborative research and development. Comput Integr Manuf 2013; 19: 1748–1754.

14.

Liang

H-l

Y-h

S-j.

Research on dynamic scheduling of scientific workflows with temporal constraints. Syst Eng Theory Pract 2015; 35: 2410–2421.

15.

Zhang

P-y

Feng

Method of workflow bi-directional scheduling in cloud computing environment. Comput Sci 2015; 42: 425–430.

16.

Cao

Wang

X-t

Xiong

L-r

. Searching method for particle swarm optimization of cloud work-flow scheduling with time constraint. Comput Integr Manuf 2016; 22: 372–380.

17.

Chen

Xue

H-x

Zhang

Q-m.

Reliable supply chain network design model based on ontology and multi-agent. Comput Integr Manuf 2011; 17: 142–150.

18.

Tang

Pan

M-L

. Temporal workflow process model and its soundness verification. J Softw 2010; 21: 1233–1253.

19.

Luo

Z-y L

Sun

G-l

Liu

J-h

. Application of the attack graph algorithm in intrusion prevention system. J Yunnan Univ 2012; 34: 271–275.

20.

Luo

Z-y

You

J-z

. Automatic recognition model of intrusive intention based on three layers attack graph. J Jilin Univ 2014; 44: 1392–1397.

Serial reduction optimization research of complex product workflow’s accuracy under the time constraint

Abstract

Keywords

Introduction

Relevant works

Problem descriptions

Definition of workflow model

Definition 1: Task pool

Definition 2: Service pool

Definition 3: Rank of service pool

Definition 4: Workflow model

Definition 5: Workflow graph

Definition 6: Service attribute

Generation algorithm of WFG

Example of generation algorithm of WFG

Constraint analysis of workflow

Definition 7: Completion time

Definition 8: Completion accuracy

Definition 9: Completion deadline

Traditional unidirectional objective algorithms

The unidirectional objective algorithm based on minimizing the completion time

The unidirectional objective algorithm based on maximizing the completion accuracy

Based on serial reduction optimization strategy in the time–accuracy

Definition

Definition 10: Task freedom WFp

Theorem 1

Authentication

Arithmetic statement

Experimental results and analysis

Case design

Algorithm analysis

Traditional unidirectional objective algorithm

Based on serial reduction optimization strategy in the time–accuracy

Algorithms’ comparison

The influence of other parameters on the algorithm performance

Size of the deadline ψ

Number of tasks

Conclusion and outlook

Footnotes

Declaration of conflicting interests

Funding

References

Definition 10: Task freedom WF_p