A Homogeneous Cloud Task Distribution Method Based on an Improved Leapfrog Algorithm

Yunliang Huo,Ji Xiong,?,Zhixing Guo,Qianbing You and Yi Peng

1School of Mechanical Engineering,Sichuan University,Chengdu,610065,China

2Chengdu Yigao Intelligent Technology Co.,Ltd.,Chengdu,610065,China

ABSTRACT Cloud manufacturing is a new manufacturing model with crowd-sourcing characteristics,where a cloud alliance composed of multiple enterprises,completes tasks that a single enterprise cannot accomplish by itself.However,compared with heterogeneous cloud tasks,there are relatively few studies on cloud alliance formation for homogeneous tasks.To bridge this gap,a novel method is presented in this paper.First,a homogeneous cloud task distribution model under cloud environment was constructed,where services description,selection and combination were modeled.An improved leapfrog algorithm for cloud task distribution(ILA-CTD)was designed to solve the proposed model.Different from the current alternatives,the initialization operator and the leapfrog operator in ILA-CTD can ensure that the algorithm always searches the optimal solution in the feasible space.Finally,the processing of task allocation for 1000 pieces of medical labeling machine bottom plates was studied as a case to show the feasibility of the proposed method.The superiority of ILA-CTD was also proven based on more optimal solutions found,compared with the three other methods.

KEYWORDS Cloud manufacturing;service composition;tasks distribution;intelligent optimization;leapfrog algorithm

1 Introduction

The application of modern technologies(the Internet of Things[1,2],service-oriented technology[3],cloud computing[4],big data[5],etc.)had a profound impact on manufacturing methods.Cloud manufacturing(CMfg)is a network-based and knowledge-enhanced manufacturing model,it is a specific form of the service-oriented manufacturing paradigm[6].Generally,there are two types of clouds:private clouds in large enterprises[6,7]and public clouds for small and medium enterprises(SMEs)[8].The application of CMfg in SMEs would better reflect the characteristics of CMfg,such as centralized management of distributed resources,crowd-sourcing manufacturing,and highly shared manufacturing resources[9].

There is consistent requirement in CMfg in SMEs,namely that a large order needs to be fulfilled in a short time,this is undertaken by an alliance of multiple SMEs[10].A single SME is unable to complete such a large order in a timely manner.A reasonable distribution of a large order to multiple SMEs can drastically reduce the time required to fulfill the order,because the order can be executed parallelly.The global optimization for this activity can be achieved through reasonable task allocation according to the capabilities of the alliance members.Two crucial steps are needed to form a cloud alliance:selection of members(services selection)and reasonable task distribution(services composition)[11].

Selection of alliance members,namely services selection(SS)can be achieved through methods such as semantic similarity[12],QoS(quality of services)[13]and rough-fuzzy approach[14].For task distribution,cloud manufacturing relates to two types:heterogeneous tasks that require different services[15],and homogeneous tasks that require the same services[16].The difference is that the latter selects services based only on QoS,and even if the production capacity of an individual service is insufficient,a large number of available services will still be obtained.However,not every available service can be assigned a task because there is the constraint of starting quantity.Therefore,how to reasonably allocate mass homogeneous tasks to such services is a complicated question with many constraints such as production capacity,QoS,and starting quantity.To propose a solution to this problem,an improved leapfrog algorithm for cloud task distribution(ILA-CTD)is presented in this study.A novel initialization operator was designed in this method to avoid the solution modification caused by the restriction of the starting quantity.The solution obtained by the leap operator satisfies the restriction of the starting quantity.Pareto optimal theory was applied to leapfrog algorithm,so that the proposed algorithm has the ability to deal with multi-objective optimization problems.

This article is organized as follows:Section 2 reviews related works;Section 3 presents the proposed model;Section 4 introduces the novel task distribution method;Section 5 describes a case study with the results discussions;and Section 6 concludes the study with remarks and suggestions for future work.

2 Related Works

2.1 Service Selection(SS)

Manufacturing services are usually designed to be user-friendly(i.e.,services can be easily identified through accurate description of QoS).After alternative services are found,discrimination of the services with overlapping or identical functionalities based on QoS can be achieved[17,18].However,things become more complex when a task consists of several subtasks,that need multiple services to accomplish collaboratively[16].

