A.Initial Task Allocation Algorithm 1 Initial Task Allocation Procedure During the initialization phase,we greedily select the server Input:G(V,E,W),S with configured containers,local for each task,which allows the earliest completion of a task server s among all servers.Specifically,the assigned sever of the Output:initial solution hidden exit (entry)task is the local server in our system.The 1:assume vo,v1,..J+1 are the task precedence of G. details of the initial task allocation are shown in Algorithm 1. 2:F,k=+oo for0≤j≤J+1and0≤k≤K. Specifically,a job G is released to local server s.The two 3:let Fo,:=0. hidden tasks (vo and vJ+1)will be placed and executed on 4:for j=1 to J do s.Before the initialization starts,we need to prioritize the 5: for k=0 to K do tasks.So we first find the longest directed path from the task 6 find Pj,Pj={(vi,sy)vi is a direct predecessor concerned to the exit task,and calculate the sum of the task task of vj,sy is the server to which vi is assigned} processing time and the communication time between tasks on 1 if server sk with container map(vj)then the longest path [10].Then,according to the decreasing order FA=maxe,e马{Eg++P巧} of the calculation result,we can prioritize these tasks (Line 1). 9: else The earliest finish time of task v;on server sk is denoted as 10: findap)ap)ss is the server Fj.k,which is set to +o initially (Line 2).The value of Fo.t with container map(vj)in edge server or cloud). is 0 because task vo is virtual (Line 3).With corresponding 11 Bk=max(e马eew{Bg++ container configuration,for each direct predecessor task v;of P5,k十△map(e)k,2} task vj,the value of Fik is equal or greater than the sum 12: end if of the finish time of v:,the communication time between 13: end for vi and vj and the processing time of vj on sk,where we 14 letu=arg mino:≤k≤KFf,k make Fi.k equal to the aforementioned maximum sum (Line 8).Without corresponding container configuration,we need 15: assign task vj to server s to add additional container configuration time from the server 16:end for with the corresponding container to sk(Line 11).We place 17:F3+1!=max(F) task vj on the server with minimum Fi..after one iteration 18:construct the initial solution from FJ+1. (Line 14-15).With the acquisition of the earliest completion 19:return initial solution time of each task,we end up with FJ+1,which also is the earliest completion time of the job.From this process,we can know where each task is assigned,and then encode it to get where o is the size of the search step:sign()represents a the initial solution. sign function;f)is a function to be optimized.Our goal is to minimize job completion time (i.e.,makespan),so we use B.Chaos-based Beetle Antennae Search Algorithm the reciprocal of the makespan as the function. The original Beetle Antennae Search Algorithm (BAS)[11] 1 algorithm has good optimization performance and convergence f(r）=makespan( (5) in continuous space,but it's not suitable for discrete space.To solve this problem,we discretize the model and then propose With iteration,the step size gradually decreases for a more the Chaos-based Beetle Antennae Search Algorithm.For a job, refined search and the distance vector is adjusted with it,they we first generate a random direction vector(i.e.,a scheduling are shown as follows: solution)in the given system as follows: 6t=h6t-1 (6) b=rndi(K,J) (1) '=6/c (7) where rndi(K,/)represents a function.The function can ran- where h is coefficient of the step size,c is a constant preferably domly generate an /-dimensional vector,each dimension of between 2 to 10. which is an integer value not exceeding K.After obtaining Note that some vectors are operated to be non-integer,such the scheduling solution b.the position of the left-tentacles and as xi and r,in order to make them operate in f,we deal with right-tentacles are defined as below: them as follows: xI=xt-d'b (2) x'=x'mod K (8) Ir =z'+d'b (3)the formula is to convert the non-integer number x'into an where zt is the position after the t-th fly of beetle.dt is the integer number that can indicate server identification. sensing length of antennae.Then,we further generate iterative The details of the CBAS are shown in Algorithm 2.More model which determines the direction and distance of the importantly,the performance of BAS after discretization is beetle at the next time,as follows: poor,so we alleviate it by adding a logistic chaotic map in the first iter/2 iterations (Line 8-12)[12].Specially,the purpose xt=xt-1+86.sign(f()-f(I)) (4) of generating the chaos value from a deterministic nonlinear Authorized licensed use limited to:University of Science Technology of China.Downloaded on July 14,2021 at 02:23:40 UTC from IEEE Xplore.Restrictions apply.A. Initial Task Allocation During the initialization phase, we greedily select the server for each task, which allows the earliest completion of a task among all servers. Specifically, the assigned sever of the hidden exit (entry) task is the local server in our system. The details of the initial task allocation are shown in Algorithm 1. Specifically, a job G is released to local server sl. The two hidden tasks (v0 and vJ+1) will be placed and executed on sl. Before the initialization starts, we need to prioritize the tasks. So we first find the longest directed path from the task concerned to the exit task, and calculate the sum of the task processing time and the communication time between tasks on the longest path [10]. Then, according to the decreasing order of the calculation result, we can prioritize these tasks (Line 1). The earliest finish time of task vj on server sk is denoted as Fj,k, which is set to +∞ initially (Line 2). The value of F0,l is 0 because task v0 is virtual (Line 3). With corresponding container configuration, for each direct predecessor task vi of task vj , the value of Fj,k is equal or greater than the sum of the finish time of vi, the communication time between vi and vj and the processing time of vj on sk, where we make Fj,k equal to the aforementioned maximum sum (Line 8). Without corresponding container configuration, we need to add additional container configuration time from the server with the corresponding container to sk (Line 11). We place task vj on the server with minimum Fj,· after one iteration (Line 14-15). With the acquisition of the earliest completion time of each task, we end up with FJ+1,l, which also is the earliest completion time of the job. From this process, we can know where each task is assigned, and then encode it to get the initial solution. B. Chaos-based Beetle Antennae Search Algorithm The original Beetle Antennae Search Algorithm (BAS) [11] algorithm has good optimization performance and convergence in continuous space, but it’s not suitable for discrete space. To solve this problem, we discretize the model and then propose the Chaos-based Beetle Antennae Search Algorithm. For a job, we first generate a random direction vector (i.e., a scheduling solution) in the given system as follows: b = rndi(K, J) (1) where rndi(K,J) represents a function. The function can ran￾domly generate an J-dimensional vector, each dimension of which is an integer value not exceeding K. After obtaining the scheduling solution b, the position of the left-tentacles and right-tentacles are defined as below: xl = xt − dtb (2) xr = xt + dtb (3) where xt is the position after the t-th fly of beetle. dt is the sensing length of antennae. Then, we further generate iterative model which determines the direction and distance of the beetle at the next time, as follows: xt = xt−1 + δtb · sign(f(xr) − f(xl)) (4) Algorithm 1 Initial Task Allocation Procedure Input: G(V,E,W), S with configured containers, local server sl Output: initial solution 1: assume v0, v1, ..., vJ+1 are the task precedence of G. 2: Fj,k := +∞ for 0 ≤ j ≤ J + 1 and 0 ≤ k ≤ K. 3: let F0,l := 0. 4: for j = 1 to J do 5: for k = 0 to K do 6: find Pj , Pj = {(vi, sy)| vi is a direct predecessor task of vj , sy is the server to which vi is assigned} 7: if server sk with container map(vj ) then 8: Fj,k = max(vi,sy)∈Pj {Fi,y + ωi,j ry,k + pj,k} 9: else 10: find S map(vj ), S map(vj ) = {sz| sz is the server with container map(vj ) in edge server or cloud}. 11: Fj,k = max(vi,sy)∈Pj ,sz∈S map(vj ) {Fi,y + ωi,j ry,k + pj,k + ∆map(vj ),k,z} 12: end if 13: end for 14: let u = arg min0≤k≤K k Fj,k 15: assign task vj to server su 16: end for 17: Fj+1,l = max(vi,sy)∈Pj+1 {Fi,y + ωi,j ry,l } 18: construct the initial solution from FJ+1,l. 19: return initial solution where δ is the size of the search step; sign(·) represents a sign function; f(·) is a function to be optimized. Our goal is to minimize job completion time (i.e., makespan), so we use the reciprocal of the makespan as the function. f(x) = 1 makespan(x) (5) With iteration, the step size gradually decreases for a more refined search and the distance vector is adjusted with it, they are shown as follows: δt = hδt−1 (6) dt = δt /c (7) where h is coefficient of the step size, c is a constant preferably between 2 to 10. Note that some vectors are operated to be non-integer, such as xl and xr, in order to make them operate in f, we deal with them as follows: x = |x | mod K (8) the formula is to convert the non-integer number x into an integer number that can indicate server identification. The details of the CBAS are shown in Algorithm 2. More importantly, the performance of BAS after discretization is poor, so we alleviate it by adding a logistic chaotic map in the first iter/2 iterations (Line 8-12) [12]. Specially, the purpose of generating the chaos value from a deterministic nonlinear Authorized licensed use limited to: University of Science & Technology of China. Downloaded on July 14,2021 at 02:23:40 UTC from IEEE Xplore. Restrictions apply.