Bayesian optimization algorithm for multi-objective scheduling of time and precedence constrained tasks in heterogeneous multiprocessor systems

• Published in: Applied soft computing 2020-07, Vol.92, p.106274, Article 106274
• Main Authors: Muhuri, Pranab K., Biswas, Sajib K.
• Format: Article
• Language: English
• Subjects: Multi-objective Bayesian optimization algorithm; Multiprocessor systems; Precedence constraints; Real-time systems; Task scheduling
• ISSN: 1568-4946; 1872-9681
• DOI: 10.1016/j.asoc.2020.106274

This paper presents a Bayesian optimization based novel approach for multi-objective scheduling of time and precedence constrained tasks in heterogeneous multiprocessing environments. The proposed approach, termed as multi-objective Bayesian optimization algorithm (moBOA) for real-time scheduling, can suitably produce optimal task schedules without any violation of the timing and precedence constraints. The moBOA utilizes Bayesian networks to learn the task graphs that represent the precedence relationships among the tasks. It first allocates tasks to individual processors and then decides the order of execution on each processor based on the latest deadline first policy. The proposed moBOA may be applied to both homogeneous and heterogeneous multiprocessor systems. Extensive comparative analysis has been made by considering two other existing evolutionary algorithms, namely the multi-objective genetic algorithm (moGA) and multi-objective hybrid genetic algorithm (mohGA) through experimental simulations with benchmark datasets. From the results of the simulation experiments, it is observed that moBOA outperforms both moGA and mohGA in terms of quality of solutions, Pareto-optimalilty and standard performance measures. We demonstrate that the task schedules produced by moBOA are optimal and comply with the timing as well as the precedence constraints. Statistical significant analyses of the results are conducted. •Multi-objective Bayesian optimization algorithm (moBOA) for real-time scheduling.•moBOA utilizes Bayesian networks to learn task graphs that show task precedencies.•It allocates tasks to processors and follows latest deadline first execution order.•Can produce feasible task schedules complying timing and precedence constraints.•moBOA may be applied to both homogeneous and heterogeneous multiprocessor systems.