On complex tasks scheduling scheme in cloud market based on coalition formation. (February 2017) - Zhu, Junwu; Song, Heng; Jiang, Yi; Li, Bin
Highlights: A novel concept called 'task density' which can measure the priority of task is proposed. A task scheduling mechanism which aims to adaptively schedule all sub-tasks to ensure the completion of the whole task is proposed. A winner coalition formation mechanism which can form the optimum coalition is proposed. A payment sharing mechanism which is based on equal allocation of nonseparable costs (EANC) is proposed. The proposed task scheduling scheme satisfies the good economic property of budget-balanced and has low time complexity. Graphical abstract: Abstract: With the increasing workload and complexity of tasks submitted by cloud consumers, how to complete these tasks effectively and rapidly with limited cloud resources is becoming more challenging. However, most of existing mechanisms focus on auction-based allocation of cloud resources rather than on the approaches to performing tasks by the allocated cloud resources. In order to solve this problem, this paper first divides the complicated task into multiple sub-tasks, and then presents the problem of sub-tasks scheduling in a formalized manner. Next, a practical task scheduling scheme that includes task scheduling mechanism, winner coalition formation mechanism and payment sharing mechanism is proposed. In addition, this paper gives some useful theorems which can suggest that the proposed scheme possesses task execution efficiency and computational traceability with the time complexity of | N ∥ T | 2 l o g | T | + | N | 2 .