Many methods have been developed to rank and select services.Zhao et al.[19]proposed an optimal service selection approach using crowd-based cooperative computing,whose main contribution was optimally balancing the QoS and the synergy effect.Eisa et al.[18]presented a Multi-Criteria Decision-Making model to rank services based on various QoS attributes;unlike other approaches,their work was based on a real cloud provider(Amazon).Hussain et al.[20]presented a novel customer-centric Methodology for Optimal Service Selection(MOSS)in a cloud environment.Bouzary et al.[21]used TF-IDF(term frequency-inverse document frequency)to identify services that satisfy QoS.A modified interval DEA model with undesirable outputs has been adopted to achieve more accurate web service selection[22].In addition,the dynamic change of consumer requirements was also considered by Devi et al.[23],they proposed a Linear Programming model to rank and select services dynamically.

Obviously,QoS plays an important role in cloud services selection.To build upon previous research,a selection method for homogeneous services based on QoS is proposed in this work.

2.2 Task Distribution and Services Composition

From ants to human beings,animals have the ability to cooperate,communicate and divide labor among individuals,which is inspiring collaborative manufacturing.Chen et al.[16]proposed an improved multi-objective evolutionary algorithm based on the decomposition-particle swarm optimization(MOEA/D-PSO)to obtain the optimal combination of services.Aimed at minimizing the making span,monetary and energy costs of tasks in the cloud-fog paradigm,a two-tier bipartite graph task allocation approach was presented by Gad-Elrab et al.[24]based on fuzzy set theory.Gigliotta et al.[25]examined the issues in task allocation in homogeneous communicating robots using the evolutionary algorithm.Sharma et al.[26]proposed an improved cloud task allocation strategy using a modified K-means clustering technique.A hybrid approach combining the features of genetic algorithm and the analytical hierarchy process,was implemented by Mostafa et al.[27]to distribute tasks to service suppliers.A multi-objective genetic algorithm was used by Jiang et al.[28]to allocate the disassembly tasks in the cloud environment.Jatoth et al.[29]presented an Optimal Fitness Aware Cloud Service Composition(OFASC)to balance multiple parameters of QoS.Zhou et al.[30]used evolutionary algorithms for many-objective cloud services composition.Somasundaram et al.[31]designed and developed a cloud resources broker(CLOUDRB),which integrated CLOUDRB with deadline-based job scheduling.They also developed a particle swarm optimization(PSO)-based resource allocation mechanism,to allocate users’requirements to cloud resources in a near-optimal manner.

In summary,task distribution(services combination)is a complex problem,and intelligent evolution algorithms(such as GA,EA and PSO)have made substantial contribution to address the complexities.Inspired by the previous efforts,ILA-CTD is proposed in this study to address the homogeneous cloud task distribution problem.

3 Homogeneous Task Distribution Model

3.1 Problem Statement

The manufacturing resources in CMfg are encapsulated as manufacturing service in a cloud resources pool.When the manufacturing tasks published in CMfg,three stages follow,namely,task decomposition,services selection,and services composition.The homogeneous cloud task distribution model is shown in Fig.1.

Manufacturing resources of factories are virtualized to various cloud services in a cloud service pool.When the tasks are uploaded,the service pool will be searched and available services will be selected.Then,the optimal service combination will be determined to identify an optimized cloud manufacturing alliance.The factories in the alliance will be notified to perform manufacturing tasks.The focus of our work is services selection and combination optimization,specifically for homogeneous tasks.This is expressed in Eq.(1):

Figure 1:The model of homogeneous cloud task distribution

3.2 Service Description and Selection

3.2.1 Manufacturing Service Description in the Cloud

Offline services selection mainly focuses on QoS,which involves cost,time,and quality.However,for cloud services,the attributes that affect the quality of the cloud manufacturing alliance also need to be considered.Evaluation indexes proposed by Chen give a comprehensive description of cloud manufacturing services;cloud manufacturing services(C-QoS)were expressed as 6 tuples(C-QoS= {SI,G,C0,T,C,Q})[16].

1)SIshown in Eq.(2)is the quality consistency:

SIiis the quality consistency ofith cloud alliance;Qjkis the evaluation value ofkth quality index ofSjin its history;Sjisjth available service;Sgn(Sj)is the status of serviceSj.IfSjis selected,Sgn(Sj)= 1;elseSgn(Sj)= 0.fis the number of available services,andqis the total number of quality indexes.

