\section{Сведение к задаче целочисленного линейного программирования} \label{sec:3_reduce_description} \index{3_reduce_description} \hspace{0.47cm} Опишем предложенную в данной работе схему сведения поставленной задачи к задаче ЦЛП. Для представления расписания, т.е. перестановки вершин графа $G = (V, E)$, воспользуемся подходом на основе переменных предшествования, описанном в \cite{BAKER} и первоначально предложенном в \cite{MANNE}. Поскольку этот подход использует длительности работ, формально положим длительность каждой работы равной 1. В рамках указанного подхода используются бинарные переменные предшествования: \begin{multline*} \begin{gathered} \forall i, j \in V, i \neq j: \\ m_{ij} = \begin{cases} 1, &\text{если вершина $i$ стоит в перестановке раньше вершины $j$}\\ 0, &\text{в противном случае} \end{cases} \end{gathered} \end{multline*} Также используются целочисленные переменные $s_j, j \in V$, которые задают время старта соответствующей работы $j$, в нашем случае равное ее позиции в расписании, считая с 0. Чтобы совокупность переменных $m_{ij}$ и $s_j$ задавала линейный порядок вершин графа с соблюдением заданного графом частичного порядка, на нее накладываются ограничения (1) -- (5) \citeappendix{BAKER}{Appendix C}. \[s_j = \sum_{i \in V}m_{ij}, \forall j \in V \eqno(1)\] \[m_{ij} + m_{ji} = 1, \forall i,j \in V, i \neq j \eqno(2)\] \[m_{ij} = 1, \forall (i,j) \in E \eqno(3)\] \[s_i + 1 \le s_j + |V|(1 - m_{ij}), \forall i,j \in V, i < j \eqno(4)\] \[s_j + 1 \le s_i + |V|m_{ij}, \forall i,j \in V, i < j \eqno(5)\] Для удобства будем считать, что \[m_{ii} = 1, i \in V \eqno(6)\] Ограничение (1) определяет, что позиция вершины в перестановке равна числу вершин, предшествующих ей в перестановке. Ограничение (2) требует, чтобы для каждой пары вершин одна из них стояла раньше другой. Ограничение (3) гарантирует частичный порядок на множестве вершин, заданный графом $G$. Ограничения (4), (5) вместе с ограничением (1) исключают цикличность перестановки, а именно задают условие: для каждой пары вершин $i, j$ либо $j$ расположена в расписании позже чем $i$ (значит, $s_i + 1 \le s_j$), либо $i$ расположена в расписании позже чем $j$ (значит, $s_j + 1 \le s_i$ ). В правых частях ограничений (4), (5) $|V|$ играет роль достаточно большого положительного числа, так чтобы в зависимости от значения $m_{ij}$ только одно из этих двух ограничений было содержательным, а второе заведомо выполнялось. Вводить ограничения (4), (5) для пар $i, j$ при $i$ > $j$ избыточно, поскольку ограничения уже введены для соответствующих пар $j, i$. Теперь необходимо ввести целевую функцию на расписании. Обозначим через $R_k$, $k \in V$, объем ресурса, который требуется при выполнении работы $k$, включая ресурс, требуемый для результата самой работы $k$. Введем переменную $F$ и ограничения для нее: \[F \ge R_k, \forall k \in V \eqno(7)\] С учетом этих ограничений, исходная задача сводится к минимизации целевой функции, равной переменной $F$: \[\min F \] Теперь надо выразить $R_k$ с использованием переменных $m_{ij}$. Для этого достаточно найти все работы $i$, выполняющиеся до работы $k$, т.е. $m_{ik} = 1$, результат выполнения которых требуется либо самой работе $k$, либо хотя бы одной работе $j$, $(i,j) \in E$, выполняющейся после работы $k$; для случая $m_{ik} = 1$ при $i = k$ считаем, что результат работы «требуется ей самой», т.к. ресурс под него отводится до высвобождения ресурса работой. Введем переменные \begin{equation*} \forall i,k \in V: y_{ik} = \begin{cases} 1, &\text{если $m_{ik} = 1$ и $\exists j \in V: ((i,j) \in E) \wedge (m_{kj} = 1)$}\\ 1, &\text{если $i = k$}\\ 0, &\text{в противном случае} \end{cases} \end{equation*} При введенных таким способом $y_{ik}$ верно, что \[R_k = \sum_{i \in V}r_iy_{ik}, \forall k \in V \] Зададим линейные ограничения на переменные $y_{ik}$: \[y_{ii} = 1, \forall i \in V \eqno(8)\] \[y_{ij} = 1, \forall (i,j) \in E \eqno(9)\] \[y_{ik} \le m_{ik}, \forall i,k: i \neq k, (i,k) \notin E \eqno(10)\] \[y_{ik} \le \sum_{(i,j) \in E}m_{kj}, \forall i,k,j: i \neq k, (i,j) \in E, (i,k) \notin E \eqno(11)\] \[y_{ik} \ge m_{kj} + m_{ik} - 1, \forall i,k,j: i \neq k, (i,j) \in E, (i,k) \notin E \eqno(12)\] Ограничение (8) показывает, что результат работы «требуется ей самой», т.к. ресурс под него отводится до высвобождения ресурса работой. Ограничение (9) гарантирует, что результат работы $i$ будет храниться до завершения выполнения всех ее прямых потомков $j$. Ограничение (10) гарантирует, что, если работа $k$ находится в расписании перед работой $i$, то результат работы $i$ для работы $k$ храниться не будет. Ограничение (11) гарантирует, что, если все прямые потомки $j$ работы $i$ находятся в расписании до работы $k$, то результат работы $i$ для работы $k$ храниться не будет. Ограничение (12) гарантирует, что результат работы $i$ будет храниться во время выполнения $k$, если хотя бы один прямой потомок $j$ работы $i$ стоит в расписании позже $k$. Итого, исходная задача сводится к задаче ЦЛП вида: \[\min F \] с переменными $m_{ij}$, $s_j$, $y_{ij}$, $F$ и ограничениями (1 – 12). Число переменных задачи ЦЛП: \[2|V|^2 + |V| + 1.\] Число ограничений задачи ЦЛП: \[|V| + (|V|^2 - |V|) + |E| + (|V|^2 - |V|) + |V| + |V| + |V| + |E| + (|V|^2 - |V| - |E|) + \] \[+(|V|^2 - |V|*p - |V| + p - |E|) + |V|*|E| - |E| - \sum_{i=1}^{|V|} l_i^2 = \] \[= 4|V|^2 + |V|*|E| - |V|*p - |E| + p - \sum_{i=1}^{|V|} l_i^2,\] где $p$ — число вершин без потомков, $l_i$ — число потомков $i$-ой вершины.