\documentclass[11pt,reqno]{amsart}
\usepackage[utf8]{inputenc}
\usepackage[english,russian]{babel}
\usepackage{amsmath}
\usepackage{amssymb}
\usepackage{amsfonts}
\usepackage{graphicx}
\usepackage{xcolor}
\usepackage[colorlinks]{hyperref}
\usepackage{algorithm}%
\usepackage{algorithmic}%


\usepackage{titlesec}
\titlespacing{\section}{0pt}{2.5ex}{1.5ex}
\titlespacing{\subsection}{0pt}{1.5ex}{1ex}
\titlespacing{\subsubsection}{0pt}{1.5ex}{1ex}
\titleformat{\section}{\large\bfseries\centering}{\thesection}{1em}{}
\titleformat{\subsection}[runin]{\bfseries}{\thesubsection.}{0.5em}{}[.\mbox{\ }]
\titleformat{\subsubsection}[runin]{\bfseries}{\thesubsubsection.}{0.4em}{}[.\mbox{\ }]





%%%%%---------- ORCiD
\newcommand\orcidicon[1]{\href{https://orcid.org/#1}{\includegraphics[scale=0.02]{orcid.pdf}}}


\def\udcs{519.8} %Here the author places classificators of the paper according to Russian classification system
\def\mscs{90-08} %Here the author places  classificators according to the AMS classification list.
\setcounter{page}{144}

\newtheorem{lemma}{Lemma}
\newtheorem{theorem}{Theorem}
\newtheorem{definition}{Definition}
\newtheorem{corollary}{Corollary}
\newtheorem{proposition}{Proposition}



\hypersetup{linkcolor=blue,filecolor=black,urlcolor=blue, citecolor=blue}

\def\logo{\textcolor{blue}{{\bf\Huge S\raisebox{0.2ex}{\hspace{0.55ex}\raisebox{0.05ex}e\hspace{-1.65ex}$\bigcirc$}MR}}}

\def\semrtop
     {
  \vbox{
     \noindent\logo \hspace{-3mm}  \parbox{12cm}{     \begin{center}
     {\LARGE \textsf{СИБИРСКИЕ ЭЛЕКТРОННЫЕ}} \\[2mm]
     {\LARGE \textsf{МАТЕМАТИЧЕСКИЕ ИЗВЕСТИЯ}} \\[2mm]
     {\Large \textsf{Siberian Electronic Mathematical Reports}} \\[1mm]
     {\Large\tt{\textcolor{blue}{http://semr.math.nsc.ru}}}\\[1mm]
     \raisebox{1ex}{ISSN 1813-3304 }
     \vspace*{-3mm}
%     {\small Институт математики им. С.Л.Соболева СО РАН}\\[-1mm]
%     {\small Sobolev Institute of Mathematics SB RAS}
     \end{center}
}
     \vspace{-1mm}
     \noindent
      \begin{tabular}{c}
     \hphantom{aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa!} \\
     \hline\hline
     \end{tabular}

     \vspace{3mm}
     {\flushleft\it Vol. 20, No. 2, pp. 144--145 (2025) \hspace{\fill}{\rm\small УДК \udcs  \hspace{-4mm}}}
     \newline  %Volume, pages in Russian, filled by Editorial board
     	{\rm\small \textcolor{blue}{https://doi.org/10.33048/semi.2023.20.???}}\hphantom{aaaaaaaaaaaaaaaaaaaaaaaa\;}{\rm\small MSC\  \mscs }
  }%\vbox
}




\begin{document}
\renewcommand{\refname}{References}
\renewcommand{\proofname}{Proof.}
\renewcommand{\figurename}{Fig.}




\thispagestyle{empty}

\title[Evolutionary Algorithm  for Multi-Processor Scheduling]{\large Evolutionary Algorithm with Optimized Operators for Multi-Processor Scheduling with Resources}


\author[Y.V. ZAKHAROVA, M.Yu. SAKHNO]{{\bf Y.V. Zakharova}\protect\orcidicon{0000-0003-4791-7011}, {\bf M.Y. Sakhno}\protect\orcidicon{0000-0003-4791-7011} }



\address{Yulia Victorovna Zakharova  % Контактные данные всех авторов и место работы указываются только на английском языке
\newline\hphantom{iii} Novosibirsk State University, 
\newline\hphantom{iii} str. Pirogova, 1
\newline\hphantom{iii} 630090, Novosibirsk, Russia
\newline\hphantom{iii} Dostoevsky Omsk State University, 
\newline\hphantom{iii} str. Neftezavodskaya, 11
\newline\hphantom{iii} 644077, Omsk, Russia
}%
\email{\textcolor{blue}{yzakharova@ofim.oscsbras.ru}}%

\address{Maria Yurievna Sakhno  % Контактные данные всех авторов и место работы указываются только на английском языке
\newline\hphantom{iii} Sobolev Institute of Mathematics, Omsk Department 
\newline\hphantom{iii} str. Pevtsova, 13
\newline\hphantom{iii} 644043, Omsk, Russia
}%
\email{\textcolor{blue}{sosnovskayamy@gmail.com}}%

\thanks{\sc Zakharova, Yu.V.,
Evolutionary Algorithm with Optimized Operators for Multi-Processor Scheduling with Resources}
\thanks{\copyright \ 2025 Zakharova Yu.V.}
\thanks{\rm The work is supported by the Mathematical Center in Akademgorodok under the agreement \textnumero~075-15-2025-349 with the Ministry of Science and Higher Education of the Russian Federation.}
\thanks{\it Received January, 1, 2025, Published December, 31, 2025}%


\semrtop \vspace{1cm}
\maketitle {\small

\vspace{-12pt}
\centerline{{\it Communicated by} {\sc P.P. Petrov}
%({\it filled by Editorial board})
}

\bigskip
\bigskip

\begin{quote}
\noindent{\bf Abstract:} 
        We consider the NP-hard multiprocessor scheduling problem with renewable and non-renewable resources that influence on the processing times of jobs.
        We propose an evolutionary algorithm with optimized operators and problem specific encoding scheme. The optimal recombination problem is solved in the crossover operator. The computational complexity of this problem and the convergence of the algorithm are analyzed. An experimental evaluation on real data shows that the algorithm demonstrates competitive results.  A mixed integer programming model is also proposed and its properties are investigated.\medskip

\noindent{\bf Keywords:} schedule, metaheuristic, computational complexity, experiment.
 \end{quote}
}

\bigskip

\section{Introduction}

Modern manufacturing and computing systems provide  new scheduling problems where machines correspond to processors or processor cores and the consumption of renewable and non-renewable resources is taken into account. Renewable resources are given by limits at each time moment with subsequent renewal at the next time moment (e.g., cache memory, data bus).
Non-renewable resources are limited for a certain period and distributed among jobs at different time moments (e.g., energy, finance for rent). Note that the duration of jobs may depend on the volumes of resource consumption.
    
We  consider the multi-machine scheduling problem with resource-dependent processing times of jobs. A set of jobs $J = \{1, ..., n\}$ must be scheduled on a set of parallel machines (processors) $I = \{1, ..., m\}$.  Each job $j\in J$ is characterized by the processing volume $W_j$ and the number of the required processors (size)  $size_j\le m$. 
Note that  $W_j$ is the execution time of job $j\in J$ on one processor with unit speed and without other jobs.
Preemptions are disallowed. A partial order is given on the set of jobs. If job $i$ precedes job $j$ (denoted by $i \to j$), then job $j$ can be started only when job $i$ is completed.

The real durations of jobs depends on resource consumption. We consider two types of resources: renewable  and non-renewable. 

Energy represents the non-renewable resource, that depends on processor speed, and the speed influences on processing time of jobs.
If job $j$ is performed at speed $s_j$, then the duration $p_j=\frac{W_j}{s_j}$ and energy consumption $E_j = size_j \frac{W_j}{s_j} s_j^\alpha$, where $\alpha > 1$ is a constant. The total energy budget is given by the value $E$.
%Energy consumption in interval $(t_0,t_1]$ is calculated as $E=\int\limits_{t_0}^{t_1}s^\alpha(t){\rm d}t$, where $s(t)$ is the speed of a processor at time $t$ and $\alpha > 1$ is the constant.

A data bus is a part of the system bus that is used to transfer data between computer components. The data bus capacity corresponds to renewable resour\-ces. The parallel execution of jobs and their joint consumption of the data bus influences the speed and duration of the jobs. %We will assume that the data bus consumption is calculated as follows...
In practice, the distribution of data bus among the threads is very hardware-specific and depends on many factors, which we can not afford to take into account (see e.g.~\cite{Nesbit06}). As a simple approximation, we assume that the data bus bandwidth allocation to jobs  may be found by the following rule.
% добавить описание того, как распределяется шина данных и влияет на длительность
Let $b_j$ denote the percent of  data bus consumed by job $j\in J$. 
Suppose that $l$ jobs are executed simultaneously, denote this set of jobs by $J_s$. 
Initially we assign to each job $b'_j:=\frac{100\%}{l}$ of the data bus. If a job $j$ has $b_j<b'_j$ then the remaining resource ($b'_j-b_j$) is divided between jobs $i\in J_s$, for which $b_j>b'_j$. The processing time of job $j\in J_s$ is equal to $\frac{b'_j}{b_j}p_j$. We assume that slowing induced by the data bus does not influence energy consumption.

It is required to construct a feasible schedule w.r.t. allocation jobs to processors, partial order, energy constraint and  common utilization of the data bus bandwidth, that minimizes one of the objectives.
Let $C_j$ denote the completion time of job $j\in J$ in a feasible schedule. We consider two criteria: the makespan $\max_{j\in J} C_j$ (the completion time of the last job)  and the total completion time   $\sum_{j\in J} C_j$. 

Using the reduction from the Partition, 3-Partition, 3-Satisfiability and Linear Arrangement problems~\cite{Lenstra1977,Lenstra1978,GJ1979} we can prove NP-hardness for both considered criteria (the makespan and the total completion time) in the cases:\\
-- arbitrary resource consumption, unit volumes, two processors, empty partial order (ordinary NP-hard);\\
-- arbitrary resource consumption, unit volumes, three processors, empty partial order (strongly NP-hard);\\
-- identical resource consumption, arbitrary volumes, at most two processors, non-empty partial order (strongly NP-hard).

%\section{NP-hardness}
%Partition problem:\\
%arbitrary durations and two processors;\\
%unit durations and resource consumption.
%partial order and unit durations (3-satisfiability);\\
%partial order (chains), arbitrary durations and two processors (3-Partition).

Sequential and parallelizable jobs were investigated for settings with energy resource. NP-hard and polynomially solvable cases have been identified and polynomial time algorithms with approximation guarantees have been provided (see, e.g., \cite{Kononov2022,Kononov2023,Gerards2016}). 
In~\cite{ZakharovaSakhno2025}, a mixed integer programming (MIP) model is provided. Heuristics based on greedy, packing, local search and evolutionary schemes were proposed and experimentally tested in~\cite{Kong2011,Li2020,ZakharovaSakhno2024,Zakharova2025}.

A configuration MIP model and a greedy algorithm were proposed for scheduling processing modules with respect to data bus bandwidth and tested on small-size instances (up to 10 modules)~\cite{ErMalSakh2020}. In~\cite{Jozefowska}, it is assumed that the amount of resources allocated to each job is limited and continuous, and it is determined by the scheduler at each time moment. The heuristics proposed in~\cite{Merkel,Zhuravlev}  are based on the principle that jobs should be allocated to processor cores in a complementary manner so that jobs with the most diverse resource usage needs are executed simultaneously. Such resources are data bus bandwidth and cache at different levels.

Our main result is an evolutionary algorithm with optimized operators and encoding-decoding scheme allowing to take into account resources: energy and data bus bandwidth. The complexity status and algorithmic aspects of operators are investigated and the convergence of the evolutionary algorithm is analyzed. A mixed integer programming model of the problem is also presented.

\section{Mixed Integer Programming Model}
%Mixed Integer Programming Model
Here we provide the mathematical model of the problem with discrete set of possible speeds of jobs based on the concept of configurations and event points.  

{\em A configuration} $c$ is the feasible subset of jobs that can be executed simultaneously, joined with their speeds. Let ${C}$ denote the set of all configura\-ti\-ons. Configurations are formed in accordance with the partial order, and we have a partial order on the set of configurations ($a_{c_1,c_2}>0$ indicates that $c_1$ precedes $c_2$).

By {\it event point} we will mean a subset of variables in mixed integer linear programming  model, which characterize a selection of a certain set of jobs and their starting and completion times, as well as resource consumption. Let $K=\{1,\dots,k_{\max}\}$ denote the set of event points.
 
The following parameters are determined and calculated at the preproces\-sing stage:     
$s_{jc}$ is the speed of job $j$ in configuration $c$, $E_c=\sum_{j\in C} s_{jc}^\alpha$ is the instantaneous power for configuration $c$ and 
\[
    q_{jc} = \left\{\begin{array}{lr}
       1, & \text{if job $j$ is performed in configuration $c$,}\\
        0 & \text{otherwise.}\\
        \end{array}\right.
  \]
    
Introduce variables:

\[
    x_{kc} = \left\{\begin{array}{lr}
       1, & \text{if configuration $c$ is assigned to event point $k$,}\\
       0 & \text{otherwise.}\\
        \end{array}\right.
  \]
  \[
    y_{jk} = \left\{\begin{array}{lr}
       1, & \text{if job $j$ starts at event point $k$,}\\
       0 & \text{otherwise.}\\
        \end{array}\right.
  \]


$t_{kc}\ge 0$ is the duration of configuration $c$ in event point $k$,

$T^f_k\ge 0$ is the completion time of event point $k$,

$C^f_j\ge 0$ is the completion time of job $j$.

Then the set of feasible solutions is defined as follows
       
            \begin{equation}\label{eqn:milp5}
                \sum_{c \in C} x_{kc} \leq 1, \ k \in K,
            \end{equation}
%             Full execution and non-preemtion of jobs.        
            \begin{equation}\label{eqn:milp6}
                \sum_{k \in K} \sum_{c \in C} t_{kc}s_{jc} = W_j, \ j \in J,
            \end{equation}
            \begin{equation}\label{eqn:milp7}
                \sum_{k \in K} y_{jk} = 1, \ j \in J,
            \end{equation}            
            \begin{equation}\label{eqn:milp8}
                \sum_{c \in C} x_{kc} q_{jc} - \sum_{c \in C} x_{k-1,c} q_{jc} \leq y_{jk}, \ j \in J, \ k \in K,
            \end{equation}
%            Completion times        
            \begin{equation}\label{eqn:milp10}
                T^f_k \geq T^f_{k-1} + t_{kc}, \ k \in K, \ c \in C,
            \end{equation}
                        \begin{equation}\label{eqn:milp4}
                t_{kc} \leq x_{kc}T_{max}, k \in K, \ c \in C,
            \end{equation}
            \begin{equation}\label{eqn:milp11}
                C^f_j \geq T^f_k - T_{max} (1 - x_{kc}), \ j \in J, \ k \in K, \ c \in C, q_{jc} > 0,
            \end{equation}         
%        Additional constraints            
            \begin{equation}\label{eqn:milp1_3}
                \sum_{k \in K} \sum_{c \in C} E_{c} t_{kc} \leq E,
            \end{equation}           
            \begin{equation}\label{eqn:milp9}
                \sum_{k \in K} (k + 1) x_{kc_{1}} \leq (1 - \sum_{k \in K} x_{kc_{1}})k_{max} + \sum_{k \in K} k x_{kc_{2}},
            \end{equation}
          $$                c_{1}, c_{2} \in C, a_{c_{1},c_{2}} > 0.
            $$
                    \begin{equation}\label{eqn:milp9-1}
            x_{k_{1},c_{1}} (k_1 + 1) \leq (x_{k_{2},c_{2}} + (1 - x_{k_{2},c_{2}})k_{\max})k_2,
        \end{equation}
        $$k_1, k_2\in K,\ c_1, c_2\in C, a_{c_1,c_2}>0,$$
                    \begin{equation}\label{eqn:milp3}
                t_{kc} \geq 0, \ k \in K, \ c \in C.
            \end{equation}
            
Inequality~(\ref{eqn:milp5}) indicates that each event point contains at most one configura\-ti\-on. 
Constraint~(\ref{eqn:milp6}) shows that all jobs are executed in full volumes, while  constraints (\ref{eqn:milp7})--(\ref{eqn:milp8}) guarantee that jobs are executed without preemptions.  
Inequalities~(\ref{eqn:milp10})--(\ref{eqn:milp11}) compute completion times for event points and jobs.   
Constraint (\ref{eqn:milp1_3}) gives bound on the energy consumption.      
Constraints (\ref{eqn:milp9}) and (\ref{eqn:milp9-1}) provide alternative ways to model precedence constraints between configurations. 

The makespan is calculated as $\max_{j\in J}  C^f_j$ and the total completion time is computed as $\sum_{j\in J}  C^f_j$.

Preliminary computations shown that modern solvers within 8 hours and 4 threads did not found even a feasible solution for greater than 10 jobs.

\section{Evolutionary Algorithm}

We propose an adaptive evolutionary algorithm (EA) with scheme~\ref{algo:GA}.
EA models the evolution of a population of individuals that represent tentative solutions of the problem~\cite{Holland1992}.
We encode solutions by permutations of jobs (in the case of several processors jobs are assigned to processors by some prespecified rules together with objective calculation).

\begin{algorithm}[h] 
\begin{algorithmic}[1]
\STATE Generate $k$ individuals to form the initial population. Keep elites as the given number $n_{elites}$ of the best individuals of the initial population w.r.t. the objective function.
\STATE Repeat until the stopping criterion is met.
\begin{enumerate}
\item[{\small 2.1}] Select individuals from the current population for the reproduction.
\item[{\small 2.2}] Apply  mutation and recombination to the selected individuals.
\item[{\small 2.3}] Build offspring.
\item[{\small 2.4}] Update the population and elites.
\end{enumerate}
\STATE Return the best found individual.
\end{algorithmic}
\caption{Elitist Evolutionary Algorithm $EA$}
\label{algo:GA}
\end{algorithm}


Individuals of the initial population are generated randomly or using ``arbitrary insertion'' method~\cite{Eremeev2020}, similar to the method for the Traveling Salesman Problem. The last method is applied with the given probability and works according to the rule: some number of jobs  are placed in random order, and each subsequent job is chosen randomly and inserted in the position among those already placed where the value of the objective function of the partial solution is minimal. %$n_J$

We use rank or $s$-tournament selection to choose parent individuals at the reproduction stage. We apply a classic restarting rule: EA is restarted as soon as the current  number of objective function calculations becomes equal to the number of objective function calculations at which the best individual was found, plus a given number of  objective function calculations $n_{FC}$. Moreover, our algorithm is elitist and the number of elites $n_{elites}$ is fixed at the preprocessing stage. The solution obtained after reproduction operators replaces the worst individual of the population.

We have a set of crossover operators, and one of them is selected at each iteration using an $(\varepsilon,\delta)$-learning scheme.
A random crossover operator is selected with probability $\varepsilon$, and the following rule is used with probability $(1-\varepsilon)$. We select an operator that has the best weight with probability $\delta$, and choose a random operator with probabilities proportional to weights otherwise (with probability $(1-\delta)$). 

The reward of operator $oper$ is calculated as
  \[
    r_{oper} = \left\{\begin{array}{lr}
       w_1, & \text{if the obtained solution becomes a new record,}\\
       w_2, & \text{if the obtained solution is a new record in the current restart,}\\
       w_3, & \text{if the obtained solution is better than one of the parents},\\
       0 & \text{otherwise.}\\
        \end{array}\right.
  \]

The weight of operator $oper$ is updated as $R_{oper} = \lambda r_{oper}  + (1- \lambda) R_{oper}.$$

% размер популяции и количество элит - параметры алгоритма
% Селекция либо ранговая, либо турнирная
% после селекции применяется мутация с использованием мутации Пуассона или heavy tailed мутации. Операторы мутации - shift или exchange в зависимости от параметра алгоримта (выбирается irace).
% кроссинговер применяется с использованием адаптивной эпсилон-дельта схемы (сначала с вероятностью эпсиолн выбирается, будет ли это случайный кроссинговер, затем с вероятностью дельта выбирается, будет ли это лучший кроссинговер). Присутствует период обучения (каждый раз после перезапуска), когда все кроссинговеры вызываются с равномерным распределениям. Вес кроссинговера пересчитывается каждый раз после вызова.

\subsection{Construction of Schedule and Calculation of Objective}
\label{sec:constSol}
%Два варианта подсчета целевой функции:
% 1. Сначала взять первые m работ из перестановки (m - число ядер), затем вычислить, какая работа закочнится первой (с учетом замедлений), взять следующую работу из перестановки и поставить её на место завершившейся. И так далее.
% 2. Добавить фейковые работы: каждый раз, когда берем новую работу, то определяем, "влезет" ли она по шине данных так, чтобы не замедляться (например, остальные m-1 работы заняли 90% шины, а этой нужно 5% - значит влезет). Если да, то ставим её. Если нет, то с некоторой вероятностью определяем, добавить ли задержку перед этой работой. Если да, то случайным образом выбираем длительность задержки в диапазоне от 0 до максимального количества тактов процессора, оставшегося до полного завершения среди всех уже имеющихся в конфигурации работ. 

% при подсчете целевой функции происходит корректировка перестановки до допустимой (если задан частичный порядок).

Under the given permutation of jobs, the optimal dividing them between the proces\-sors is NP-hard problem for makespan criterion even in the case of identical data bus requirements for jobs and two processors (the proof is based on the reduction of the Ordered Partition Problem~\cite{GJ1979}). Similar question for the total completion time criterion is open. So, we propose a heuristic algorithm to construct a schedule for a permutation.


Energy consumption for jobs is assigned in polynomial time using the convex model on the lower bound of objective~\cite{Kononov2022,Kononov2023}. We assume that slowing due to common using of  data bus does not change the energy consump\-tion.

We tested two ways to construct a feasible schedule and compute objective for the given permutation of jobs:\\
1. We take the maximum subset $J_0$ of the first jobs from the permutation with $\sum_{j\in J_0} size_j\le m$  and compute data bus consumption for them (see Algorithm~\ref{algo:DataBus}). Then calculate durations of jobs and identify the shortest job $j_s$. After the completion of this job we go to the next job $j_n$ from the permutation and try to put it. If $size_{j_n}>size_{j_s}$, then 
we are waiting for the completion time of the next job in the current schedule.
And so on.\\
2.  We take the maximum subset $J_0$ of the first jobs from the permutation with $\sum_{j\in J_0} size_j\le m$  and compute data bus consumption for them. Then calculate durations of jobs and identify the shortest job. After the completion of this job we go to the next job or add a {\em fake} job with zero resource consumption. If the next job requires less percent of data bus that we have, then we try to put this job. Otherwise, we randomly select the delay duration in the range from 0 to the rest duration of the largest job in the current configuration and place fake job of this duration before the next job with the given probability $p_{fake}$, and add the next job without delay with probability $(1-p_{fake})$. And so on.

The experimental evaluation showed that EA with the second way of objective calculation demonstrates statistically significantly better results than EA with the first way of objective calculation (Wilcoxon test was used). Note that the role of fake jobs is placing idle periods before jobs in order to reduce data bus consumption during these periods.

% when calculating the objective function, the permutation is adjusted to an acceptable one (if a partial order is specified).
% в случае критерия makespan раскидать работы по процессорам NP-Трудная задача при заданной перестановке

% из последовательности берется след работа, для которой все предшественники завершили выполнение...
% потребление энергии и длителности работ им соотвествующие определяются по тем же правилам (из моделей выпуклого программирования) что были представлены в работах с критериями Cmax и Сsum, когда шина данных не учитывается. Считается, что замедление по шине данных не влияет на потребление энергии. Ссылки на наши с Кононовым работы.

% Как шина данных распределяется между работами в одной конфигурации (из статьи на optima 2020):
%    Now we suppose that for each job ${p}$, ${p = 1, ..., m}$, the percentage of data bus consumption ${b_{p}}$ under ideal conditions is known. During the execution of job ${p}$, a smaller percentage of the data bus can be allocated than ${b_{p}}$ if other jobs are simultaneously performed on other cores. Denote by ${z_{pk}}$ the actually allocated percentage of the data bus to job ${p}$ in configuration ${k}$. In practice, the distribution of values $z_{pk}$ among the threads is very hardware-specific and depends on many factors, which we can not afford to take into account (see e.g.~\cite{Nesbit06}). As a simple approximation, we assume that the data bus bandwidth allocation to jobs in any configuration~$k$ may be found by Algorithm~1, described below. The speed ${v_{pk}}$ of execution of job ${p}$ in the configuration ${k}$ is then proportional to the ratio ${z_{pk}}/{b_{p}}.$

 \begin{algorithm}[h] 
\begin{algorithmic}[1]
\STATE Put the percentage of the free data bus ${freePercent := 100\%}$ (the entire data bus is free) and set the number of jobs for which the data bus is not allocated, ${jobsCount}$ to be the number of jobs in configuration~${k}$.
\STATE While ${jobsCount} \ne {0}$, do:
\begin{enumerate}
\item[{\small 2.1}] Calculate a percentage of data bus that can be allocated to each job:  ${percent := freePercent / jobsCount}.$
\item[{\small 2.2}] For jobs ${j}$ with ${b_{j} < percent}$  put: ${b_{j}' := b_{j}}$ and ${freePercent := freePercent - b_{j}},$\\
${jobsCount := jobsCount - 1}.$
\item[{\small 2.3}] For remaining jobs $j$ put ${b_{j}' := percent}$ and ${jobsCount := 0}.$
\end{enumerate}
\STATE Output computed values $b_{j}'$.
\end{algorithmic}
\caption{Calculation of data bus consumption for a subset of jobs.}
\label{algo:DataBus}
\end{algorithm}

Moreover, the permutation is preliminary corrected in accordance with the partial order. We take at each step the next job in the permutation, for which all predecessors are already placed. 
% This method of capacity allocation is different from the concurrent network flow allocation, well-known in multicommodity flow problems (see e.g.~\cite{SM90}), where the ratio of the flow of each commodity to the predefined flow demand for that commodity must be the same for all commodities. We expect that the capacity allocation represented by Algorithm~1 is more adequate to the case of data bus information flows because in this case a software module has no explicit way to communicate its flow demand to the system.



\subsection{Mutation} %Scramble mutation based on insert and swap.

The mutation is applied with probability $P_{m}$.
We apply the classic mutation operators such as swap and shift~\cite{Holland1992}, as well as scramble mutation and heavy-tailed scramble mutation~\cite{Doerr2024}.

Scramble mutation operator works as follows. The operator
samples a number $n_p$ according to a Poisson distribution with mean $\lambda_{p} = 1$,
selects a random set of $n_p$ elements from $[1\dots n]$, and applies a random permutation to this set.

%Heavy-tailed Mutation Operators
We also apply a heavy-tailed scramble
mutation operator. We say that an integer random variable $X$ follows a
power-law distribution with parameters $\beta$ and $u$ if

\[
    Pr[X = i] = \left\{\begin{array}{lr}
       C_{\beta,u}i^{-\beta}, & \text{if $i \in [1\dots u]$,}\\
       0 & \text{otherwise.}\\
        \end{array}\right.
  \]
where $C_{\beta,u} = (\sum_{i=1}^u i^{-\beta})^{-1}$
denotes the normalization coefficient. We write
$X \sim pow(\beta, u)$ and call $u$ the range of $X$ and $\beta$ the power-law exponent.


The heavy-tailed scramble mutation (with power-law exponent $\beta$) is
the mutation operator that first samples a number $n_p \sim pow(\beta, n)$, then
selects a random subset of $n_p$ elements from $[1\dots n]$, and finally applies a random permutation on this set.

\subsection{Randomized Crossover and Optimal Recombination}

The cros\-so\-ver is applied with probability $P_{c}$.
We operate with randomized and optimi\-zed crossover operators. The classic randomized operators are used, such as Order crossover (OX), One point  crossover (1PX), Cycle crossover (CX) and Partially mapped crossover (PMX)~\cite{Kellegoz2008}. %+ ORP + Partial ORP

The Optimal Recombination Problem (ORP) is formulated as follows. Let us have $l$ parent permutations $\pi^1,\ \pi^2,\dots,\pi^l $. It is required to find a permutation~$\pi'$ such that:\\
1.~${\pi_i'\in \{\pi_i^1,\pi_i^2,\dots,\pi_i^l\}}$ 
for all ${i \in \{1, \ldots, n\}}$;\\
2.~${\pi'}$ has the optimum value of objective
function among all permutations that satisfy condition~1).

NP-hardness of the ORP in different cases  will be proved by the polynomial reduction of the well-known NP-hard problems: NUMERICAL MATCHING with TARGET SUMS and ORDERED PARTITION.


\textbf{NUMERICAL MATCHING with TARGET SUMS (strongly NP-hard)~\cite{GJ1979}}:
Given two $n$-element sets $A_1 = \{1,\dots,n\}$ and $A_2=\{ n+1,\dots, 2n_0\}$,
weights of all elements $e_i\in Z^+$, $i=1,\dots,2n_0$, and a vector of bounds $(B_1,\dots,B_{n_0})$ with positive integer coordinates.
The question is to decide whether a set $A_1\cup A_2$ can be partitioned
 into $n_0$ disjoint subsets $a_1,\ a_2,\dots,a_{n_0}$ such that each set $a_j$ contains exactly one element
from the sets $A_1$, $A_2$ and $\sum_{i\in a_j} e_i = B_j$.

\textbf{ORDERED PARTITION (ordinary NP-hard)~\cite{GJ1979}}:
Given an ordered set  $A=\{1,2,\dots,2n_0\}$
and weight $e_i$ of each element $i\in A$ such that $\sum_{i\in A} e_i=2B$ and $e_i<e_{i+1},\ i=1,\dots,2n_0-1$.
The question is to decide whether $A$ can be partitioned into two subsets
$A_1$ and $A_2$ so that
$$\sum_{i\in A_1} e_i=\sum_{i\in A_2} e_i=B,$$
and subset $A_1$ contains only one element from each pair ${2i-1},\ {2i},\ i=1,\dots,n_0$.
Note that $\vert  A_1\vert  =\vert  A_2\vert  =n_0$ in the case of existence.

\begin{theorem}
Optimal recombination problem with the makespan criterion and single processor jobs even for the given assignment of jobs to processors in parent solutions is ordinary NP-hard in the cases:\\
two parents, two processors and equal resource consumption;\\
two parents and unit  volumes of jobs;\\
and strongly NP-hard in the case of three processors, and unit  volumes of jobs.
\end{theorem}
\begin{proof}
1), 2) We will use the reduction from the Ordered Partition problem.

1) Put the number of jobs $n=2n_0$, the number of processors $m=2$. Jobs correspond to elements of the Ordered Partition problem, processing volume is $W_j=e_j$ and resource consumption $b_j=50\%$ for job $j=1,\dots,2n_0$. 
Threshold value for the makespan is $B$ and energy budget is $2B$, so, jobs may be executed only with unit speed.

Set the parent permutations for the first processor:
$\pi^{11} =(1,3,\dots,2n_0-1)$, $\pi^{12} =(2,4,\dots,2n_0)$ and 
parent permutations for the second processor:
$\pi^{21} =(2,4,\dots,2n_0)$, $\pi^{22} =(1,3,\dots,2n_0-1)$.

Permutation $\pi=(\pi^1,\pi^2)$, for which $\pi^1_i\in \{\pi^{11}_i, \pi^{12}_i\}$, $\pi^2_i\in \{\pi^{21}_i, \pi^{22}_i\}$, $i=1,\dots,n_0$, and 
makespan is bounded by $B$, exists if and only if the Ordered Partition Problem has a positive answer.

2) Put the number of jobs $n=2n_0$, the number of processors $m=n_0$. Jobs correspond to elements of the Ordered Partition problem, processing volume is $W_j=1$ and resource consumption is $b_j=\frac{100\times e_j}{B}\%$ for job $j=1,\dots,2n_0$. 
Threshold value for the makespan is $2$ and energy budget is $2B$, so, jobs may be executed only with unit speed.

Set the parent permutations for the $j$-th processor:
$\pi^{j1} =(2j-1,2j)$, $\pi^{j2} =(2j,2j-1)$, $j=1,\dots,n_0$.

Permutation $\pi=(\pi^1,\pi^2,\dots,\pi^{n_0})$, for which $\pi^j_i\in \{\pi^{j1}_i, \pi^{j2}_i\}$, $i=1,2,\ j=1,\dots,n_0$, and 
makespan is bounded by $2$, exists if and only if the Ordered Partition Problem has a positive answer. Here we want to divide the set of jobs into two parts of equal total data bus consumption if it is possible.

3) We will use the reduction from the Numerical Matching with Target Sums problem.
Put the number of jobs $n=3n_0$, the number of processors $m=3$. The first $2n_0$ jobs correspond to elements of the Numerical Matching with Target Sums problem, processing volume is $W_j=1$ and resource consumption is $b_j=\frac{100\times e_j}{M}$ for job $j=1,\dots,2n_0$. Jobs $2n_0+1,\dots,3n_0$ have unit volumes and resource consumption $b_j=\frac{100\times (M-B_j)}{M}$ for job $j=2n_0+1,\dots,3n_0$. Here $M$ is the sufficiently big constant.
Threshold value for the makespan is $n_0$ and energy budget is $3n_0$, so, jobs may be executed only with unit speed.

Put the $i$-th parent permutation for processors:\\
$\pi^{1i} =(i,i+1\ {\rm mod} n_0,\dots,i + n_0 - 1\ {\rm mod}\ n_0)$,\\
$\pi^{2i} =(n_0+i,n_0+i+1\ {\rm mod}\ 2n_0,\dots,n_0+i+ n_0 - 1\ {\rm mod}\ 2n_0)$,\\ 
$\pi^{3i} =(2n_0+1,\dots, 3n_0)$, $i=1,\dots,n_0$.

Permutation $\pi=(\pi^1,\pi^2,\pi^3)$, for which $\pi^j_i\in \{\pi^{jl}_i\}_{l=1}^{n_0}$, $i=1,2,\dots,\ n_0,\ j=1,\ 2,\ 3$, and 
makespan is bounded by $n_0$, exists if and only if the  Numerical Matching with Target Sums problem has a positive answer. Here we try to reorder jobs on the first two processors such that the data bus consumption is equal to $\frac{100\times B_t}{M}$  for unit intervals $t=1,\dots,n_0$ if possible.
\end{proof}

%\begin{theorem}
%Optimal recombination for the total completion time criterion is NP-hard even in the case of two processors and only one two-%processor job. (equal resource consumption and different durations OR different resource consumption and identical durations).
%\end{theorem}

\begin{theorem}
Optimal recombination problem with the total completion time criterion even for the given assignment of jobs to processors in parent solutions is ordinary NP-hard  in the cases:\\
at least one two-processor job, two parents, two processors and equal resource consumption for single-processor jobs;\\
two parents and unit  durations of jobs;\\
and strongly NP-hard in the case of three processors, and unit  durations of jobs.
\end{theorem}
\begin{proof}
We show the NP-hardness for the case, when energy resource is not considered. The provided reductions can be generalized to the case of energy resource using approaches from papers~\cite{ZakharovaSakhno2025} (see Theorem~1) and \cite{Kononov2023} (see Theorem 3.1).

1), 2) We will use the reduction from the Ordered Partition problem. This reduction is similar to the case of makespan criterion, but has unique properties due to the objective.

1) Put the number of jobs $n=2n_0+1$, the number of processors $m=2$. We have $2n_0$ single-processor jobs and one two-processor job. Single-processor jobs correspond to elements of the Ordered Partition problem, processing volume $W_j=e_j$ and resource consumption $b_j=50\%$ for job $j=1,\dots,2n_0$. Two-processor job is characterized by volume $W_{2n_0+1}=M> \sum_{i=1}^{n_0} (n_0+i+1) (e_{2i-1} + e_{2i}) + \frac{1}{2} \sum_{i=1}^{n_0}(e_{2i-1} + e_{2i})$ and resource consumption $b_{2n_0+1}=100\%$.
Threshold value for the total completion time is $L:=\sum_{i=1}^{n_0} (n_0+i+1) (e_{2i-1} + e_{2i}) + \frac{1}{2} \sum_{i=1}^{n_0}(e_{2i-1} + e_{2i})+M$, so, jobs may be executed only with unit speed.

We set parent permutations for the first processor:
$\pi^{11} =(1,3,\dots,2n_0-1, 2n_0 +1)$, $\pi^{12} =(2,4,\dots,2n_0, 2n_0+1)$, and 
parent permutations for the second processor:
$\pi^{21} =(2,4,\dots,2n_0, 2n_0+1)$, $\pi^{22} =(1,3,\dots,2n_0-1,2n_0+1)$.

Permutation $\pi=(\pi^1,\pi^2)$, for which $\pi^1_i\in \{\pi^{11}_i, \pi^{12}_i\}$, $\pi^2_i\in \{\pi^{21}_i, \pi^{22}_i\}$, $i=1,\dots,n_0+1$, and 
the total completion time is bounded by $L$, exists if and only if the Ordered Partition Problem has a positive answer. We want to divide single-processor jobs between two processors such that the two-processor job starts at time $\frac{1}{2} \sum_{i=1}^{n_0}(e_{2i-1} + e_{2i})$ if it is possible.

2) Put the number of jobs $n=2n_0$, the number of processors $m=n_0$. Jobs are single-processor and correspond to elements of the Ordered Partition problem, processing volume is $W_j=1$ and resource consumption $b_j=\frac{100\times e_j}{B}\%$ for job $j=1,\dots,2n_0$. 
Threshold value for the total completion time is $3n_0$, so, jobs may be executed only with unit speed.

We set parent permutations for the $i$-th processor as $\pi^{i1} =(2i-1,2i)$, $\pi^{i2} =(2i,2i-1)$, $i=1,\dots,n_o$ and prove NP-hardness similarly to the makespan criterion.

3) We will use the reduction from the Numerical Matching with Target Sums problem.
Put the number of jobs $n=3n_0$, the number of processors $m=3$. The first $2n_0$ jobs correspond to elements, processing volume  $W_j=1$, $size_j=1$ and resource consumption $b_j=\frac{100\times e_j}{M}$ for job $j=1,\dots,2n_0$. Jobs $2n_0+1,\dots,3n_0$ have unit volumes, $size_j=1$ and resource consumption $b_j=\frac{100\times (M-B_j)}{M}$ for job $j=2n_0+1,\dots,3n_0$.
Threshold value for the total completion time criterion is $3\sum_{i=1}^{n_0}i=3\frac{n(n+1)}{2}$, so, jobs may be executed only with unit speed.

Then we put parent permutations as for the makespan criterion and continue the proof similarly.
\end{proof}

Now we go to discussion of the solving methods for the ORP. 
Construct a bipartite graph $G=(J_{n},J,U)$ with two parts of the vertices set $J_n, J$
of equal sizes and the set of edges ${U=\{\{i,x\}:}$ ${i\in
J_{n},\ x\in\{\pi_i^1,\pi_i^2,\dots,\pi_i^l\}}\}$. The left part of the vertex set represents positions and the right part shows jobs.
By construction we see that there is a one-to-one correspondence between perfect matchings of $G$ and feasible permutations (Fig.~\ref{Graph:fig}).

\begin{figure}
  \includegraphics[width=0.4\linewidth]{Graph4.png}
  \caption{Graph $G=(X_{4},X,U)$ for parent permutations $\pi^1=(j_3,\ j_1,\ j_2,\ j_4)$, $\pi^2=(j_2,\ j_2,\ j_3,\ j_4)$, $\pi^3=(j_1,\ j_4,\ j_2,\ j_3)$, $\pi^4=(j_2,\ j_1,\ j_3,\ j_4)$ and possible perfect matchings.}
  \label{Graph:fig}
\end{figure}

A feasible schedule of the ORP can be found in polynomial time by solving the well known assignment problem~\cite{Munkres1957}, and the optimal solution may be computed in $O(n^{2.5} + n^2 n_{pm})$ time by enumerating perfect matchings (see, e.g., \cite{Uno1997}) in the corresponding bipartite graph $G$ ($n_{pm}$ is the number of perfect matchings) and computing objectives for appropriate schedules. Here time $O(n^{2.5})$ corresponds to compute one  perfect matching and time $O(n^2 n_{pm})$ is used for going from the current perfect matching to the next one and calculating the required metrics.

In the case of two parents we have the following optimistic property: ``Almost all'' pairs of parent solutions give the ORP with at most $n$ feasible solutions, that can be found in polynomial time~\cite{Eremeev2014}.
We also consider partially optimized crossover, where at most the given number of feasible solutions (the given number of perfect matchings) is considered in the solving method of the ORP. This number depends on the problem dimension (the number of jobs).  

The ORP can be formulated in terms of MIP subproblem, when we fix Boolean variables with identical values for parents and solve the subproblem on the rest variables. The previous research shown that the approach based on enumerating perfect matchings  demonstrates better results than MIP approach for scheduling problems on permutations (see, e.g., \cite{ZakharovaSakhno2025,ZakharovZakharova2024}).

\section{Convergence of the Evolutionary Algorithm}

%The convergence of the proposed algorithm was investigated and the average number of iterations to the first achievement of the optimum was estimated for the case when the search is aimed at finding the optimal schedule among those where the cores are maximally loaded with existing jobs and are not idle if there are still unfulfilled jobs.

Now we analyze the convergence to the optimum of the proposed algorithm and estimate the expected number of iterations in the suggestion that the energy-resource is not considered.
%We will see that the expected number of iterations is polynomial for the multi-machine problem in the case of constant number of orders, selecting parameters $N$ and $\frac{1}{P_{\rm mut}}$ as polynomial functions of the number of products and machines.

\begin{theorem}
\label{th:EArank}
The expected number of iterations of EA is bounded by $$O\left((n-1) \left(\frac{k^2n^2p_{\max}}{P_m (1-P_c)\Delta_p p_{fake}^{\min}}\right)^{n-1}\right),$$ 
if the rank selection is chosen as the selection operator.
Here $n$ is the total number of jobs, $k$ is the size of the population, $p_{fake}^{\min}=\min\{p_{fake}, 1-p_{fake}\}$, $p_{\max}$ is duration of the longest jobs with slowing effect due to common using of data bus, $\Delta_{p}$ is the duration portion, which is a multiple of all job durations taking into account possible slowing effect. 
\end{theorem}
\begin{proof} 
We denote by $\pi^*$ the permutation, corresponding to the starting times of jobs in optimal solution. Now we consider an arbitrary permutation $\pi^0$ from the initial population.  Let $d^0$ be the distance (the number of positions with different values) between $\pi^0$ and $\pi^*$. We will calculate upper bound on the expected  number of iterations required to obtain  $\pi^*$ from $\pi^0$.


We will go from $\pi^0$ to
$\pi^*$ in at most $(d^0-1)$ iterations only by means of mutation, where the distance between the selected permutation and the optimal one is decreased at each iteration. For the given pair of solutions a crossover operator is not applied with probability $(1-P_c)$, and for the given solution a mutation operator is applied with probability $P_m$.

We will consider such transition from $\pi^0$ to $\pi^*$, that at least one job is placed in the same position as in $\pi^*$ by the mutation at each iteration and the obtained permutation is selected at the next iteration.

The probability of an individual being selected in the rank selection operator is $\frac{2}{k(k+1)}$.
 And the probability that one of the jobs will be in the same position as in the optimal permutation after applying swap or insert mutation has a lower bound $\frac{1}{n^{2}}$. 
Thus, the probability of obtaining $\pi^*$ from $\pi^0$ in at most $d^0-1$ iterations is bounded by
$
\left( \frac{2}{k(k+1)} P_m \frac{1}{n^{2}} (1-P_c) \right)^{d^0 -1 }.
$
In construction of a schedule for permutation $\pi^*$ the fake jobs of necessary durations are placed before real jobs with probability no less $\left(\frac{\Delta_p p_{fake}^{\min}}{p_{\max}}\right)^{n-1}$. Here we suppose that the duration of a fake job is set as $k \Delta_p$, and $k$ is selected randomly from $\{1,\dots,\frac{p_{rest}}{\Delta_p}\}$, where $p_{rest}$ is the  rest duration of the largest job in the corresponding configuration (see Section~\ref{sec:constSol}).

Denote the estimation on the probability of constructing an optimal solution in at most $d^0-1$  iterations as 
$$
p^*:=\left( \frac{2}{k(k+1)} P_m \frac{1}{n^{2}} (1-P_c) \right)^{d^0 -1 } \cdot \left(\frac{\Delta_p p_{fake}^{\min}}{p_{\max}}\right)^{n-1}.
$$


Now we consider a series of $(d^0 -1)$ iterations. Let $S_i$ be an event indicating that an optimal solution is absent in the population of series $i$. Then the probability $P(S_i)\le 1-p^*$ for any prehistory, therefore, 
$ P(S_1\& \dots \& S_t) \le (1-p^*)^t.$

Let us denote by $\Xi$ the random variable equal to the number of the first series, when an optimal solution is obtained. We have 
$$E[\Xi]=\sum_{i=0}^{\infty}P(\Xi>i) = 1 + \sum_{i=0}^{\infty}  P(S_1\& \dots \& S_i)\le 1 + \sum_{i=0}^{\infty} (1-p^*)^i = \frac{1}{p^*}.$$

Thus, the expected number of iterations does not exceed:
$$T:=(d^0-1)\left(\frac{ k^2n^2 }{P_m (1-P_c)}\right)^{d^0-1}  \left(\frac{p_{\max}}{\Delta_p p_{fake}^{\min}} \right)^{n-1}.$$


Let us denote by $\Theta$ the random variable equal to
the number of iterations until the optimal solution is obtained, by $\pi^{1,0}$ the first individual of the initial population $\Pi^0$. Then, according to the formula of the total probability for conditional mathematical expectations, we have:
%, and by $E[\cdotp]$ the mathematical  expectation
$$E[\Theta]=\sum_{\pi\in \Pi^0}E[\Theta|\pi^{1,0}=\pi]\cdot P\{\pi^{1,0}=\pi\}\leq T \sum_{\pi\in \Pi^0}P\{\pi^{1,0}=\pi\}=T.$$

The statement follows from inequality $d^0\le n$ and the property that after the optimal solution is reached, such solution will be kept in each subsequent population.
\end{proof}

Similar theorem is also valid when we use tournament selection.
The probability that the required permutation will be selected as a parent by the $s$-tournament selection is no less than $\frac{1}{k^{s}}$.

\begin{theorem}
\label{th:EAtournament}
The expected number of iterations of EA is bounded by $$O\left((n-1) \left(\frac{k^sn^2p_{\max}}{P_m (1-P_c) \Delta_p p_{fake}^{\min}}\right)^{n-1}\right),$$ 
if $s$-tournament  selection is chosen as the selection operator.
\end{theorem}

Theorems~\ref{th:EArank} and \ref{th:EAtournament} guarantee that our EA almost surely converges to an optimum  as the number of iterations tends to infinity.

%Была исследована сходимость предложенного алгоритма и определена оценка среднего числа итераций до первого достижения оптимума для случая, когда поиск направлен на нахождение оптимального расписания среди тех, где ядра максимально загружаются имеющимися работами и не простаивают, если ещё имеются невыполненные работы. 

%Теорема 1. Генетический алгоритм GA в среднем не более чем за $O\left((n-1) \left(\frac{kn(k+1)(n-1)}{2P_m (1-P_c)}\right)^{n-1}\right)$ итераций впервые достигает оптимум задачи построения расписания на многоядерном процессоре с учетом взаимного влияния работ.

%Доказательство.  Вычислим вероятность  того, что из особи ξ за n-1 итерацию получится особь ξ*, представляющая оптимальное решение задачи. Вероятность особи быть выбранной в операторе ранговой селекции равна 2k(k+1). Вероятность того, что при мутации сдвига один из генов переместится на позицию, совпадающую с позицией из оптимального решения, равна Pm1n(n-1), при этом кроссинговер должен отсутствовать. Таким образом, вероятность получить из особи ξ особь ξ* за n-1 итерацию равна 2(1 - Pc)Pmk(k+1)n(n-1)(n-1), а среднее число итераций до достижения этого события не превосходит (n-1)kn(k+1)(n-1)2Pm(1-Pc)(n - 1). Теорема доказана. 

%Аналогичные теоремы справедливы и при использовании турнирной  селекции и мутации обмена.

%        \textbf{Теорема 1.} Предложенный генетический алгоритм в среднем не более чем за $O\left(n \left(\frac{k^2n^2}{P_m (1-P_c)}\right)^n\right)$ итераций впервые достигает оптимум, если в качестве оператора селекции выбрана ранговая селекция.
        
%        \textbf{Теорема 2.} Предложенный генетический алгоритм в среднем не более чем за $O\left(n \left(\frac{k^sn^2}{P_m (1-P_c)}\right)^n\right)$ итераций впервые достигает оптимум, если в качестве оператора селекции выбрана s-турнирная селекция.


\section{Computational Experiment}
    
The experiment was carried out on a computer with 16 GB of RAM and Intel Core i7-8565U 1.80 GHz CPU. 
For the computational experiment, the following procedures  from the Intel MKL (Math Kernel Library) are used as jobs:\\
-- copying a vector to another vector,\\
-- calculation of the sum of magnitudes of the vector elements,\\
-- calculation of a vector-scalar product and adding the result to a vector,\\
-- calculation of the QR factorization of a matrix.

    The choice of such procedures is due to the fact that they consume the data bus in different ways. The input data to the procedures has different sizes (for procedures with vectors, this is the vector length, for procedures with matrices, this is the matrix size). For vectors, the dimensions from 10 to 70~million elements were used, for matrices, the dimensions varied from 1000 to 1300. Data bus consumption for jobs  is calculated by the method presented in \cite{ErMalSakh2020}.
    Parameter $\alpha:=2$ for calculating energy consumption.

    Input parameters of the instances:\\
-- The number of jobs $n=50,\ 100$.\\
-- Precedence constraints: jobs without partial order and  binary tree.\\
-- The number of processors (cores) $m=12,\ 24$.\\
-- Data bus consumption $b_j\in \{4, 7, 8, 9, 10, 11\}$, in \%.

\subsection{Testing Evolutionary Algorithm} We carried out the experiment on EA with scramble mutation (SM) and heavy-tailed scramble mutation (H-SM) on series constructed for  $50$ and $100$ jobs with bitree partial order (B-PO) and without partial order (N-PO).

The total budget on the objective function calculations is 1.5 millions, the number of calculations before the next restart $n_{FC}$ is 200 thousands. We put weights in the adaptive scheme $w_1=1,\ w_2=0.8$ based on the preliminary computational experiment.
Numerical parameters of EA are tuned at the preprocessing stage by IRACE package (see Table~\ref{irace_params}). Here values were configured by testing on instances with $50$ jobs. For all experiments the number of parents in the optimized crossover was set to two and the maximum number of the considered permutations was set to $0.5\mathrm{log} n$ for the partially optimized crossover.

The lower bounds on objectives and energy consumption for jobs are calculated  using the convex models for both criteria, taking into account only energy resource and ignoring slowing due to data bus bandwidth~\cite{Kononov2022,Kononov2023}. The objective function deviations of solutions obtained by EA from the lower bound (LB) and from the objective of solutions found by the greedy algorithm (GR)~\cite{ErMalSakh2020} are presented in tables~\ref{resEACmaxNoPO}, \ref{resEACmaxBPO}, \ref{resEACsumNoPO} and \ref{resEACsumBPO}.


         \begin{table}[H]
            \begin{center}
                \begin{tabular}{ | r | r | r | r | r | r | r | r |r| }
                    \hline

&   \multicolumn{4}{r|}{$C_{\max}$} & \multicolumn{4}{r|}{$\sum_j C_j$} \\
\cline{2-9}
\textbf{param} & {SM,} & {H-SM,} & {H-SM,} & {SM,} & {SM,}  & {SM,}  & {H-SM,}  & {H-SM,}\\ 
\textbf{} & {N-PO} & {N-PO} & {B-PO} & {B-PO} & {N-PO}  & {B-PO}  & {B-PO}  & {N-PO}\\ 
                    \hline
                    $k$ & 232 & 246 & 200 & 238 & 244 & 228 & 198 & 202\\
                    %--population-size
                   $n_{elites}$  & 192 & 74 & 2 & 232 & 28 & 114 & 22 & 80\\
                   %--elites-count
                    select & s = 14 & rank & rank & rank & rank & rank & rank & rank\\
                    $p_{fake}$ & 0.88 & 0.52 & 0.5 & 0.87 & 0.74 & 0.48 & 0.22 & 0.7\\
                    %--probability-of-fake-job
                   % --mutation-type & shift & shift & shift & swap & shift &  shift & shift & swap\\
                 % $f_{ORP}$  & 0.75 & 0.5 & - & - & - & - & - & -\\
                    %--optimized-rate
                   % --poisson-lambda & 1 & - & - & 1 & 2 & 2 & - & -\\
                     $\beta$ & - & 1.44 & 1.5 & - & - & - & 1.17 & 1.16\\
                     %--heavy-tailed-beta
                   % --heavy-tailed-max-ratio & - & 0.4 & 0.5 & - & - & - & 0.16 & 0.17\\
                     $\lambda$ & 0.44 & 0.54 & 0.2 & 0.26 & 0.64 & 0.81 & 0.64 & 0.13\\
                     %--adaptive-lambda
                     $w_3$ & 0.12 & 0.21 & 0.3 & 0.29 & 0.51 & 0.53 & 0.69 & 0.65\\
                     %--min-weight
                    $\varepsilon$ & 0.064 & 0.03 & 0.01 & 0.065 & 0.061 & 0.054 & 0.026 & 0.04\\
                    %--adaptive-epsilon
                     $\delta$ & 0.08 & 0.085 & 0.01 & 0.042 & 0.082 & 0.08 & 0.076 & 0.011\\
                     %--adaptive-delta
                    \hline
                \end{tabular}
            \end{center}
            \caption{Values of parameters found by IRACE package.}
            \label{irace_params}
        \end{table}

         \begin{table}
            \begin{center}
                \begin{tabular}{ | r | r | r | r | r | r | r | r | r |}
                    \hline
                \textbf{} &   \multicolumn{4}{r|}{\textbf{50}} & \multicolumn{4}{r|}{\textbf{100}} \\
\cline{2-9}   
                   &  \multicolumn{2}{r|}{\textbf{SM}} & \multicolumn{2}{r|}{\textbf{H-SM}} & \multicolumn{2}{r|}{\textbf{SM}} & \multicolumn{2}{r|}{\textbf{H-SM}} \\ 
\cline{2-9} 
                   &  \textbf{LB} & \textbf{GR} &  \textbf{LB} & \textbf{GR} &  \textbf{LB} & \textbf{GR} &  \textbf{LB} & \textbf{GR} \\ 
                   \hline
                   \textbf{min} & 0.0 & 0.01 & 0.0 & 0.01 & 58.53 & 0.0 & 52.87 & 0.0 \\
                    \textbf{avg} & 0.9 & 12.71 & 0.84 & 12.79 & 65.18 & 0.1 & 59.32 & 3.86 \\
                     \textbf{max} & 1.23 & 24.27 & 1.19 & 24.57 & 76.06 & 5.2 & 65.96 & 12.17 \\

\hline
\end{tabular}
\end{center}
\caption{Results for the jobs without partial order and $C_{\max}$ criterion: relative deviation from the lower bound and from the solution of greedy algorithm~\cite{ErMalSakh2020}, \%.} % считаю по формуле (большее - меньшее) / меньшее * 100
\label{resEACmaxNoPO}
\end{table}

         \begin{table}
            \begin{center}
                \begin{tabular}{ | r | r | r | r | r | r | r | r | r |}
                    \hline
                \textbf{} &   \multicolumn{4}{r|}{\textbf{50}} & \multicolumn{4}{r|}{\textbf{100}} \\
\cline{2-9}   
                   &  \multicolumn{2}{r|}{\textbf{SM}} & \multicolumn{2}{r|}{\textbf{H-SM}} & \multicolumn{2}{r|}{\textbf{SM}} & \multicolumn{2}{r|}{\textbf{H-SM}} \\ 
\cline{2-9} 
                   &  \textbf{LB} & \textbf{GR} &  \textbf{LB} & \textbf{GR} &  \textbf{LB} & \textbf{GR} &  \textbf{LB} & \textbf{GR} \\ 
                   \hline
                   \textbf{min} & 11.55 & 0.0 & 11.55 & 0.0 & 78.03 & 0.0 & 58.65 & 0.0 \\
                    \textbf{avg} & 74.62 & 4.05 & 74.62 & 4.05 & 118.57 & 3.3 & 100.93 & 13.12 \\
                     \textbf{max} & 228.9 & 35.53 & 228.9 & 35.53 & 207.93 & 16.74 & 207.93 & 22.94 \\

\hline
\end{tabular}
\end{center}
\caption{Results for the jobs with bitree partial order and $C_{\max}$ criterion: relative deviation from the lower bound and from the solution of greedy algorithm~\cite{ErMalSakh2020}, \%.}
\label{resEACmaxBPO}
\end{table}

         \begin{table}
            \begin{center}
                \begin{tabular}{ | r | r | r | r | r | r | r | r | r |}
                    \hline
                \textbf{} &   \multicolumn{4}{r|}{\textbf{50}} & \multicolumn{4}{r|}{\textbf{100}} \\
\cline{2-9}   
                   &  \multicolumn{2}{r|}{\textbf{SM}} & \multicolumn{2}{r|}{\textbf{H-SM}} & \multicolumn{2}{r|}{\textbf{SM}} & \multicolumn{2}{r|}{\textbf{H-SM}} \\ 
\cline{2-9} 
                   &  \textbf{LB} & \textbf{GR} &  \textbf{LB} & \textbf{GR} &  \textbf{LB} & \textbf{GR} &  \textbf{LB} & \textbf{GR} \\  
                   \hline
                   \textbf{min} & 50.05 & 17.61 & 50.13 & 17.61  & 121.01 & 39.56 & 114.78 & 42.31\\
                    \textbf{avg} & 62.0 & 27.26 & 62.0 & 27.26  & 139.32 & 51.54 & 136.85 & 53.91\\
                     \textbf{max} & 74.04 & 34.31 & 74.04 & 34.31 & 154.97 & 68.27 & 155.28 & 72.0\\

\hline
\end{tabular}
\end{center}
\caption{Results for the jobs without partial order and $\sum_jC_{j}$ criterion: relative deviation from the lower bound and from the solution of greedy algorithm~\cite{ErMalSakh2020}, \%.}
\label{resEACsumNoPO}
\end{table}

         \begin{table}
            \begin{center}
                \begin{tabular}{ | r | r | r | r | r | r | r | r | r |}
                    \hline
                \textbf{} &   \multicolumn{4}{r|}{\textbf{50}} & \multicolumn{4}{r|}{\textbf{100}} \\
\cline{2-9}   
                   &  \multicolumn{2}{r|}{\textbf{SM}} & \multicolumn{2}{r|}{\textbf{H-SM}} & \multicolumn{2}{r|}{\textbf{SM}} & \multicolumn{2}{r|}{\textbf{H-SM}} \\  
\cline{2-9} 
                   &  \textbf{LB} & \textbf{GR} &  \textbf{LB} & \textbf{GR} &  \textbf{LB} & \textbf{GR} &  \textbf{LB} & \textbf{GR} \\ 
                   \hline
                   \textbf{min} & 90.61 & 0.0 & 90.61 & 0.0 & 162.88 & 0.0 & 157.69 & 0.3 \\
                    \textbf{avg} & 184.8 & 2.79 & 184.8 & 2.79 & 242.68 & 4.76 & 234.23 & 7.57 \\
                     \textbf{max} & 533.67 & 14.48 & 533.67 & 14.48 & 515.63 & 13.82 & 505.75 & 16.05 \\

\hline
\end{tabular}
\end{center}
\caption{Results for the jobs with bitree partial order and $\sum_j C_{j}$ criterion: relative deviation from the lower bound and from the solution of greedy algorithm~\cite{ErMalSakh2020}, \%.}
\label{resEACsumBPO}
\end{table}

As we can see, EA with SM and EA with H-SM demonstrate similar good results on instances with 50 jobs due to the big number of calculations for this dimension. EA with H-SM demonstrates sufficiently better results in comparison with EA with SM and greedy algorithm in the case of 100 jobs. The statistical analysis of experimental data using the Wilcoxon test shows that difference between the record values of  EA with H-SM and EA with SM is statistically significant at level less than $0.05$ on all series with 100 jobs. For the total completion time criterion EA shows more sufficient improvement of results of greedy algorithm on instances without partial order in comparison with instances with partial order. Deviation from the lower bound is better for the makespan criterion than for the total completion time criterion.

The results of $(\varepsilon,\delta)$-learning scheme show  that CX, 1PX and partially optimized crossover demonstrate leading positions during EA iterations. CX is the more effective randomized operator for instances without partial order and 1PX is the more effective randomized operator for instances with bitree order. Significant differences in the work of operators for criteria $\sum_{j} C_j$ and $C_{\max}$ are not identified. We also tested our EA based on adaptive scheme without optimized crossover operators on instances without partial order. The results are statistically significantly worse than the results with optimized operators.

% Выводы по кроссинговерам в адаптивной схеме
% CMAX, BITREE ORDER 
%-- для 100 работ явный лидер 1PX, остальные все хуже (CX, PMX, OX, OUR_CX)
% -- для 50 работ два лидера: OUR_CX, 1PX, рядом CX, остальные отстают значительно

% CSUM, BITREE ORDER
% -- для 100 работ три лидера: 1PX, CX, OUR_CX, остальные значительно отстают
% -- для 50 работ явный лидер 1PX, отстают от него CX, OUR_CX, остальные значительно хуже

% CSUM, NO ORDER
% -- для 100 работ два лидера CX, OUR_CX, недалеко от них 1PX, остальные значительно отстают
% -- для 50 работ лидеры CX, OUR_CX, остальные отстают

% Выводы по кроссинговерам в адаптивной схеме
% CMAX, BITREE ORDER 
%-- для 100 работ явный лидер 1PX, остальные все хуже (CX, PMX, OX, OUR_CX)
% -- для 50 работ два лидера: OUR_CX, 1PX, рядом CX, остальные отстают значительно

% CSUM, BITREE ORDER
% -- для 100 работ три лидера: 1PX, CX, OUR_CX, остальные значительно отстают
% -- для 50 работ явный лидер 1PX, отстают от него CX, OUR_CX, остальные значительно хуже

% CSUM, NO ORDER
% -- для 100 работ два лидера CX, OUR_CX, недалеко от них 1PX, остальные значительно отстают
% -- для 50 работ лидеры CX, OUR_CX, остальные отстают

\subsection{Comparison with Solver}

Here we present the results of evolutionary algorithm EA with heavy-tailed scramble mutation H-SM for small-size instan\-ces ($n=4,\ 6,\ 7,\ 8,\ 10$), and compare them to the results of the Gurobi solver reached withing 20 minutes by model (\ref{eqn:milp5})--(\ref{eqn:milp3}). Four series of  are considered: instances without partial order (no order), instances with bitree partial order (bitree), instances with one-to-many-to-one partial order (otmto) and instances with random partial order (random), see~\cite{ErMalSakh2020}.
Each series contains $192$ instances.

% 20 мин CPLEX
% оптимльные найдены для всех 192 примеров 
        \begin{table}[H]
            \begin{center}
                \begin{tabular}{ | r | r | r | r | r | }
                    \hline
                    \textbf{} & \textbf{no order} & \textbf{bitree} & \textbf{otmto} & \textbf{random} \\ \hline
                        min & 0.04 & 0.00 & 0.00 & 0.01 \\ 
                        avg & 1.47 & 1.82 & 0.97 & 1.94 \\ 
                        max & 19.89 & 20.53 & 19.20 & 17.63 \\ 
                    \hline
                \end{tabular}
            \end{center}
            \caption{Relative deviation of GA solution from Gurobi solution for 4 jobs, \%.}
            \label{ga_vs_mip_table}
        \end{table}   

% оптимальные НЕ найдены для 7 из 192 примеров
            \begin{table}[H]
            \begin{center}
                \begin{tabular}{ | r | r | r | r | r | }
                    \hline
                    \textbf{} & \textbf{no order} & \textbf{bitree} & \textbf{otmto} & \textbf{random} \\ \hline
                        min & 0.07 & 0.09 & -0.77 & -0.12 \\ 
                        avg & 0.15 & 0.83 & 3.30 & 1.99 \\ 
                        max & 0.29 & 9.89 & 26.98 & 13.88 \\
                    \hline
                \end{tabular}
            \end{center}
            \caption{Relative deviation of GA solution from Gurobi solution for 6 jobs, \%.}
            \label{ga_vs_mip_table}
        \end{table}  

% оптимальные НЕ найдены для 31 из 192 примеров
            \begin{table}[H]
            \begin{center}
                \begin{tabular}{ | r | r | r | r | r | }
                    \hline
                    \textbf{} & \textbf{no order} & \textbf{bitree} & \textbf{otmto} & \textbf{random} \\ \hline
                        min & -3.88 & -0.11 & -0.02 & 0.00 \\ 
                        avg & 0.10 & 0.37 & 2.36 & 1.82 \\ 
                        max & 0.49 & 4.73 & 25.19 & 14.47 \\ 
                    \hline
                \end{tabular}
            \end{center}
            \caption{Relative deviation of GA solution from Gurobi solution for 7 jobs, \%.}
            \label{ga_vs_mip_table}
        \end{table} 

% оптимальные НЕ найдены для 73 из 216 примеров
            \begin{table}[H]
            \begin{center}
                \begin{tabular}{ | r | r | r | r | r | }
                    \hline
                    \textbf{} & \textbf{no order} & \textbf{bitree} & \textbf{otmto} & \textbf{random} \\ \hline
                        min & -2.60 & -1.82 & -2.33 & -2.54 \\ 
                        avg & -0.06 & 0.40 & 1.41 & 1.72 \\ 
                        max & 0.37 & 10.41 & 20.96 & 13.78 \\ 
                    \hline
                \end{tabular}
            \end{center}
            \caption{Relative deviation of GA solution from Gurobi solution for 8 jobs, \%.}
            \label{ga_vs_mip_table}
        \end{table} 

% оптимальные НЕ найдены для 115 из 192 примеров
            \begin{table}[H]
            \begin{center}
                \begin{tabular}{ | r | r | r | r | r | }
                    \hline
                    \textbf{} & \textbf{no order} & \textbf{bitree} & \textbf{otmto} & \textbf{random} \\ \hline
                        min & -10.20 & -12.74 & -10.90 & 0.00 \\ 
                        avg & -0.51 & -1.45 & 0.04 & 1.22 \\ 
                        max & 0.36 & 0.36 & 5.84 & 8.75 \\ 
                    \hline
                \end{tabular}
            \end{center}
            \caption{Relative deviation of GA solution from Gurobi solution for 10 jobs, \%.}
            \label{ga_vs_mip_table}
        \end{table} 

Note that Gurobi solver was not found an optimal solution in all instances  (6 jobs: 7 instances, 7 jobs: 31 instances; 8 jobs: 73 instances; 10 jobs: 115 instances). EA demonstrates no more than 3.5\% deviation from the Gurobi solution on average and it shows an advantage as dimension increased.


\section*{Conclusion}
We proposed a new adaptive evolutionary algorithm with optimized
crosso\-ver and scramble mutation for the multi-processor scheduling with
resources. The problem specific decoding scheme is used allowing to provide assignment of processors and resources. The complexity of operators and convergence of the algorithm were theoretically analyzed. The experimental evaluation showed that the developed evolutionary algorithm demonstrated competitive results on instances generated based on procedures from the Intel MKL library.

\bigskip
\begin{thebibliography}{1} % Ссылки на литературу приводятся только на английском языке (даже если у источника нет англоязычной версии).


\bibitem{Doerr2024}
Doerr, B., Ghannane, Y., Ibn Brahim, M.: Runtime Analysis for Permutation-based Evolutionary Algorithms. Algorithmica \textbf{86}, 90-129 (2024)

\bibitem{Eremeev2014}
Eremeev A. and Kovalenko Y.: Optimal recombination in genetic algorithms for com-
binatorial optimization problems: part II. Yugoslav. J. Oper. Res. \textbf{24}(2),  165–186 (2014)

\bibitem{Eremeev2020}
Eremeev, A.V. and Kovalenko, Y.V.: A memetic algorithm with optimal recombination for the asymmetric travelling salesman
problem. Memetic Computing \textbf{12}, 23–36 (2020). \doi{10.1007/s12293-019-00291-4}

\bibitem{ErMalSakh2020}
Eremeev, A.V., Malakhov, A.A., Sakhno, M.A. and Sosnovskaya, M.Y.:  Multi-core Processor Scheduling with Respect to Data Bus Bandwidth. In: Olenev, N., Evtushenko, Y., Khachay, M., Malkova, V. (eds) Advances in Optimization and Applications. OPTIMA 2020. Communications in Computer and Information Science, vol. 1340, pp. 55-69. Springer, Cham (2020). 

\bibitem{GJ1979}
Garey, M.R., Johnson, D.S.: Computers and intractability. 
San Francisco: Freeman (1979)

\bibitem{Gerards2016}
Gerards, M.E.T., Hurink, J.L. and Holzenspies, P.K.F.: A survey of offline algorithms for energy minimization under deadline
constraints. J. Sched. \textbf{19}, 3-19 (2016). \doi{10.1007/s10951-015-0463-8}

\bibitem{Holland1992}
Holland, J.H.: Adaptation in Natural and Artificial Systems: An Introductory Analysis with Applications to Biology, Control, and Artificial Intelligence, The MIT Press (1992). \doi{10.7551/mitpress/1090.001.0001}

\bibitem{Jozefowska}
Jozefowska,~J., Weglarz,~J.:
Scheduling with resource constraints continuous resources. 
Handbook of Scheduling: Algorithms, Models, and Performance Analysis. 
24-1--24-15 (2004).

\bibitem{Kellegoz2008}
Kellegoz, T., Toklu, B. and Wilson, J.: Comparing efficiencies of genetic crossover operators for one machine total weighted tardiness problem. Applied Mathematics and Computation \textbf{199}(2), 590–598 (2008).

\bibitem{Kong2011}
Kong, F.,  Guan, N.,  Deng, Q., Yi, W.: Energy-efficient scheduling for parallel real-time tasks based on level-packing. Proceedings of the 2011 ACM Symposium on Applied Computing. pp. 635–640 (2011).

\bibitem{Kononov2022}
Kononov, A. and Zakharova, Y.: Speed scaling scheduling of multiprocessor jobs with energy constraint and makespan criterion. J Glob Optim \textbf{83}, 539–564 (2022). \doi{10.1007/s10898-021-01115-x}

\bibitem{Kononov2023}
Kononov, A.V. and  Zakharova, Y.V.: Speed scaling scheduling of multiprocessor jobs with energy constraint and total completion time criterion. Int. J. Artif. Intell. \textbf{21}(2),  109–129 (2023).

\bibitem{Lenstra1977}
Lenstra, J.K., Rinnooy Kan, A.H.G. and Brucker, P.:
Complexity of machine scheduling problems.
Ann. of Discrete Math. \textbf{1}, 343-362 (1977).

\bibitem{Lenstra1978}
Lenstra, J.K. and Rinnooy Kan, A.H.G.:
Complexity of scheduling under precedence constraints.
Oper. Res. \textbf{26}(1), 22-35 (1978).

\bibitem{Li2020}
Li, K.: Energy efficient scheduling of parallel tasks on multiprocessor computers. J Supercomput \textbf{60}, 223–247 (2020).

\bibitem{Merkel}
Merkel,~A., Stoess,~J. and Bellosa,~F. Resource-conscious scheduling for energy efficiency on multicore processors. In: Proc. 5th European Conference on Computer Systems (EuroSys'10), Paris, France. ACM, New York, NY, USA, 153–166 (2010). \doi{10.1145/1755913.1755930}

\bibitem{Munkres1957}
Munkres, J.: Algorithms for the assignment and transportation problems. Journal of the society for industrial and applied mathematics \textbf{5}(1), 32-38 (1957).

\bibitem{Nesbit06} 
Nesbit, K.J., Aggarwal, N., Laudon, J. and Smith, J.E.: 
Fair Queuing Memory Systems. In Proc. of 39th Annual IEEE/ACM International Symposium on Microarchitecture (MICRO'06), pp. 208--222 (2006)

\bibitem{Uno1997}
Uno, T.: Algorithms for enumerating all perfect, maximum and maximal matchings in bipartite graphs. In Algorithms and Computation: 8th International Symposium, ISAAC'97 Singapore, December 17–19, 1997 Proceedings 8. pp. 92-101. Springer Berlin Heidelberg (1997).

\bibitem{ZakharovaSakhno2024}
Zakharova Y.V. , Sakhno M.Y.:
Adaptive Genetic Algorithm with Optimized Operators for Scheduling in Computer Systems. In: IFIP Advances in Information and Communication Technology.2024.V.Part 1- Intelligent Information Processing XII : 13th IFIP TC 12 International Conference, IIP 2024, Shenzhen, China, Proceedings. pp. 317-328 (2024). \doi{10.1007/978-3-031-57808-3\_23}

\bibitem{ZakharovaSakhno2025}
Zakharova, Y. and Sakhno, M.:
Complexity and heuristic algorithms for speed scaling scheduling of parallel jobs with energy constraint. 
Journal of Computational and Applied Mathematics \textbf{457} (2025)
\doi{10.1016/j.cam.2024.116254}

\bibitem{ZakharovZakharova2024}
Zakharova, Y.V. and Zakharov, A.O.:  Integer Programming Models and Metaheuristics for Customer Order Scheduling. In: Eremeev, A., Khachay, M., Kochetov, Y., Mazalov, V., Pardalos, P. (eds) Mathematical Optimization Theory and Operations Research: Recent Trends. MOTOR 2024. ССIS, vol. 2239, pp.  276–290 Springer, Cham (2024). \doi{10.1007/978-3-031-73365-9\_19}

\bibitem{Zakharova2025}
Zakharova, Y.V.:  Population Local Search for Single Processor Energy Efficient Scheduling Problem. In: Sergeyev, Y.D., Kvasov, D.E., Astorino, A. (eds) Numerical Computations: Theory and Algorithms. NUMTA 2023. Lecture Notes in Computer Science, vol. 14476. P. 400-408. Springer, Cham (2025). https://doi.org/10.1007/978-3-031-81241-5\_35 (2025).

\bibitem{Zhuravlev}
Zhuravlev,~S., Blagodurov,~S. and Fedorova,~A.:
Addressing shared resource contention in multicore processors via scheduling. In:
Proc. 15th International Conference on Architectural Support for Programming Languages and Operating Systems (ASPLOS'10), Pittsburgh, USA. 
ACM, New York, NY, USA, pp. 129–142 (2010). \doi{10.1145/1735970.1736036}.
\end{thebibliography}
\end{document}

\section{Introduction}
In this article, we discuss some aspects of   commutative algebras \cite{2}. Let
\begin{equation}\label{f1}
 A=B.
\end{equation}

\begin{theorem}
Text of the theorem.
\end{theorem}

\begin{proof}
Let us consider equation \eqref{f1}.
\end{proof}


\bibitem{1} D.G. Northcott,
\href{https://doi.org/10.1017/CBO9780511565908}{\it Ideal Theory}, Cambridge University Press, Cambridge, 1953.

\bibitem{2} I.I. Ivanov,
\href{https://doi.org/10.1002/cpa.20282}{\it Some properties of commutative algebras}, Siberian Electronic
Mathematical Reports, {\bf 1} (2004), 142--143.

\bibitem{3} A.V. Tetenov, M. Samuel, D.A. Vauilin,
\href{https://doi.org/10.21538/0134-4889-2017-23-4-281-291}{\it On dendrites generated by polyhedral systems and their ramification points}, Trudy Inst. Mat. Mekh. UrO RAN, \textbf{23}:4 (2017), 281--291.