On complex tasks scheduling scheme in cloud market based on coalition formation

摘要

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 vertical bar N vertical bar vertical bar T vertical bar(2)log vertical bar T vertical bar + vertical bar N vertical bar(2). (C) 2016 Published by Elsevier Ltd.