Abstract

Abstract

Рассматривается известная задача о выборе заявок или процессов, имеющая большое практическое значение. На основе сформулированных очевидных утверждений строится новый алгоритм решения данной задачи. Его идея состоит в работе со списками конфликтующих заявок. Каждой заявке приписан такой список, который на первой стадии алгоритма наполняется, а на второй сокращается до нуля. Обнуление всех списков свидетельствует о получении решения с максимальным числом не конфликтующих между собой заявок. Приводится оценка времени работы алгоритма, показывающая, что по этому показателю он не уступает известным сегодня алгоритмам. В то же время он отличается от них тем, что не требует предварительной сортировки заявок и в случае неединственности оптимального решения дает более плотное расписание (с меньшей суммой простоев).

Full Text

Важнейшей особенностью современных задач принятия решений является стремление к поиску наилучших решений. В свою очередь задачи оптимизации могут решаться разными методами и алгоритмами, отличающимися эффективностью и точностью. Возможность выбора позволяет исследователю подобрать наиболее подходящий для конкретной задачи алгоритм. В настоящей статье предлагается новый алгоритм для известной задачи, которую называют задачей о выборе процессов или задачей о выборе заявок. Эта задача формулируется следующим образом. Имеется конечное множество процессов, операций, работ или заявок Z = {z1, z2,…,zn}, претендующих на один и тот же неделимый ресурс. Для каждого процесса zi известны начальный момент si и конечный момент fi, такие что 0 £ si < fi < ¥. Если временные интервалы двух или более процессов пересекаются, то они являются конкурирующими или несовместимыми. Задача заключается в выборе такого подмножества Z* Í Z взаимно совместимых процессов, которое имеет максимальный размер. Очевидно, что элементами множества Z могут быть не только собственно процессы в компьютерах. Приведем несколько примеров, соответствующих рассматриваемой задаче. 1. В некотором городе проходит фестиваль кинофильмов или театральных постановок, который проводится одновременно в разных залах. Имея расписание всех мероприятий, некий журналист или критик стремится составить для себя такой непротиворечивый график, который позволит ему посмотреть как можно больше фильмов или спектаклей. 2. При составлении расписания учебных занятий в вузе часто возникает ситуация, когда на одну аудиторию претендуют n несовместимых по времени занятий, начало и окончание которых уже фиксированы. Диспетчер пытается найти вариант расписания, по которому в аудитории пройдет максимальное число занятий. 3. В пункте проката имеется дефицитный инструмент (спортинвентарь, станок и т.п.). Поступило n заявок на взятие этого инструмента в прокат с желаемыми сроками использования. Сходная проблема имеет место при сдаче квартиры (комнаты, дома) в популярной курортной зоне в летние месяцы, когда поступает много не совместимых по времени заявок. В таких случаях понятно желание хозяина пункта проката (квартиры) удовлетворить максимальное количество заявок. Можно привести и другие примеры проблемных ситуаций, приводящие к задаче выбора заявок. Для решения задачи выбора процессов разработан ряд эффективных алгоритмов, в том числе несколько вариантов жадных алгоритмов [1, 2]. Применение этих алгоритмов предполагает, что исходное множество заявок уже упорядочено по fi или si. Ниже приводится еще один алгоритм, не требующий предварительной сортировки. Построение алгоритма Предлагаемый алгоритм строится на основе следующих утверждений. Утверждение 1. Заявка zi Î Z, совместимая со всеми заявками из Z\zi, принадлежит оптимальному списку Z* Í Z. Утверждение 2. Заявка zi Î Z, имеющая наибольшее число несовместимых с ней заявок из Z\zi, не может принадлежать Z* Í Z. Заявкам в исходном множестве Z присвоены номера в естественном порядке, то есть какое-либо упорядочение Z не производится. Максимальный номер заявки равен числу заявок n в исходном множестве Z, то есть n = |Z|. В процессе работы алгоритма при сокращении текущего Z соответственно уменьшается и n. Каждой заявке припишем список (множество) Mi, содержащий номера заявок, не совместимых с zi. Первоначально все списки пустые. На первом этапе работы алгоритма эти списки последовательно пополняются, а на втором происходит их сокращение в соответствии с утверждением 2. Алгоритм: 1.Выполняется проверка на совместимость заявок и заполнение списков Mi. 1.1. n=|Z|, i=1 1.2. j= i+1 1.3. если fi £ sj, то переход на 1.5, иначе если fj £ si, то переход на 1.5 1.4. Mi= Mi È {j} Mj= Mj È {i} 1.5. если j < n, то j= j+1 и переход на 1.3, иначе если i < n–1, то i= i+1и переход на 1.2 2. Сокращается множество заявок до получения искомого решения. 2.1. m=max| Mi |, 2.2. если m>0, то N={номера заявок с | Mi|=m}, иначе Z* = Z, конец 2.3. k=arg max(fi – si), iÎN 2.4. Z=Z\zk, для "i такого, что kÎMi, Mi= Mi\k 2.5. n= n–1, переход на 2.1. Выполнение одного из неравенств в п.1.3 означает, что сравниваемые заявки zi и zj совместимы, а в противном случае номер j заносится в список Mi, а номер i в Mj. По мере выполнения действий 1.2–1.5 списки M пополняются строго возрастающими номерами заявок. Во второй части алгоритма из Z удаляется заявка с максимальным числом несовместимостей (вместе со своим списком Mk). Если таких заявок больше одной, то есть | N |>1, то удаляется заявка с максимальной продолжительностью (п. 2.3). Оценим время работы алгоритма как функцию мощности исходного множества Z. Решающее влияние n на время работы алгоритма проявляется в его первой части. Здесь алгоритм выполняет парные сравнения заявок, а их количество непосредственно зависит от n. Так как число сочетаний то оценкой времени работы приведенного выше алгоритма справедливо считать O(n2). Время работы известных алгоритмов решения задачи о заявках оценивается как O(n), но оно относится к случаю упорядоченного по одному из моментов (si или fi) множества Z [1]. Если же учесть, что сортировка слиянием оценивается временем O(n lg n), а по методу вставки – O(n2), становится очевидным, что предложенный алгоритм не уступает приведенным в [1, 2]. Тестирование алгоритма В программной реализации алгоритма множество заявок формируется с помощью датчика случайных чисел с интервалом [0, 100]. Для образования заявки генерируются 2 числа, и большее значение присваивается f, а меньшее s. Исследование работы алгоритма проведено для различных значений n, от 30 до 300. Прежде всего, нас интересовал характер зависимости времени работы алгоритма от n. С этой целью проведено 10 серий прогона алгоритма, в каждой серии генерировалось 15 множеств Z и замерялось время решения соответствующих задач. В качестве показателя работы алгоритма взята оценка среднего времени решения задачи Tср. Полученные результаты приведены в табл. 1. Чтобы исключить влияние характеристик компьютера, Tср дано в относительных единицах (за единицу принято среднее время при n = 30). Там же в относительных единицах представлены оценки среднеквадратичного отклонения sT. Таблица 1 Результаты тестирования алгоритма n306090120150180210240270300 (n/30)2149162536496481100 Tср13,3247,11714,71623,45732,61746,12060,28979,09395,775 sT0,1660,5090,6662,7801,9832,8712,2972,6574,3733,985 Из этой таблицы следует, что время работы алгоритма с ростом n увеличивается не быстрее чем (n/30)2. Время работы алгоритма определялось и при увеличении интервала датчика случайных чисел в два раза в том же диапазоне изменения n, при этом характер зависимости от n не претерпел существенных изменений. Также сравнивались решения, получаемые по нашему алгоритму (NA) и алгоритму Greedy_Activity_Selector (GAS) [1]. В процессе исследования была установлена существенная особенность алгоритма NA. В тех случаях, когда задача имеет более одного решения, расписание по предложенному алгоритму получается более плотным, чем по GAS, то есть в нем меньше простоев между соседними заявками. Для подтверждения этого свойства алгоритма NA приведем два примера. В табл. 2 представлено множество Z из 30 заявок, параметры которых выдал датчик случайных чисел. Таблица 2 Исходное множество заявок (пример 1) i123456789101112131415 si32259952853038729218768470297 fi52100100939374449295347891843946 Окончание табл. 2 i161718192021222324252627282930 si127142323922586142532536704933 fi419577985384657443646470998091 Решения для Z из примера 1, полученные по обоим алгоритмам, приведены в табл. 3. Сравнение показывает, что при одинаковом числе заявок в обоих расписаниях сумма простоев по алгоритму GAS составляет 41 единицу времени, а по алгоритму NA только 16. Таблица 3 Результаты работы алгоритмов для примера 1 Алгоритм GASNA isifiПростоиisifiПростои 101834 101834 24424382039535 255364102553640 117678121370846 12849161284910 992951992951 39910043991004 Данные для второго примера, сгенерированные также датчиком случайных чисел, представлены в табл. 4. Таблица 4 Исходное множество заявок (пример 2) i1234567891011121314151617181920 si505351148148243259599913777546189743574 fi66786132939557805598100936283667993994887 Окончание табл. 4 i2122232425262728293031323334353637383940 si979065354922347145971693760852583174737 fi98979149569856749499683652100928790486467 Применив сравниваемые алгоритмы к множеству заявок из табл. 4, получили расписания, представленные в табл. 5. Таблица 5 Результаты работы алгоритмов для примера 2 Алгоритм GASNA isifiПростоиisifiПростои 41432 41432 19354832435493 1554666150661 28717452871745 14778331477833 37839003783900 12919312290970 10959823097990 1199100111991000 Как следует из табл. 5, суммарный простой по расписанию GAS равен 21 единице времени, а по расписанию NA только 12, то есть почти в два раза меньше. Эти примеры показывают, что алгоритм NA одновременно с нахождением максимального числа совместимых заявок обеспечивает более эффективное использование времени на рассматриваемом интервале, чем применяемый сегодня алгоритм GAS. Эта особенность алгоритма может иметь решающее значение в некоторых приложениях. Так, при сдаче в аренду помещения или оборудования, если цена аренды за единицу времени постоянна, выбор заявок по алгоритму NA при охвате максимального числа клиентов даст больший доход владельцу помещения (оборудования). Задача о выборе заявок или процессов относится к классу комбинаторных задач. Для ее решения сегодня применяются жадные алгоритмы, которые могут работать только после предварительной сортировки заявок по начальным или конечным моментам [1, 2]. Эти алгоритмы работают по принципу «снизу вверх», последовательно наращивая результирующее множество до получения оптимального решения. Предложенный в настоящей работе алгоритм NA не требует сортировки заявок и работает по принципу «сверху вниз», последовательно сужая исходное множество заявок до достижения искомого. По времени решения задачи сравниваемые алгоритмы имеют близкие оценки, но алгоритм NA будет предпочтительнее, когда сортировка исходного множества заявок (процессов) нежелательна или невозможна. А в тех случаях, когда требуется не только набрать максимальное число совместимых заявок, но и при этом получить наибольшую плотность расписания, построенный алгоритм NA, как показывают результаты сравнения, оказывается явно предпочтительнее известных жадных алгоритмов.