Task Scheduling Model and Multi-objective Optimization Genetic Algorithm Considering Quality of Service

Shanshan Hao ； Yuping Wang ； Hejun Xuan

《電腦學刊》 29卷4期 (2018/08) Pp. 217-229

https://doi.org/10.3966/199115992018082904017

摘要

Divisible task scheduling is a famous NP-hard problem. Most existing works aim at minimizing the completion time, i.e., minimizing the makespan as their single target. However, in practice, there are usually more than one objectives needed to be optimized. In this paper, we introduce the quality of service, and use it as another optimization objective except for optimizing the makespan. As a result, we set up a new optimization model: multi-objective optimization model, which is more practical and more reasonable. To resolve this multi-objective optimization model efficiently, a novel genetic algorithm based on MOEA/D is proposed, in which two new crossover operators and a specific-designed mutation operator are put forward. To demonstrate the effectiveness and efficiency of the proposed model and algorithm, a series of experiments are conducted, and the experimental results indicate the effectiveness and efficiency of the proposed model and algorithms.

關鍵字

bi-objectives ； divisible task scheduling ； genetic algorithm ； quality of service