On-line load balancing is one of the most important problems for applications with resource allocation. It aims to assign tasks to suitable machines and balance the load among all of the machines, where the tasks need to be assigned to a machine upon arrival. In practice, tasks are not always required to be assigned to machines immediately. In this paper, we propose a novel on-line load balancing model with task buffer, where the buffer can temporarily store tasks as many as possible. Three algorithms, namely LPTCP1_α, LPTCP2_α, and LPTCP3_β, are proposed based on the Longest Processing Time (LPT) algorithm and a variety of planarization algorithms. The planarization algorithms are proposed for reducing the difference among each element in a set. Experimental results show that our proposed algorithms can effectively solve the on-line load balancing problem and have good performance in large scale experiments.
Publié le : 2017-12-19
Classification:  other areas of Computing and Informatics,  On-line schedule, load balancing, task buffer, planarization processing
@article{cai2017_5_1207,
     author = {Jiayin Wei; College of Computer Science and Technology, Guizhou University and Daoyun Xu; College of Computer Science and Technology, Guizhou University and Yongbin Qin; College of Computer Science and Technology, Guizhou University and Ruizhang Huang; College of Computer Science and Technology, Guizhou University},
     title = {On-Line Load Balancing with Task Buffer},
     journal = {Computing and Informatics},
     volume = {35},
     number = {4},
     year = {2017},
     language = {en},
     url = {http://dml.mathdoc.fr/item/cai2017_5_1207}
}
Jiayin Wei; College of Computer Science and Technology, Guizhou University; Daoyun Xu; College of Computer Science and Technology, Guizhou University; Yongbin Qin; College of Computer Science and Technology, Guizhou University; Ruizhang Huang; College of Computer Science and Technology, Guizhou University. On-Line Load Balancing with Task Buffer. Computing and Informatics, Tome 35 (2017) no. 4, . http://gdmltest.u-ga.fr/item/cai2017_5_1207/