A look-ahead strategy-based method for scheduling multiprocessor tasks on two dedicated processors

Meziane Aider (1) , Fatma Zohra Baatout (1) , Mhand Hifi (2)

1 LAROMAD - Laboratoire de Recherche Opérationnelle et de Mathématique de la Décision [Tizi-Ouzou]
2 EPROAD - Eco-Procédés Optimisation et Aide à la Décision - UR UPJV 4669

In this paper, we investigate the use of a look-ahead strategy combined with path-relinking for tackling the problem of scheduling multiprocessor tasks on two dedicated processors. An instance of the problem is composed of a set of tasks divided into three subsets and two processors, where some tasks can be executed either on one processor or two processors. The goal of the problem is to schedule all tasks such that the execution of the last assigned task is minimized. First, the proposed method starts with a greedy feasible solution built by applying a knapsack rule related to a predefined sequence. Second, a series of local operators are added in order to drive the search process around a series of neighborhoods. Third, a first diversification strategy based upon drop and rebuild operators is employed. The second diversification/intensification strategy is used for highlighting the performance of the method; it incorporates a look-ahead strategy combined with the path-relinking. Finally, the performance of the proposed method is experimentally analyzed on a set of benchmark instances of the literature, where its provided results are compared to those achieved by more recent methods available in the literature. Its behavior is also evaluated by providing a statistical analysis using both the Sign test and the Wilcoxon signed-rank test.

Domaines: Informatique [cs]

Meziane Aider, Fatma Zohra Baatout, Mhand Hifi. A look-ahead strategy-based method for scheduling multiprocessor tasks on two dedicated processors. Computers & Industrial Engineering, 2021, 158, ⟨10.1016/j.cie.2021.107388⟩. ⟨hal-03617882⟩