Method and System for Scheduling Task in Cloud Computing

Patent metadata

Field	Value
Publication number	US-2016292013-A1
Application number	US-201314650747-A
Country	US
Kind code	A1
Filing date	Oct 14, 2013
Priority date	Dec 10, 2012
Publication date	Oct 6, 2016
Grant date	—

Abstract

Disclosed are a method and a system for scheduling a task in cloud computing. The feature information of the task is parameterized; the task is classified; the best working node is obtained by computation through a Bacteria Foraging Optimization Algorithm (BFOA) according to the classification result; and the best working node is matched with the task. Obviously, the BFOA is adopted to implement task scheduling and resource allocation in cloud computing, so that the cloud computing has the advantages of group, intelligent and parallel search, simplicity in escaping from a local minimum and the like for the scheduling of a user task group, is favourable for keeping the diversity of the task group in the cloud computing, can meet the requirement of the user better, and improves the degree of satisfaction of user experience.

First claim

1 . A method for scheduling a task in cloud computing, comprising:
parameterizing feature information of the task; classifying the task; making a computation through a Bacteria Foraging Optimization Algorithm (BFOA) according to a classification result to obtain a best working node; and executing the task by the best working node.

2 . The method according to claim 1 , wherein making the computation through the BFOA algorithm according to the classification result to obtain the best working node comprises:
encoding the parameterized feature information of the task according to the classification result to obtain encoded feature information; selecting N working nodes to form an initial bacterial colony, wherein the N working nodes selected serve as bacterial individual i of the initial bacterial colony, where 1≦i≦N; decoding respectively the encoded feature information corresponding to each bacterial individual according to an algorithm decoder library; computing a fitness value of the each bacterial individual; performing a taxis operation on the each bacterial individual; performing a duplication operation on the each bacterial individual; performing a migration operation on the each bacterial individual; judging whether a best bacterial individual obtained currently reaches a user expectation value, based on that the best bacterial individual obtained currently reaches the user expectation value, selecting a working node corresponding to the best bacterial individual obtained currently as the best working node; based on that the best bacterial individual obtained currently does not reach the user expectation value, returning to a step of computing the fitness value of the each bacterial individual.

3 . The method according to claim 2 , wherein in a process of performing the taxis operation on the each bacterial individual, the method further comprises:
performing quorum sensing operation on the each bacterial individual.

4 . The method according to claim 3 , wherein performing the quorum sensing operation on the each bacterial individual comprises:
determining a bacterial individual sequence I c _ best which is currently in a best position in the bacterial colony, storing a position and a fitness value of each bacterial individual in the bacterial individual sequence; determining a bacterial individual sequence I to be searched for in the bacterial colony; selecting a serial number J rand in the I c _ best ; traversing the I c _ best to determine a position P J of the J rand in the I c _ best ; traversing each bacterial individual in the I to find an initial position of the J rand in the I, and replacing a serial number of the initial position of the J rand with the serial number of the P J ; comparing a current position of a current bacterial individual with a position of each bacterial individual in the I c _ best , based on that the new current position of the current bacterial individual is better, updating the best bacterial individual to the current bacterial individual, and updating a best fitness value of the bacterial colony correspondingly; based on that the new current position of the current bacterial individual is not better, moving toward a position of the best bacterial individual in a next taxis operation.

5 . The method according to claim 4 , wherein during performing the quorum sensing operation on the each bacterial individual, when the current bacterial individual is found in a standstill, reselecting a direction to search for the bacterial individual again; or, stopping searching for the current bacterial individual and performing a searching operation for a next bacterial individual.

6 . The method according to claim 4 , wherein updating the best bacterial individual to the current bacterial individual, and updating the best fitness value of the bacterial colony correspondingly when the new position of the current bacterial individual is better comprises:
when J i (j+1,k,l)>J best (j,k,l)
θ cc i ( j+ 1, k,l )=θ i ( j+ 1, k,l )+ C cc ×(θ b ( j,k,l )−θ i ( j,k,l ))

where, θ cc i (j+1,k,l) is an updated position of the current bacterial individual i after the quorum sensing operation; J i (j+1,k,l) is a fitness value of the current bacterial individual i; θ b (j,k,l) and J best (j,k,l) are respectively a position and a fitness value of bacterial individual b in a best position in a current bacterial colony; and C cc is an attractive factor which determines a step at which the bacterial individual swims to a historical best position of the bacterial colony.

7 . The method according to claim 4 , wherein moving toward the position of the best bacterial individual in the next taxis operation comprises:
V id new =ω·V id old +C l ·φ l ·(θ b ( j,k,l )−θ i(d-1) old ( j+ 1, k,l ))
θ id new ( j+ 1, k,l )=θ i(d-1) old ( j+ 1, k,l )+ V id new
where, V id new represents a velocity of the current bacterial individual i after a dth taxis operation; ω is an inertia weight, which enables a bacteria to keep movement inertia and a trend of expanding a search space; V id old represents a velocity of the current bacterial individual i after a (d−1)th taxis operation; C 1 is an acceleration constant; φ 1 is a pseudo-random number uniformly distributed in an interval [0, 1]; V i is a velocity of the bacterial individual i; θ b (j,k,l) is a position of bacterial individual b in a best position in the current bacterial colony; θ i(d-1) old (j+1,k,l) is a position of the current bacterial individual i after a (d−1)th taxis operation; and θ id new (j+1,k,l) is a position of the current bacterial individual i after a dth taxis operation.

8 . The method according to claim 2 , wherein performing the taxis operation on the current bacterial individual i comprises:
θ i ( j+ 1, k,l )=θ i ( j,k,l )+ C ( i )Φ( j )
where, C(i)>0, representing a step at which a bacteria swims forwards;

Φ


(
j
)

=

Δ




(
i
)

Δ
T



(
i
)



Δ


(
i
)

,

wherein Δ(i) represents a rotating vector, which is a number in an interval [−1, 1]; or,
performing the taxis operation on the current bacterial individual i comprises:
θ i ( j+ 1, k,l )=θ i ( j,k,l )+ C ( k,l )Φ( j )

where, C(k,l)=L init /n k+l−1 , C(k,l) represents a taxis operation step of the bacterial individual during a kth duplication operation and a lth migration operation; L init is an initial

Assignees

• Zte Corp

Inventors

• Li Mingli
• Ren Jianli

Classifications

• G06F9/5066 Primary

  Algorithms for mapping a plurality of inter-dependent sub-tasks onto a plurality of physical CPUs (mappping at compile time, see G06F8/451) · CPC title

• G06F9/5027

  the resource being a machine, e.g. CPUs, Servers, Terminals · CPC title

• G06F9/5083 Primary

  Techniques for rebalancing the load in a distributed system · CPC title

• G06F9/4881

  Scheduling strategies for dispatcher, e.g. round robin, multi-level priority queues · CPC title

• G06F17/11

  for solving equations {, e.g. nonlinear equations, general mathematical optimization problems (optimization specially adapted for a specific administrative, business or logistic context G06Q10/04)} · CPC title