Методы обучения с подкреплением для класса задач теории расписания

Проблема распределения связанных между собой задач между ис-
полнителями присутствует во многих областях нашей жизни. В качестве
примера можно рассмотреть две такие области: облачные вычисления и
энергетика.
Потребность общества в вычислительных ресурсах растет из года в
год весьма стремительно, а появление новых технологий только подстеги-
вает взрывной рост. Как пример, рост популярности нейронных сетей при-
вел к появлению запроса на высокопроизводительные вычисления с тен-
зорами, что сильно увеличило спрос на видеокарты (GPU), которые ранее
использовались в основном в узкоспециализированных задачах (компью-
терная графика, симуляция физики). Нейронные сети внедряются повсе-
местно, что повлекло за собой внедрению специализированных вычисли-
тельных модулей в потребительской электронике, даже в мобильной тех-
нике.
Хоть рост вычислительной мощности индивидуальных устройств в
целом следует знаменитому закону Мура, приближение к физическим огра-
ничениям технического процесса производства процессоров и кремния как
материала, становится очевидно [1], что локальные вычисления далеко не
всегда смогут удовлетворять нужды пользователей.
Появление Apache Hadoop в 2006 году позволило популяризировать
распределенные вычисления, показав преимущества горизонтальной инте-
грации и параллельных вычислений. Сейчас рынок облачных (распреде-
ленных) вычислений оценивается в 760 миллиардов долларов, и только
продолжит расти [2].
При взаимодействии большого числа вычислительных узлов возни-
кает проблема управления: как оптимально распределять связанные меж-
ду собой вычислительные задачи? На эту проблему можно посмотреть с
различных точек зрения: оптимизация по числу единовременно задейство-
ванных ресурсов, энергоэффективности, длительности выполнения задачи,
затрачиваемым ресурсам, стоимости. Данную проблему в математике ре-
шает класс алгоритмов теории расписаний.
Алгоритмы теории расписаний долго применялись в данной области,
но развитие нейронных сетей и алгоритмов обучения с подкрепление поз-
волило превзойти классические эвристики [3].
Отдельно можно выделить проблему построения расписания на на-
правленных ациклических графах. Для некоторых вычислительных задач
уже заранее может быть известен набор подзадач, связи между ними и по-
следовательность их выполнения, представляющий собой вычислительных
граф. К таким задачам относится обучение нейронных сетей, декодирова-
ние генома.
Если же рассматривать энергетику, то рост так называемой зеленой
экономики способствует к всё более широкому использованию возобновля-
емых источников энергии. Два наиболее популярных – солнечная и ветря-
ная энергия имеют один существенный недостаток: непостоянство. Энер-
гия ветра, преобразуемая в электричество ветряными электрогенератора-
ми, может быть весьма непредсказуемой – в день с сильным ветром энергии
может быть переизбыток, в то время как в штиль энергии может не быть
совсем. Солнечная энергия же циклична, нам хорошо известен промежуток
времени, когда её возможно генерировать. Но здесь возникает известная в
энергетике проблема – что делать при резком скачке спроса на электри-
чество? Освещение и отопление в большей степени требуется ночью, когда
солнце уже не светит.
Хранение полученный из таких источников энергии может серьёзно
повысить их эффективность и привлекательность для потребителя, даже
на уровне отдельного домохозяйства [4]. Баланс между запасанием энергии
из нескольких непостоянных источников, продажей её обратно в электро-
сеть (популярно в Европе и США), и расходом сейчас может представлять
из себя комплексную оптимизационную задачу.
Как и в случае с распределенными вычислениями, мы можем оптими-
зировать по уровню использования, энергоэффективности, цене. Возника-
ет задача распределения нагрузки, получаемой из различных источников
между потребителями и устройствами хранения. Если же уровень потреб-
ления электроэнергии известен заранее или может быть достаточно точно
предсказан, можно выстроить граф подзадач потребления энергии и рас-
пределять каждую подзадачу на один из генераторов энергии.
Две приведенные выше области, на первый взгляд различные, имеют
один и тот же набор оптимизационных задач – распределение связанных
между собой задач между исполнителями. Для их решения возможно эф-
фективно применить Reinforcement Learning, который превосходит клас-
сические алгоритмы теории расписаний, что и будет показано в данной
работе.
Постановка задачи
Пусть задан направленный ациклических граф G = (V, E), где V =
v1 , …, vn – множество вершин графа, представляющих собой задачи, E –
множество ребер графа. Все вершины и ребра имеют веса: вес вершины Wvi
представляет собой трудозатраты на исполнение задачи, вес ребра Wi,j в
свою очередь представляет собой трудозатраты исполнителя при переклю-
чении на новую задачу. Каждое ребро (i, j) ∈ E представляет собой отно-
шение предшествования, задача не может начать своё выполнение, пока не
были выполнены все предшествующие задачи.
Вершина без предшественников называется входной вершиной, без
наследников – выходной. Если вершин без предшественников несколько,
то все они становятся наследниками псевдо-входной вершины с нулевым
весом как самой вершины, так и исходящих из неё рёбер. По аналогии,
если выходных вершин несколько, то они все получат единого наследника
с нулевым весом вершины и входящих в неё ребер. Данное требование не
несет в себе практической цели для данной работы, но было введено с
целью согласования с возможными требованиями алгоритмов для данного
класса задач, по аналогии с работами
Введем понятие исполнителя – агента, который выполняет задачи.
Пусть задано 3 типа исполнителя: small, medium, large. Каждый из ис-
полнителей принадлежит к определенному типу, единственное их отли-
чие будет заключаться в значении их мощности – параметра, характе-
ризующего эффективность исполнителя при выполнении задачи. Пусть
P = {Psmall , Pmedium , Plarge } – множество параметров мощности. Пусть за-
дано множество исполнителей M = {m1P∗ , …, mkP∗ }. Для исключения три-
виальных решений будем полагать, что k < n. Введем pred(vi ), succ(vi ) - множества непосредственных предшествен- ников и наследников соответственно. Пусть comp(mjP∗ ) - множество выпол- ненных исполнителем mjP∗ . Тогда длительность выполнения задачи vi на mjP∗ будет вычисляться как