Degree Name

Doctor of Philosophy


School of Computer Science and Software Engineering


Task allocation is an important problem in grid/cloud environments in both research and applications. With the rapid development of grid/cloud environments, the features of openness and dynamism of environments put two new challenges to the development of task allocation approaches and strategies in such environments. Firstly, the participants in the environments normally have only local views about the environments due to the administrative independencies between the participants and the limited communication abilities of the participants. Secondly, task allocation methods/ approaches have to handle the dynamism and openness of the environments. In particular, task allocation methods/approaches have to respond to and be resilient from the unpredicted changes in the environments in a quick manner.

This thesis aims 1. to study the approaches of single task allocation with time constraints in open and dynamic grid/cloud environments where both the resource consumers and providers can enter and leave freely. A decentralised negotiation-based method for such a type of task allocation is proposed. In the proposed method, both consumers and providers only have local views about the environment. Consumers and providers trade with each other through negotiations in which they make their offer (count-offer) decisions strategically through taking the issues that they are concerned with into account. The experimental results show that the proposed method can achieve desirable performances in terms of the success rate of and profit obtained from the task allocation;

2. to investigate the problem of group task allocation with time constraints, in which a task consists of more than one independent subtask, in open and dynamic grid/cloud environments. To solve this problem, a decentralised combinatorial auction-based approach is proposed. In the proposed approach, the combinatorial auction is used to select a group of resource providers to perform all the subtasks need to be allocated. An indicator is also designed to help a consumer to select the most suitable group of providers; and

3. to study the problem of group task allocation, in which a task consists of more than one interdependent subtask with dependency constraints, in open and dynamic grid/cloud environments. A strategic max-sum belief propagation-based approach is proposed for such a type of task allocation. In the proposed approach, providers quote for the subtasks that they are interested in, and are allowed to dynamically and strategically update their quote prices, according to the constant changes in the environment. In addition, aiming at accelerating the online response to, improving the resilience from the unpredicted changes in general grid/cloud environments, and mitigating the requirement of message passing, a max-sum belief propagation-based method is also proposed.