2)Gshown in Eq.(3)is the composability:

Giis the composability of theith cloud alliance;Gojis the number of times thatSjhas been used in a combination in its history;Gnjis the number of times thatSjhas been used in its history.

3)C0shown in Eq.(4)is communication ability:

Coiis the communication ability of theith cloud alliance;Cojhis the evaluation value of communication ability given by thehth service provider who has cooperated withSj;pis the number of services that have collaborated withSj.

4)Tshown in Eq.(5)is the time consumed by service:

Tiis the consumed time of theith cloud alliance;Tmajis the time consumed bySjfor producing a unit product;Ttajis the time consumed when the unit product is transported bySj;andsjis the number of products undertaken bySj.

5)Cshown in Eq.(6)is the cost:

Ciis the cost of theith cloud alliance;Cmajis the cost consumed bySjfor producing a unit product;Ctajis the cost consumed bySjwhen the unit product is transported.

6)Qshown in Eq.(7)is the quality:

Qjkis the evaluation value of thekth quality index ofSjin its history;andnQis the total number of evaluations ofQjkin its history.

3.2.2 Services Selection

Forrcandidate services in the cloud pool,incapable services should first be eliminated from selection.Then,f(f

rkis thekth requirement,andakis the value of the service attribute corresponding tork.

3.3 Distribution Model

The distribution model ofnproducts tofavailable services is shown in Eqs.(9)–(11).Assj≥Mjmust be satisfied,a situation may arise,namely,that not every available service can be assigned with tasks ifnis relatively small orfis relatively large.

Therefore,a complex problem arises,because product quantities undertaken by each service and different service combinations will constitute different cloud alliance options.We assign a reasonable quantity andsj(shown in Eq.(9))and optimize objectives(shown in Eq.(10))under constraints(shown in Eq.(11)):

TrandCrrepresent consumer expectations of time and cost,respectively.

4 Solution Methods

The leapfrog method is an efficient algorithm with both hereditary and group behavior[32–34].However,the classic leapfrog algorithm is incapable of solving the above model because it is a multi-objective optimization problem,and many infeasible solutions will be generated because of the constraint of starting quality.To solve the presented model,an improved leapfrog algorithm for cloud task distribution(ILA-CTD)is proposed.

4.1 Basic Definitions

Pareto domination:Assuming thataandbare two solutions of a multi-objective functionFwithmbenefit-oriented targets andncost-oriented targets,if ?i,Fi(a)≤Fi(b)(i=1,2,...,m)andFj(a)≥Fj(b)(j=1,2,...,n),whereFiis the benefit-oriented target andFjis the cost-oriented target,and at least one strict inequality holds,thenbdominatesa.

Non-dominated solution:Assuming thatcis a feasible solution of a multi-objective functionFwithmtargets,if there is no other solutiondthat satisfiesFi(c)≤Fi(d)(i=1,2,...,m)andFj(a)≥Fj(b)(j=1,2,...,n),thencis a non-dominated solution.

Elite archives:Set of non-dominated solutions obtained in the process of searching for the best solution.

4.2 ILA-CTD Operators

4.2.1 Initialization of Frog Population

A solution of the model is mapped to a frogin ILA-CTD,andpfrogs form a populationP.Different from the classic leapfrog algorithm in which the initialization of the population is achieved via the rand methods,in this work,a novel initialization method shown in Eq.(12),was designed to satisfy the constraint in Eq.(13).

unidrnd(f)is a function that produces an integer from 0 tof;aandbare the initial speed factors;cis the diversity factor;andris a random number between 0 and 1.

nis the total number required to be distributed.Obviously,all solutions obtained through the designed initialization method satisfy the constraint of starting quality,and the diversity of populationPis also guaranteed via factorc.

4.2.2 Fitness Function

A fitness function shown in Eq.(14)was designed to rank frogs,wherefiis the fitness value of theith frog in a population.

4.2.3 Grouping

Dividingpfrogs intoqgroups,whereq

4.2.4 Leap Operator τ(Ui)

The search process constantly makes the worst frog in eachmemeplexleap to a better position.The leap operatorτ(Ub)is shown in Eq.(15):

Uwis the worst frog in amemeplex,andUbis the best frog.It is easy to prove that the solution obtained via the leap operator also satisfies the constraint of starting quality,which is more efficient than the other methods that consume time to amend infeasible solutions.

4.2.5 Local Search

Local search replaces the worst frog with a better one in eachmemeplex.The flowchart is shown in Fig.2.

Figure 2:Flowchart of local search

Step 1:Find the local worst frogUw,the local best frogUb,and the global best frogUgb.

Step 2:UpdateUwby using the leap operatorτ(Ub).

Step 3:Is the newUwbetter than the old one? If yes,go to Step 4;else,go to Step 5.

Step 4:Replace theUwwith the new one.

Step 5:Update theUwby using the leap operatorτ(Ugb).

Step 6:Is the newUwbetter than the existingUw? If yes,go to Step 4;else,go to Step 7.

Step 7:Randomly generate a frog to replaceUw.

4.3 Process of ILA-CTD

Based on the above operators,the flowchart of ILA-CTD is shown in Fig.3.The detailed steps are as follows:

Figure 3:Flowchart of ILA-CTD

Step 1:Determine the population sizep,number of groupq,and termination conditionT.

Step 2:Initialize population with the proposed method.

Step 3:Calculate the fitness value of each frog in the population.

Step 4:Sort frogs by fitness value.

Step 5:Grouppfrogs intoqgroups.

Step 6:Perform local search for each group(update the worst one in each group).

Step 7:Converge frogs in each group,and sort frogs by fitness value again.

Step 8:Whether termination condition is met? If yes,go to Step 9;else,go to Step 10.

Step 9:Are the elite archives full? If the elite archives are not full,then fill elite archives with non-dominated solutions obtained in this generation;else,discard dominated solutions in the elite archives and fill with non-dominated solutions.Then,go to Step 5.

Step 10:Out put the elite archives.

5 A Case Study

The allocation of processing 1,000 pieces of medical labeling machine bottom plates shown in Fig.4,was used as a case to demonstrate the feasibility of the proposed method.The performance of the plate mainly depends on the dimensional accuracyQ1,position accuracyQ2of the holes,and flatnessQ3of the plate.The specific accuracy requirements and delivery time constraint is shown in Tab.1;10 available services shown in Tab.2 were obtained after services selection.

Figure 4:Medical labeling machine bottom plate

Table 1:Requirement information table

Table 2:Services information table

A personalized solution is always required in actual application,and a comprehensive evaluation based on consumer preferences for targets is necessary.Therefore,the function shown in Eq.(18)was adopted to normalize the attributes values.

Table 3:Normalized service attributes

Table 4:Example solutions of ILA-CTD

Then,the experiment was conducted under the environment of Windows10 and MATLAB 2016a.The parameters of ILA-CTD were set as population sizeP=100,elite archives = 100,number of groupsq=5,evolutionary generationT=2,000,speed factorsa=0.1 andb=10,and diversity factorc=0.4.The solution set obtained via ILA-CTD is shown in Tab.4 and Fig.5.

Figure 5:Performances of solutions obtained through ILA-CTD

5.1 Feasibility Analysis

The number of non-dominated solutions in the elite archives of each generation(shown in Fig.6)can reflect the dynamic process of the generated non-dominated solutions.As the generations increase,grows rapidly at first,and then fluctuates dynamically.This means that better solutions have been found and filled into the elite archives with the increase of generations.

Figure 6:Non-dominated solutions in the elite archives of each generation

The IGD(inverted generational distance)is a simple way to evaluate the convergence of the algorithm based on the optimal solutions set.However,it is impossible for this problem.Because the optimal solutions cannot be obtained at first.Therefore,a new measure was constructed to evaluate the performance of the method proposed in this article.The model proposed in this work is a six-targets problem,and it is difficult to directly display the Pareto frontier.If the algorithm converges,then it means the Pareto frontier converges to a certain area.Thus,the average distance between adjacent generations should become steady.Hence,the average distance between adjacent generations(Da)was adopted to evaluate the convergence of the proposed method(Eq.(19)).

Figure 7:Average distance between adjacent generations

As shown in Fig.7,Darises sharply at first,then falls,and finally stabilizes,which is consistent with the process predicted by the algorithm.The phenomenon results because of three reasons:(1)The non-dominated solutions with different search directions increase dramatically as the generations increase,(2)the optimal search direction is determined progressively and the non-dominated solutions tend to the definite search direction;so,Dadecrease,and(3)the Pareto frontier is found,Dabecomes steady,which validates that the proposed method converges.

5.2 Performance Comparison

To assess the performance of the method proposed in this work,the results obtained via ILA-CTD were compared with MOEA/D-PSO,MOEA/D-GA[11],and NSGA-Πunder the same conditions.The solutions set obtained via ILA-CTD,MOEA/D-PSO,MOEA/D-GA and NSGA-Πare shown in Tabs.5–7,respectively,and their performances are shown in Figs.8–10,respectively.

Table 5:Example solutions of MOEA/D-POS

Table 6:Example solutions of MOEA/D-GA

Table 7:Example solutions of NSGA-Π

Figure 8:Performances of solutions obtained through MOEA/D-PSO

Figure 9:Performances of solutions obtained through MOEA/D-GA

Because MOEA/D-PSO,MOEA/D-GA,and NSGA-Πare methods that have been proven to be feasible in previous studies,they can be used as comparisons to evaluate the performance of ILA-CTD.Two indicators were constructed investigate the relative performance of the proposed method.

1)Proportion of non-dominated solutions in mixed Pareto setta

