Full Text

Введение. Теория расписаний - важная область прикладной математики, имеющая многочисленные и разнообразные применения [1, 2]. Потребность в составлении расписаний, оптимальных по какому-либо критерию, часто возникает на практике, например, при формировании последовательности исполняемых заданий в многопроцессорных вычислительных системах [3]. Правильный подбор такой последовательности позволяет экономить ресурсы - общее время выполнения, объем используемой памяти и задействованные вычислительные мощности. Одной из проблем теории расписаний является так называемая конвейерная задача, которая, как известно, является NP-трудной для k-этапных заданий при k > 2 [4, 5]. Её решение для системы из n заданий с помощью полного перебора всех n! возможных последовательностей выполнения работ при больших n практически не осуществимо, а точных полиномиальных алгоритмов для её решения до сих пор не найдено. Поэтому актуальной задачей является поиск эффективного алгоритма. Стоит отметить, что для частного случая конвейерной задачи, когда число этапов равно двум, существует точный полиномиальный алгоритм Джонсона [6]. Кроме того, для случая, когда число этапов k > 2, известен так называемый фронтальный алгоритм, относящийся к классу быстрых приближенных алгоритмов для решения конвейерной задачи [7]. В данной работе авторами предложен новый подход для решения конвейерной задачи, а именно лексикографический алгоритм, основанный на лексикографической сортировке символьных строк, сопоставленных по некоторому правилу каждому из заданий. Данные символьные строки содержат специальным образом структурированную информацию о длительности каждого этапа задания. Как показало тестирование, проведенное на большом наборе входных данных, предложенный алгоритм в подавляющем большинстве случаев имеет более высокую точность в сравнении с фронтальным алгоритмом. Постановка задачи. Конвейерная задача заключается в следующем: пусть i - номер этапа задания (и номер исполнителя, ), j - номер задания ( ), - действительная матрица с положительными элементами размеров k×n (где k - количество этапов и исполнителей, n - количество заданий), у которой элемент определяет время выполнения i-го этапа j-го задания i-м исполнителем. Требуется составить оптимальное расписание, т.е. найти последовательность выполнения всех заданий за минимальное время, удовлетворяющую следующим нескольким ограничениям: 1. Исполнитель не может приступить к выполнению своего этапа задания, пока не будут завершены все предыдущие этапы этого задания (поэтому задание не может выполняться одновременно несколькими исполнителями). 2. Один исполнитель не может одновременно выполнять несколько заданий [8]. Под временем выполнения всех заданий в данном случае понимается длительность временного промежутка с момента начала работы первого исполнителя до момента завершения работы k-го исполнителя. Фронтальный алгоритм. Чтобы решить конвейерную задачу для набора заданий с числом этапов более двух, можно применить быстрый приближенный фронтальный алгоритм, который относится к классу «жадных алгоритмов» - аналогу метода градиента для непрерывных задач [7]. Сначала для j-го задания находится величина его суммарной трудоемкости, Задания выполняются в порядке невозрастания (либо неубывания) величин Таким образом, предпочтение отдается заданиям с максимальной (либо минимальной) суммарной трудоемкостью. Далее будет приведен пример работы фронтального алгоритма на конкретном наборе из четырех трехэтапных заданий. Лексикографический алгоритм. Авторами предлагается следующий лексикографический алгоритм: 1. Для каждого выполняется сортировка длительностей всех этапов j-го задания в невозрастающем порядке. Номера этапов после сортировки записываются в виде символьной строки (классификации). Например, если трехэтапное задание j имеет длительности этапов то это задание получает классификацию 3.1.2. 2. Полученные классификации заданий сортируются лексикографически в порядке убывания, поэтому в первую очередь будут выполнены задания, последние этапы которых имели наибольшую длительность по сравнению с длительностями остальных этапов этого же задания. Как будет показано далее, такая стратегия позволяет уменьшить потенциальные простои в ожидании возможности начать выполнение отдельных этапов для последующих заданий. Ниже приведен псевдокод предлагаемого алгоритма. public class Work { public int id; //номер задания public int[] part; //массив этапов (содержит длительность) public string leks; //лексикографический порядок } public static List<Work> Function(List<Work> works, int n, int k) //n - количество заданий, k - количество этапов { foreach(Work w in works) { int[] mas = new int[n]; //массив номеров этапов for (int i = 0; i < k; i++) mas[i] = i; Array.Sort(w.part, mas); //сортировка массива этапов по их длительности в порядке возр. Array.Reverse(mas); //по убыванию (самый длинный этап вначале) w.leks = mas[0].ToString(); //перевод массива в лексикограф. порядок for (int i = 1; i < k; i++) { w.leks += "."; w.leks += mas[i].ToString(); } } List<Work> result = list.OrderByDescending(x => x.leks). ThenByDescending(x => x.part[x.leks[0] - '0']).ToList(); //сортировка заданий по убыванию лексикографического порядка, затем задания с одинаковым лексикографическим порядком сортируются в порядке убывания длительности максимального этапа return result; } Заметим, что предлагаемый лексикографический алгоритм является приближенным, поскольку не всегда находит оптимальное расписание. Исследование погрешности алгоритмов. Рассмотрим пример работы фронтального и лексикографического алгоритмов на конкретном наборе входных данных, состоящем из четырех трехэтапных заданий, т.е. n = 4, k = 3. Пусть задания имеют следующие длительности: первое задание - t11 = 7, t21 = 1, t31 = 10, второе задание - t12 = 10, t22 = 10, t32 = 2, третье задание - t13 = 3, t23 = 4, t33 = 4, четвертое задание - t14 = 6, t24 = 3, t34 = 1. Фронтальный алгоритм в качестве ответа выдает последовательность выполнения заданий 4, 3, 1, 2, что соответствует расписанию длительности 38 единиц и имеет относительную погрешность 12 % по сравнению с точным ответом. Данное решение изображено на рис. 1 в виде диаграммы Ганта, где указаны длительности заданий, а также моменты начала и окончания выполнения каждого из этапов [9]. Рис. 1. Результат работы фронтального алгоритма Предложенный лексикографический алгоритм предлагает иную последовательность выполнения заданий 3, 1, 2, 4, которая является правильной и представляет собой искомое оптимальное расписание, требующее для выполнения всего 34 единицы. Действительно, классификации заданий в данном примере представляют собой следующие символьные строки соответственно: 3.1.2, 1.2.3, 3.2.1, 1.2.3. Лексикографически наибольшей является строка 3.2.1, далее по убыванию идет строка 3.1.2, затем две одинаковых строки 1.2.3 и 1.2.3. Это соответствует последовательности выполнения заданий 3, 1, 2, 4 и расписанию, изображенному на рис. 2. Для точного решения конвейерной задачи известен также метод ветвей и границ [10]. Для получения верхней оценки в этом методе можно, в частности, использовать приближенные алгоритмы. Однако для более качественной оценки, от которой существенно зависит скорость работы такого метода, требуются более точные алгоритмы, поэтому актуален поиск приближенных быстрых алгоритмов с высокой точностью [7]. Также на практике используются эвристические, метаэвристические и гибридные алгоритмы [11, 12]. К примеру, усовершенствованный алгоритм дифференциальной эволюции решает конвейерную задачу с погрешностью около 3 % [13]. Приближенный итеративный алгоритм позволяет решать задачу со средней погрешностью 12 % [14]. Рис. 2. Результат работы лексикографического алгоритма Для сравнения погрешности лексикографического и фронтального алгоритмов разработаны программные модули на языке программирования C# и проведено исследование на ПК с тактовой частотой 1,7 GHz в среде разработке Visual Studio 2013. Длительности этапов случайным образом генерировались из диапазона [1, 50] при количестве заданий n в пределах от 2 до 9 и числе этапов k в пределах от 2 до 12. На рис. 3 и 4 изображены соответственно графики зависимости относительной погрешности лексикографического и фронтального алгоритмов от количества этапов и числа заданий. Для каждого фиксированного количества этапов и числа заданий сгенерировано 100 000 тестов. Общее количество тестов равно 8 800 000. На данных тестах лексикографический алгоритм демонстрирует лучшую точность по сравнению с фронтальным алгоритмом для набора тестов, где n > k , т.е. количество заданий больше числа исполнителей. Также стоит отметить, что для двухэтапных заданий средняя погрешность лексикографического алгоритма равна около 1 %, а максимальная полученная погрешность для лексикографического и фронтального алгоритмов составила 51 и 53 % соответственно. Рис. 3. Зависимость погрешности лексикографического алгоритма от количества заданий и этапов Для большего количества заданий (100 заданий, количество этапов случайным образом генерировалось в диапазоне от 5 до 10) сгенерировано 100 000 тестов, среди которых в 81 % случаях ответ лексикографического алгоритма был точнее, чем фронтального алгоритма. Временная сложность алгоритмов. Сложность лексикографического алгоритма зависит от сложности выбранного типа сортировки. К примеру, для сортировки со сложностью лексикографический алгоритм имеет следующую сложность: O(nk(logk + logn)), где k - количество этапов (и исполнителей), n - количество заданий. Такая сложность алгоритма обусловливается тем, что сначала необходимо отсортировать этапы для каждого задания, а затем и сами задания через лексикографическую сортировку соответствующих классификаций. Для оценки временной сложности алгоритмов проведено исследование зависимости времени их работы от количества этапов (в пределах от 10 до 1000) и количества заданий (в пределах от 10 до 10 000). Для обоих алгоритмов рост количества этапов серьезнее влияет на время, чем количество заданий. Несмотря на это, для задачи большой размерности 1000×10 000 (количество этапов, количество заданий) время работы лексикографического алгоритма составляет примерно 6,5 мин, а время работы фронтального алгоритма - 3 с. Для сравнения стоит отметить, что метод ветвей и границ решает задачу размерности 5×10 за 51 с [7]. Рис. 4. Зависимость погрешности фронтального алгоритма от количества заданий и этапов В табл. 1 и 2 продемонстрированы данные о времени работы (в секундах) лексикографического и фронтального алгоритма соответственно. Таблица 1 Время работы лексикографического алгоритма (в секундах) Количество этапов Количество заданий 10 100 1000 10 000 10 0,00025 0,002 0,024 0,35 100 0,006 0,05 0,49 5 1000 0,35 3,45 35,6 389,7 Таблица 2 Время работы фронтального алгоритма (в секундах) Количество этапов Количество заданий 10 100 1000 10000 10 0,00004 0,0003 0,003 0,04 100 0,0002 0,002 0,02 0,23 1000 0,0014 0,015 0,25 2,8 Выводы. Проведенное исследование включало в себя разработку нового лексикографического алгоритма для решения конвейерной задачи с числом этапов более двух. Разработанный алгоритм был реализован в виде программного продукта. Для его тестирования был подготовлен большой пакет тестовых заданий. Для заданий небольшой размерности точный ответ был предварительно получен с помощью программного модуля, реализующего тривиальный алгоритм, представляющий собой полный перебор всех возможных вариантов и требующий экспоненциального времени работы. Кроме того, для сравнения работы предложенного лексикографического и известного фронтального алгоритмов последний также был реализован в виде программного модуля. Необходимо отметить, что предложенный авторами лексикографический алгоритм имеет простую внутреннюю логику, легко реализуем в виде программного продукта и может применяться на практике для приближенного решения задач большой размерности. Алгоритм имеет низкую относительную погрешность, в особенности для комплекса работ, где количество заданий больше, чем количество этапов. В большинстве случаев алгоритм находит более близкое к оптимальному решение, чем существующий фронтальный алгоритм. Погрешность лексикографического алгоритма и время его работы увеличиваются с увеличением количества заданий и количества этапов. Например, задачу размерности 1000×1000 алгоритм решает примерно за 35 с, что вполне приемлемо, если учесть, что единственный известный на данный момент точный алгоритм для решения конвейерной задачи такой размерности представляет собой полный перебор всех возможных вариантов, не осуществимый из-за неприемлемо значительных временных затрат.

About the authors

A. A Chusovliankin

National Research University «Higher School of Economics»

Email: lixich@mail.ru

V. V Morozenko

National Research University «Higher School of Economics»

Email: v.morozenko@mail.ru

References

Statistics

Views

Abstract - 21

PDF (Russian) - 15

Refbacks

• There are currently no refbacks.