On complex tasks scheduling scheme in cloud market based on coalition formation. (February 2017)

• Record Type: Journal Article
• Authors: Zhu, Junwu; Song, Heng; Jiang, Yi; Li, Bin
• Is Part Of: Computers & electrical engineering. Volume 58(2017)
• Page Start: 465
• Page End: 476
• Publication Date: 2017-02
• Subjects: Cloud computing -- Task scheduling -- Coalition formation -- Payment sharing -- Mechanism design; 00-01 -- 99-00; Computer engineering -- Periodicals; Electrical engineering -- Periodicals; Electrical engineering -- Data processing -- Periodicals; Ordinateurs -- Conception et construction -- Périodiques; Électrotechnique -- Périodiques; Électrotechnique -- Informatique -- Périodiques; Computer engineering; Electrical engineering; Electrical engineering -- Data processing; Periodicals; Electronic journals; 621.302854
• DOI: 10.1016/j.compeleceng.2016.09.034
• Languages: English
• ISSNs: 0045-7906

Abstract

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 .