Selectingmsolutions from each Pareto set that was finally obtained via MOEA/D-PSO,MOEA/D-GA,NSGA-Π,and ILA-CTD,respectively,and dominance relationships shown in Eq.(20)for the selected4 msolutions were judged.

D(ma)is the number of non-dominated solutions obtained through methoda(a∈MOEA/DPSO,MOEA/D-GA,NSGA-Π,ILA-CTD),andPDis total number of solutions in the mixed Pareto set.The comparison results are shown in Fig.11(m=10).

Figure 10:Performances of solutions obtained through NSGA-Π

Figure 11:Performance of ILA-CTD in each generation

As the generations increased,more and more non-dominated solutions inPDwere obtained via ILA-CTD.From the perspective of the number of non-dominated solutions inPDunder the same conditions(T= 2000 andm= 10),ILA-CTD performed best,followed by NSGA-Π,MOEA/D-PSO,and MOEA/D-GA.

2)Proportion of feasible solutionsPf

In practical applications,the obtained solutions must be feasible.Most evolutionary algorithms deal with infeasible solutions through a penalty function.The feasibility of all final solutions cannot be guaranteed if the penalty function is unreasonable;therefore,Pfcan express the reliability and practicability of a method.ThePfof ILA-CTD,NSGA-Π,MOEA/D-PSO,and MOEA/D-GA is shown in Fig.12.

