A two-phase hybrid evolutionary algorithm for solving the bi-objective scheduling multiprocessor tasks on two dedicated processors

Fatma-Zohra Baatout and Mhand Hifi ()
Additional contact information
Fatma-Zohra Baatout: USTHB
Mhand Hifi: USTHB

Journal of Heuristics, 2023, vol. 29, issue 2, No 2, 229-267

Abstract: Abstract In this paper, we solve the bi-objective scheduling problem on two dedicated processors, an NP-Hard combinatorial optimization problem with a hybrid scatter search-based method. The goal of the problem is to schedule all tasks on their related processors such that the makespan and the total tardiness are minimized. The proposed method starts with an initial reference set, namely Pareto front set, provided by applying an adaptation of the knapsack type procedure. It then solves the problem by making a cooperation between two stages: (i) the first stage focuses on improving the reference set by optimizing the objective related to makespan and, (ii) the second stage tries to highlight the final reference set by favoring the optimization of the total tardiness. Further, at each stage, the $$\varepsilon $$ ε -constraint strategy is employed as a learning strategy, where its aim is to enlarge the search process around reference solutions for covering some unvisited subspaces and so, to avoid a premature convergence. In order to link both stages of the method, the path-relinking is injected whenever a new/modified reference set is reached. Finally, the performance of the designed algorithm is evaluated on instances extracted from the literature. Its results are compared to the results obtained by more recent methods of the literature. Encouraging results have been obtained.

Keywords: Bi-objective; Evolutionary; Heuristics; Scatter search; Scheduling (search for similar items in EconPapers)
Date: 2023
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
http://link.springer.com/10.1007/s10732-023-09511-0 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:joheur:v:29:y:2023:i:2:d:10.1007_s10732-023-09511-0

Ordering information: This journal article can be ordered from
http://www.springer.com/journal/10732

DOI: 10.1007/s10732-023-09511-0

Access Statistics for this article

Journal of Heuristics is currently edited by Manuel Laguna

More articles in Journal of Heuristics from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().