Figure 12: Pf of each method

From the perspective ofPfin the final output solutions,ILA-CTD performed best,followed by MOEA/D-PSO,NSGA-Π,and MOEA/D-GA.It can be concluded that ILA-CTD is more practical compared with the other methods.

6 Conclusions

As one of the research hotspots of CMfg,more and more studies are being undertaken on services selection and their combination especially the combination of heterogeneous services.However,the works related to homogeneous cloud services combinations are relatively few.After reviewing the existing works and noting certain limitations,a homogeneous cloud task distribution model was proposed,and an improved leapfrog algorithm for cloud task distribution(ILA-CTD)was designed to solve the model.The contributions of the paper are summarized as follows:

1)Compared to heterogeneous task distribution,there is relatively little research on homogeneous cloud tasks.A strategy of dealing with homogeneous tasks in the cloud environment was presented to bridge this gap.

2)A specific model was proposed to describe homogeneous cloud task distribution more precisely compared with alternative methods.An improved leapfrog algorithm was designed,which was proven to be more suitable for solving the proposed model.

3)The distribution of real manufacturing tasks of medical labeling machine bottom plates was presented as a case.It was shown that the proposed method provided a combination of factories with a high degree of quality similarity and high informationization under the constraints of factory capacity,task duration,and cost.

To promote the implementation of CMfg platforms with higher agility,future works should focus on the development of efficient demand-service matching algorithm.Personalized service customization should also be studied,because personalized demands from consumers are increasing.

Funding Statement:The research was financially supported by the National Science and Technology Major Project of China(No.2019ZX04007001),the Science and Technology Major Project of Sichuan Province(No.2020ZDZX0022).

Conflicts of Interest:The authors declare that they have no conflicts of interest to report regarding the present study.