«Нижегородский государственный университет им. Н.И. Лобачевского ЗАДАЧИ И МЕТОДЫ КОНЕЧНОМЕРНОЙ ОПТИМИЗАЦИИ Учебное пособие Часть 3. Д.И. Коган Динамическое программирование и дискретная многокритериальная оптимизация ...»

Общая задача однопроцессорного обслуживания множества заявок с критерием суммарного штрафа. Данная задача – обобщение однопроцессорной задачи мастера. Ее отличие от задачи мастера в том, что для каждой заявки i вместо числовой характеристики а(i) задается монотонно возрастающая (в нестрогом смысле) функция индивидуального штрафа i(t). Значение этой функции – величина штрафа по заявке i, если обслуживание этой заявки завершается в момент времени t. При реализации расписания величина штрафа Wi() по произвольной заявке i оказывается равной i(t*(,i)), где t*(,i) – момент завершения обслуживания заявки i при реализации расписания. Требуется найти расписание, минимизирующее величину суммарного по всем заявкам штрафа.

Сначала выделим частные случаи, в которых правила оптимального упорядочения заявок получаются применением перестановочного приема.

экспоненциальны:

константа считается положительной. Реализуя перестановочный прием, легко получаем алгоритм синтеза оптимального расписания: для каждой заявки i, i = 1, n, нужно вычислить показатель далее заявки следует упорядочить по убыванию значений (i). Полученная перестановка является оптимальным расписанием обслуживания имеющегося множества заявок.

Выделим случай, когда все функции индивидуального штрафа одинаковы: i(t) = Ф(t), i= 1, n ; здесь Ф(t) – произвольная монотонно возрастающая (в нестрогом смысле) функция. Перестановочный прием дает следующий алгоритм синтеза оптимального расписания: заявки следует упорядочить по возрастанию показателя (i) – требуемой продолжительности обслуживания; полученная перестановка является оптимальным расписанием.

Перестановочный прием срабатывает, когда знак разности между величинами суммарного штрафа для расписания 0 = (1, 2,..., n) и для расисанияq, получаемого из 0 переменой местами заявок q и q+1, зависит только от параметров переставляемых заявок. Теорема Кладова- Лившица [23] устанавливает, что перестановочный прием дает способ определения показателя, сортировка по которому приводит к оптимальному расписанию, только для трех случаев:

1) все функции индививидуального штрафа линейны:

2) все функции индививидуального штрафа экспоненциальны:

3) функции индивидуального одинаковы для всех заявок: i(t) = Ф(t), i= 1, n ;

здесь Ф(t) – произвольная монотонно возрастающая (в нестрогом смысле) функция.

Теорема Кладова – Лившица доказана в предположении, что функции индивидуального штрафа являются достаточно гладкими (существуют третьи производные).

Отметим, что в трех перечисленных случаях вычислительная сложность алгоритма построения оптимального расписания (число выполняемых алгоритмом элементарных операций) имеет порядок nlgn, это соответствует сложности процедуры сортировки.

Если исходные данные определяют задачу, не подпадающую под какой-либо из перечисленных в теореме Кладова – Лившица случаев, то целесообразным способом ее решения является метод динамического программирования.

Рассмотрим обозначаемую символом Z, задачу обслуживания множества заявок N ={1,2,…,n} в однопроцессорной системе, в которой единственное ограничение, налагаемое на функции индивидуального штрафа – их монотонное возрастание. Считаем, что для каждой заявки i, i= 1, n, известны: (i) – продолжительность обслуживания на процессоре и i(t) – монотонно возрастающая в нестрогом смысле функция индивидуального штрафа; требуется построить расписание обслуживания, обеспечивающее минимальное значение суммарного по всем заявкам штрафа. Пусть S – произвольное подмножество заявок, S {1,2,…,n}. Через Z(S) обозначим частную задачу, получаемую из Z в предположении, что обслуживанию подлежит только совокупность заявок S, а через К(S) - минимально возможный суммарный штраф в частной задаче Z(S). Для одноэлементного множества заявок, как очевидно, имеем:

Сейчас предположим, что все значения функции К(S) для р-элементных множеств S уже найдены, здесь р {1,2,…,n-1}. Пусть S* - произвольное (р+1)элементное множество заявок. Если считать, что в совокупности S* последней обслуживается заявка j, то величина индивидуального штрафа по этой заявке равна j( ( ) ), минимально возможный суммарный по всем заявкам данной совокупности штраф в имеющейся ситуации равен К(S* \ {j}) + j( здесь S* - произвольное подмножество заявок, состоящее не менее, чем из двух элементов. Если минимум правой части (2.10) достигается при j = q, то последней в подмножестве S* следует обслужить заявку q. Равенства (2.9) – (2.10) - рекуррентные соотношения динамического программирования, позволяющие решить задачу Z.

Подсчитывая на их основании значения функции К(S* ), вычисления выполняются в порядке роста числа элементов в множествах S*, мы в итоге находим величину К(N), т.е. оптимальное значение критерия в решаемой задаче (минимальную величину суммарного штрафа).

ПРИМЕР 2.2. Имеется процессор, обслуживанию которым подлежат заявки множества N = {1,2,3}. Известно, что (1) = 3; (2) = 2; (3) =4; 1(t) = 2t2; 2(t) = 3t ;

3(t) = t2+ t. Требуется построить расписание, минимизирующее величину суммарного штрафа.

По формуле (2.9) вычисляем:

К({1}) =1(3)= 18; К({2}) = 2(2)=6; К({3}) = 3(4)=20.

Далее, пользуясь формулой (2.10), находим последовательно:

К({1, 2})=min{К({2})+ 1(5), К({1})+ 2(5)}= min{6+ 50, 18+ 15}= 33;

К({1,3})=min{К({3})+ 1(5), К({1})+ 3(7)}= min{20+98, 18+ 56}= 74;

К({2, 3})=min{К({3})+ 2(6), К({1})+ 2(5)}= min{20+ 18, 6+ 42}= 38;

К({1, 2, 3})=min{ К({2,3})+ 1(9), К({1,3})+ 2(9), К({1, 2})+ 3(9)}= min{38 + в левых частях записанных конкретизаций равенства (2.10) подчеркнуты значения параметра j, обеспечивающие минимальные значения их правых частей. Оптимальное значение критерия в рассматриваемом примере равно 101.

Благодаря сделанным в процессе вычислений подчеркиваниям, легко определяем оптимальную последовательность обслуживания заявок. Действительно, в совокупности {1, 2, 3} последней надо обслужить заявку 2 (именно этот номер был подчеркнут при определении К({1, 2, 3})). Заявке 2, таким образом, предшествует пара заявок {1,3}. В совокупности {1,3} последней надо обслужить заявку 3 (номер 3 был подчеркнут при определении К({1, 3})). И, наконец, заявка 1 должна быть обслужена первой. Легко подсчитывается, что при реализации построенного расписания величина суммарного штрафа действительно равна 101.

Задача однопроцессорного обслуживания множества заявок с минимаксным критерием. Имеется множество заявок N ={1,2,…,n} и процессор П, на котором должна быть обслужена каждая заявка этого множества; процессор не может обслуживать несколько (более одной) заявок одновременно; переход от обслуживания одной заявки к обслуживанию следующей за ней заявки затрат времени не требует.

Обслуживание заявок начинается с момента времени t = 0. Для каждой заявки i известны: (i) – продолжительность обслуживания на процессоре; монотонно возрастающая (в нестрогом смысле) функция индивидуального штрафа i(t). Если обслуживание заявки i завершается в момент времени t, то i(t) – величина штрафа по этой заявке. При реализации расписания моменты завершения обслуживания заявок вычисляются по формулам (2.1) – (2.3), величина штрафа Wi() по произвольной заявке i оказывается равной i( t*(,i)), i= 1, n. Вводим критерий Проблема заключается в отыскании расписания, минимизирующего значение максимального из индивидуальных штрафов:

Очевидно, что обслуживание процессором заявок множества N завершается в момент времени Т = (1) +(2) +…+(n). Подсчитаем все значения i(Т), i= 1, n ; пусть k(Т) – минимальная из найденных величин. Покажем, что в таком случае имеется оптимальное для задачи (2.8) расписание, в котором заявка k обслуживается последней.

Предположим, что в некотором расписании заявка k обслуживается j- ой по очереди (j {1,2,…, n–1}), а последней обслуживается заявка р, причем k(Т) k(Т). Последовательными перестановками заявки k и каждой непосредственно следующей за ней по обслуживанию заявки от расписания переходим к расписанию ', в котором заявка k обслуживается предпоследней. По расписанию ' каждая из заявок множества N\{k,p} завершается обслуживанием раньше, чем по расписанию ; заявка р завершается обслуживанием в тот же момент времени Т. Заявка k по расписанию ' завершается обслуживанием в момент Т – (р), но k(Т– (р)) k(Т). Далее каждая дополненная указанным образом запись из списка В переносится в список D. В списке D отыскивается запись с минимальным значением четвертой координаты.

Найденная запись, пусть это (')* = < t*, S*, (S*), *, t*1, S*1, i1*>, – итог работы процедуры 2. Четвертая координата найденной записи – оптимальное значение критерия в задаче (2.15).

Процедура 3 заключается в построении расписания opt,, обеспечивающего полученное оптимальное значение критерия *. Указанное расписание состоит из начальной части 1 и заключительной части 2. При этом 2. =(S*), т.е. это третья компонента записи (' )*, найденной в итоге работы процедуры 2. В расписании 1 на последнем месте должна стоять заявка i1*. Согласно записи (')*, эта заявка начинается обслуживанием, когда система находится в состоянии (t*1, S*1). Отыскиваем в списке С запись с первой компонентой t*1, и второй компонентой S*1; указанному требованию удовлетворяет ровно одна запись списка С. Пусть эта запись своими четвертой, пятой и шестой компонентами имеет соответственно. t*2, S*2, i2*. Тогда в расписании 1 на предпоследнем месте должна стоять заявка i2*. Далее отыскиваем в списке С запись с первой компонентой t*2, и второй компонентой S*2; указанному требованию удовлетворяет ровно одна запись списка С. Пусть эта запись своими четвертой, пятой и шестой компонентами имеет соответственно. t*3, S*3, i3*. Тогда в расписании 1 заявке i2*. должна непосредственно предшествовать заявка i3*. Действуя идентичным образом дальше, реализуем полное построение искомого расписания. Отметим, что последняя найденная в списке С запись своими четвертой и пятой компонентами должна иметь и V(0)), что соответствует начальному состоянию системы.

Задача однопроцессорного обслуживания потока заявок с учетом времен переналадок. Данная задача отличается от канонической тем, что при переходе процессора, завершившего обслуживание заявки i, к обслуживанию заявки j необходимо выполнение соответствующей переналадки продолжительностью р(i,j).

Считается, что в момент времени 0 процессор находится в нейтральном (нулевом) состоянии и продолжительность его наладки для обслуживания заявки i равна р(0, i).

Все числа р(i,j), где i = 0, n и j = 1, n, предполагаются заданными в виде целочисленной матрицы времен переналадок Р = {рij} соответствующей размерности. Условно будем говорить, что процессор, завершивший обслуживание заявки i, находится в конфигурации i.

Расписание обслуживания отождествляем с перестановкой = (i1, i2,…, i n) элементов множества {1, 2,..., n}; заявка ik в расписании обслуживается k-ой по очереди. Обозначим через tнач(, ik) и t*(, ik) моменты начала и завершения обслуживания заявки i k при реализации расписания, k = 1, n. Считаем, что реализация расписания компактна, т.е. имеют место соотношения:

Суммарный штраф по всем заявкам потока R, обслуживаемым по расписанию, есть Проблема заключается в минимизации суммарного штрафа, т.е. в нахождении Состояние системы обслуживания определяем как тройку (t, i, S), где t – момент принятия очередного решения по загрузке процессора; в момент t процессор считается свободным и находящимся в конфигурации i; S – множество заявок, которые по состоянию на момент времени t прибыли и ожидают обслуживания.

Пусть (t, i, S) обозначает минимальную величину суммарного штрафа по заявкам множества S и заявкам, поступающим в систему обслуживания позднее момента времени t, для системы, находящейся в состоянии (t, i, S). Как очевидно, (0,0, V(0)) – оптимальное значение критерия в решаемой задаче (2.19).

Как и ранее, через D(t, µ) обозначаем совокупность заявок, прибывающих в систему обслуживания на временном отрезке [t + 1, t + µ].

Существенно, что в состоянии (t, i, S) в качестве очередной обслуживаемой может быть выбрана заявка не обязательно из числа имеющихся в совокупности S (как это было ранее); она может быть взята из совокупности поступающих во время реализации соответствующей переналадки (при этом для времени переналадки берется верхняя оценка max р(i,j)). Для учета новой возможности введем в рассмотрение множество S, состоящее из заявок, поступающих во временном промежутке [t+1, t + + max р(i,j)]. Выбор очередной обслуживаемой заявки в ситуации, описываемой тройкой ( t, i, S), будем осуществлять в совокупности S* = S S.

Кроме того, в множество S* включаем нулевую (фиктивную) заявку. При этом считаем, что принятие на обслуживание фиктивной заявки не предусматривает предварительной переналадки процессора и означает его простой в течение одного такта.

Если в момент принятия решения t в совокупности S* выбрана заявка j, то ее обслуживание начнется в момент max{t + р(i,j), t(j)} и завершится в момент Т(t,i,j) = max{t + р(i,j), t(j)} + (j).

В принятых обозначениях основное рекуррентное соотношение динамического программирования для рассматриваемой задачи записывается в виде Задача однопроцессорного обслуживания потока заявок с нелинейными функциями индивидуальных штрафов. Минимизируемым в данной задаче критерием считаем суммарный штраф по всем заявкам. Вместо показателя а(i), как это имело место в канонической модели, здесь каждой заявке i приписывается, вообще говоря, нелинейная функция индивидуального штрафа i(t). Если обслуживание заявки i завершается в момент времени t*, то величина выплачиваемого по данной заявке штрафа равна i(t*), i =1, n. Все функции i(t) считаются монотонно возрастающими в нестрогом смысле. Полагаем, что эти функции заданы программно, вычисление значения каждой из них в произвольной точке t требует выполнения не более чем k элементарных операций, где k – фиксированная константа. Как и ранее, состояния системы обслуживания – пары (t, S), где t – МПР, а S – множество заявок, которые по состоянию на момент времени t прибыли и ожидают обслуживания; фиктивная заявка в совокупности S присутствует. Пусть нл(t, S) обозначает минимальную величину суммарного штрафа по заявкам множества S и заявкам, поступающим в систему позднее момента t, для системы, находящейся в состоянии (t, S). Тогда общее рекуррентное соотношение динамического программирования для решения рассматриваемой задачи записывается в виде нл(t,S) = min { i(t+ (i))+ нл( t + (i),(S \ i) D(t,(i))}. (2.21) Задача однопроцессорного обслуживания потока заявок с нелинейными функциями индивидуальных штрафов и директивными сроками. Здесь в дополнение к исходным данным предшествующей задачи для каждой заявки i считается указанным обозначаемый через d(i) директивный срок завершения обслуживания, i = 1, n.

Расписание именуем допустимым, если для всех i = 1, n имеет место t*(, i) d(i).

Проблема заключается в отыскании допустимого расписания, минимизирующего величину суммарного штрафа.

минимизируемого критерия (возможными считаются только допустимые расписания).

необходимость соблюдения директивных сроков, но введем новые функции индивидуального штрафа: величину штрафа i(t) по заявке i определим следующим образом: i(t) = i(t), если t d(i), и i(t) = i(t) + L в противном случае.

Полученная задача является задачей синтеза расписания, минимизирующего суммарный штраф; при этом функции индивидуального штрафа нелинейны, но директивные сроки отсутствуют. Соответствующий алгоритм решения изложен выше.

Если минимальное значение суммарного штрафа в полученной задаче оказывается меньшим L, то обеспечивающее его расписание является одновременно оптимальным решением исходной задачи (с учетом директивных сроков).

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

2.3. Задачи синтеза расписаний обслуживания для систем с параллельными и последовательными процессорами.

Сначала рассмотрим задачу, возникающую в системах с параллельными процессорами.

Задача синтеза оптимального расписания для системы с параллельными процессорами. Каждую заявку входного потока R = {1, 2,..., n} следует обслужить одним из m идентичных процессоров j ( j = 1, m ). Полагаем, что процессор j готов к обслуживанию заявок потока R начиная от целочисленного момента времени Tj (0 = T T2... Tm). Одновременное обслуживание каждым процессором более одной заявки, а также неоправданные простои процессоров запрещены; обслуживание каждой заявки осуществляется без прерываний, в момент завершения обслуживания очередной заявки каждый процессор считается готовым к обслуживанию следующей.

Каждая заявка i входного потока характеризуется тремя целочисленными параметрами:

t(i) момент поступления в систему обслуживания (0 = t(1) t(2) … t(n - 1) t(n));

(i) требуемая продолжительность обслуживания любым из процессоров ((i)> 0);

a(i) штраф за единицу времени (такт) пребывания в системе обслуживания.

Если обслуживание заявки i завершается в момент времени t*(i), то а(i) (t*(i) t(i)) индивидуальный штраф по данной заявке.

Расписание обслуживания представляет собой кортеж, где j = ( i j1, i j2,..., i jv ( j ) ) – последовательность обслуживания заявок процессором j: первой на данном процессоре обслуживается заявка i j1, второй – заявка i j 2,…, последней – заявка i jv ( j ) ( j = 1, m ). Каждая заявка потока R входит только в одну из составляющих кортеж последовательностей. Таким образом, v(1) + v(2) + …. + v(m) = n. По смыслу задачи параметры расписания v(j), j = 1, m, неотрицательны, а равенство v(j’) = означает, что по расписанию процессор j’ не принимает участия в обслуживании заявок потока R.

Обозначим через tнач(, i jr ) и t*(, i jr ) соответственно моменты начала и завершения обслуживания заявки i jr при реализации расписания ( r = 1, ( j ), j = 1, m ).

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

При обслуживании потока R управленческие решения принимаются для тех моментов времени, когда по меньшей мере один процессор свободен. Каждое решение состоит в выборе заявки, которая немедленно поступает на обслуживание свободным процессором. Если таких процессоров несколько, полагаем, что для обслуживания выбранной заявки назначается свободный процессор с минимальным номером; такой процессор будем называть первым свободным процессором. Текущее состояние в момент принятия решения t определяется как набор F = (t, S, 1, 2,…, m), где S – множество заявок, которые прибыли и ожидают обслуживания, а j – число тактов дискретного времени, оставшихся до освобождения процессора j, j = 1, m. Так как t – МПР, по меньшей мере одно из чисел j равно нулю. Выбор очередной обслуживаемой заявки осуществляется из совокупности S.

Через D(t, µ) обозначаем множество заявок, прибывающих в систему обслуживания на временном отрезке [t + 1, t + µ], здесь µ – целое неотрицательное число; отметим, что D(t,1) – совокупность заявок, прибывающих на обслуживание в момент времени t+1; дополнительно полагаем, что D(t,0) =. Для любого состояния F = (t, S, 1, 2,…, m), множество S считаем непустым, что обеспечивается обязательным включением в него нулевой (фиктивной) заявки 0 с параметрами а(0) = 0, t(0) = t и (0) = min { D(t, t +) }. Взятие на обслуживание фиктивной заявки означает простой процессора от момента t до ближайшего момента поступления в систему какой-либо новой заявки потока R. Если поступившая фиктивная заявка не принимается на немедленное обслуживание, то она выпадает из дальнейшего рассмотрения. Как и в случае однопроцессорной системы, иногда принятие на обслуживание фиктивной заявки целесообразно и при наличии в S заявок, не являющихся фиктивными.

Пусть W(t, S, 1, 2,…, m) обозначает минимальную величину суммарного штрафа по заявкам множества S и заявкам, которые поступят в систему обслуживания позднее момента времени t при условии, что (t, S, 1, 2,…, m) – текущее состояние системы.

Предположим, что в состоянии F = (t, S, 1, 2,…, m) из совокупности S выбрана и направлена на немедленное обслуживание первым свободным процессором j заявка i. Тогда следующим моментом принятия решения является t +, где = min (1, 2,…, j-1, (i), j+1, …, m). Отметим, что если в рассматриваемом состоянии F свободны несколько процессоров, то = 0 и следующее решение по загрузке принимается в тот же момент времени t. По состоянию на момент t + совокупность ожидающих обслуживания заявок состоит из двух подмножеств, S \ {i} и D(t, ). Таким образом, состояние системы в следующий момент принятия решения характеризуется как набор (t +, (S \ {i}) D(t, ), 1-, 2-,…, j-1-, (i)-, j+1-, …, m- ). В принятых обозначениях рекуррентное соотношение динамического программирования записывается в виде:

W(t, S, 1, 2,…,m) = min {a(i) [t +(i) t(i)] + W(t+, (S \ i) D(t, ), 1-,2i S,…, здесь j – минимальное значение индекса, при котором компонента j в кортеже (1, 2,…, j,…, m) равна нулю.

Если в соотношении (2.26) минимум реализуется при i = i`, то в момент времени t на первый свободный процессор следует направить заявку i` из совокупности S. Направление на обслуживание нулевой заявки означает простой процессора по меньшей мере до следующего момента пополнения множества S прибывающими заявками. Если в момент принятия решения t на первый свободный процессор направляется нулевая заявка, то одновременно такие же нулевые заявки направляются на остальные свободные процессоры.

В силу значительной вычислительной сложности изложенной процедуры для рассматриваемой задачи актуальна разработка реализуемых в приемлемом времени эвристических алгоритмов. Один из таких алгоритмов предложен далее, в главе 3.

Перейдем к рассмотрению задач обслуживания потока поступающих в дискретном времени заявок R = {1, 2,..., n} в системе, состоящей из двух последовательных процессоров j, j = 1,2.

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

Полагаем, что первый процессор готов к обслуживанию заявок потока начиная от момента времени 0, а второй процессор от момента времени Т0. Одновременное обслуживание каждым процессором более одной заявки, а также неоправданные простои процессоров запрещены; обслуживание каждой заявки осуществляется без прерываний, в момент завершения обслуживания очередной заявки каждый процессор считается готовым к обслуживанию следующей. Каждая заявка i потока R характеризуется целочисленными параметрами:

t(i) момент поступления в систему обслуживания (0 = t(1) t(2) … t(n - 1) t(n));

1(i) требуемая продолжительность обслуживания первым процессором (1(i)> 0);

2(i) требуемая продолжительность обслуживания вторым процессором (2(i)> 0);

a(i) штраф за единицу времени (такт) пребывания в системе обслуживания.

Момент полного завершения обслуживания заявки это момент завершения ее обслуживания вторым процессором.

Расписание обслуживания представляет собой кортеж, где 1 ={i1, i2, …, in} и 2 ={j1, j2, …, jn}– последовательности индексов заявок, определяющие порядок их обслуживания на первом и втором процессорах соответственно. Пусть t1нач(, ik) и t1*(, ik) обозначают моменты начала и завершения обслуживания заявки ik на первом процессоре при реализации расписания ; аналогично t2нач(, jk) и t2*(, jk) моменты начала и завершения обслуживания вторым процессором заявки jk при реализации того же расписания, k = 1, n.

Считаем, что реализация расписания компактна, т.е. имеют место соотношения Величина суммарного штрафа по всем заявкам при реализации расписания вычисляется по формуле образом:

Отметим, что в некоторых производственно-транспортных системах возникает специфическая и более простая задача, когда между первым и вторым процессором заявки переставлять нельзя, т.е. последовательности обслуживания заявок на первом и втором процессорах должны совпадать. Данное ограничение является существенным;

его наложение, вообще говоря, вызывает рост оптимального значения рассматриваемого минимизируемого критерия. Приведем пример. Пусть R = {1, 2}, в начальный момент времени 0 свободны оба процессора, характеристики заявок следующие: t(1) = 0, t(2) = 10; 1 (1) = 10, 2 (1) = 10, 1 (2) = 1, 2 (2) = 1; a(1) = 1, a(2) = 10. Легко проверяется, что единственным оптимальным в общей постановке задачи (2.27) является расписание, где 1 ={1, 2}, а 2 ={2, 1}.

Рассмотрим вопрос о решении задачи (2.27) в общей постановке методом динамического программирования. В связи с целочисленностью всех определяющих задачу параметров время считается дискретным.

При обслуживании потока R управленческие решения принимаются для тех моментов времени, когда по меньшей мере один процессор свободен. Каждое решение состоит в выборе заявки, которая немедленно поступает на обслуживание свободным процессором. Если свободны оба процессора, то определяется пара заявок, первая из которых поступает на обслуживание первым, а вторая вторым процессором.

Состояние системы определяем как набор F = (t, S1, S2, d, T, ). Здесь t МПР (в момент времени t по меньшей мере один процессор свободен); S1 совокупность заявок, которые к рассматриваемому МПР поступили и ожидают обслуживания первым процессором; S2 совокупность заявок, которые к рассматриваемому МПР прошли обслуживание первым процессором и ожидают обслуживания вторым процессором; d номер процессора, который в момент времени t свободен (d равно 1 или 2); Т число тактов дискретного времени, оставшегося до освобождения занятого процессора; если Т = 0, то по состоянию на момент времени t свободны оба процессора; номер заявки, которая в данный момент времени обслуживается первым процессором (в случае, когда d = 1, т.е. первый процессор свободен, полагаем = 0).

Через W(t, S1, S2, d, T, ) обозначим минимальную величину суммарного штрафа по заявкам множеств S1, S2 и заявкам, которые поступят в систему обслуживания позднее момента времени t, для системы, находящейся в состоянии (t, S1, S2, d, T, ), здесь t момент принятия решения.

Как и ранее, V(t) обозначает совокупность заявок, поступающих на обслуживание в произвольный момент времени t. Таким образом, шестерка (0, V(0),, 1, Т0, 0) это начальное состояние системы, а W(0, V(0),, 1, Т0, 0) искомое оптимальное значение критерия в рассматриваемой задаче (минимально возможное значение суммарного по всем заявкам штрафа). Запишем рекуррентные соотношения, позволяющие организовать процесс последовательного вычисления значений функции W (t, S1, S2, d, T, ) вплоть до отыскания величины W(0, V(0),, 1, Т0, 0).

Вначале отметим, что при t>t(n) значения W (t,, S2, 1, 0, 0) вычисляются без затруднений, ибо в таком случае шестерка (t,, S2, 1, 0, 0) определяет относящуюся ко второму процессору задачу мастера, оптимальное расписание в которой строится крайне просто (см. п.1 данной главы).

Далее при записи рекуррентных соотношений, необходимых для вычисления значений функции W(t, S1, S2, d, T, ) на других наборах значений ее аргументов, нам будет удобно использовать функции f(,T), (,T) и (,), в которых и принимают значения на множестве номеров заявок, а Т на множестве целых неотрицательных чисел, не превышающих максимальной из заданных для заявок продолжительностей обслуживания первым и вторым процессором. Функция f(,T) принимает значение 1, если T-1() 0, и значение 0 в противном случае. Функция (,T) принимает значение 1, если T-2() > 0, и значение 0 в противном случае.

Функция (,) принимает значение 1, если 1()2(), и значение 0 в противном случае. Считаем, что в совокупность S1 всегда входит нулевая (фиктивная) заявка с продолжительностью обслуживания на первом процессоре 1, а на втором 0; в совокупность S2 всегда входит нулевая (фиктивная) заявка с продолжительностью обслуживания на первом процессоре 0, а на втором 1; штраф по фиктивной заявке всегда нулевой. Кроме того, дополнительно положим, что для отрицательных значений аргумента Т значение функции W (t, S1, S2, d, T, ) равно нулю.

W(t, S1, S2, 1, T, 0) = min [f(,T) W(t+1(), (S1 \ {})) D(t, 1()), S2{}, 1, T-1(), 0) + (1- f (, T)) W(t+Т, (S1 \ {})) D(t, Т), S2, 2, 1() - T, ) ];

W(t, S1, S2, 2, T, ) = min {[a() [t +2() - t()] + (,T) W(t+2(),(S1 D(t, 2()), S2\{}, 2, T-2(),)+ + (1- (, T)) W(t + Т, (S1 D(t, T), S2{}, 1, 2() - T, 0)]};

W(t, S1, S2, 1, 0, 0) = D(t, 1()), (S2\{}){}, 1, 2()-1(),,0)+(1-(,)) W(t+2(), (S1\{}) D(t, 2()),, (S2\ {}), 2, 1()- 2(),)}.

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

Построим соответствующие рекуррентные соотношения динамического программирования.

В частной задаче момент времени t называем моментом принятия решения (МПР), если в данный момент свободен первый процессор. Состояние системы это тройка объектов (t, S, T), где t МПР; S совокупность прибывших и по ситуации на момент времени t ожидающих обслуживания на первом процессоре заявок; Т время, оставшееся (в ситуации на момент t) до освобождения второго процессора от работ по обслуживанию тех заявок, которые уже прошли первый процессор.

Пусть W'(t, S, T) минимальный суммарный штраф по заявкам множества S и заявкам, которые прибудут на обслуживание позднее момента t, для системы, находящейся в состоянии (t, S, T).

Ясно, что начатая в момент времени t обслуживанием на первом процессоре заявка i из совокупности S на втором процессоре будет начата обслуживанием в момент t+ max(1(i), T); поэтому величина индивидуального штрафа по этой заявке окажется равной a(i) (t+max(1(i), T)+ 2(i) t(i)). Cледующим МПР будет t*= t + 1(i); по состоянию на МПР t* до освобождения второго процессора останется max(1(i), T)+ 2(i) 1(i) единиц времени. Отсюда получаем следующее рекуррентное соотношение:

+ W'(t+ 1(i), (S \ {i}) D(t, 1(i)), max(1(i), T)+ 2(i) 1(i))} Итоговым результатом вычислений по этому соотношению является величина W'(0, V(0), T0) оптимальное значение критерия в рассматриваемой частной задаче.

2.4. Задачи оптимального обслуживания стационарных объектов, расположенных в одномерной зоне.

Рассматриваются две близкие по описанию модели обслуживания одним или двумя мобильными процессорами стационарно расположенных объектов. В рамках этих моделей формулируются и решаются задачи синтеза оптимальных расписаний (последовательностей обслуживания).

Модель I следующая. Имеется n-элементное множество М = {о1, о2,…,оn} стационарных объектов, расположенных в рабочей зоне мобильного (перемещаемого) процессора P. Зона представляет собой направленный отрезок L, в фиксированных точках которого расположены объекты о1, о2,…, оn. Начальная точка отрезка L является базовой для процессора; от этой точки он сначала перемещается к конечной точке отрезка (прямой рейс, примем для него обозначение +), а затем, достигнув ее, возвращается к базовой точке (обратный рейс, примем для него обозначение –). При реализации цикла +– процессор должен выполнить обслуживание каждого объекта множества М; обслуживание части объектов реализуется в прямом рейсе, обслуживание всех остальных объектов в обратном рейсе. Осуществляемое процессором обслуживание каждого объекта однократное, без прерываний. Остановки процессора при выполнении цикла +– связаны только с обслуживанием объектов множества М. Затраты времени на перемещения процессора и на обслуживание каждого объекта, а также штрафы за задержки в обслуживании характеризуются известными параметрами и функциональными зависимостями.

Отличие модели II от модели I заключается в том, что обслуживание объектов множества М осуществляется не одним, а двумя идентичными процессорами Р1 и Р при реализации движений только в прямом направлении; движение процессора Р2 от базовой точки начинается позже, чем движение процессора Р1. Удобно считать, что обслуживание объектов процессором Р1 реализуется в рейсе, именуемом +, а обслуживание объектов процессором Р2 реализуется в рейсе, именуемом -.

Примем следующие обозначения:

1 и n – начальная и конечная точки отрезка L соответственно;

l1, l2, …, ln (1 < l1 < l2 A1n величины В*(i, D) заведомо не имеют смысла.

Как очевидно, В*(1, 0) – величина индивидуального штрафа по первому объекту в случае, когда его обслуживание реализуется в рейсе -, т.е. завершается в момент времени 0,1 + М(1). В то же время В*(1, 1) – величина индивидуального штрафа по первому объекту, если его обслуживание выполняется в рейсе +, т.е.

завершается в момент 0,1 + 1. Поэтому При D{0, 1} величины В*(1, D) смысла не имеют. Дополнительно удобно положить Предположим, что все значения В*(i, D) для некоторого i{1, 2,…, n - 2} уже найдены. При определении значений В*(i + 1, D), надо учитывать две возможности:

1). Объект oi+1 обслуживается в рейсе +. Тогда рассматриваемой паре (i + 1, D) непосредственно предшествует ситуация (i, D - i+1).

рассматриваемой паре непосредственно предшествует ситуация(i, D).

С учетом этих возможностей получаем:

В*(i + 1, D) = min{В*(i, D - i+1) + i+1(0,1 + 1,2 + … + i,i+1 + D), здесь i{1, 2,…, n - 2}.

Вычисляемое по формуле (2.35) значение В*(i + 1, D) оказывается равным + в том и только том случае, когда определяемая парой (i + 1, D) ситуация возникнуть не может.

При определении значений В*(n, D) следует иметь в виду, что по принятому соглашению объект on обслуживается при завершении движения +,, т.е. nV. Поэтому каждой рассматриваемой паре (n, D) непосредственно предшествует только ситуация (n - 1, D - n). Следовательно, Каждая вычисляемая величина В*(n, D) – это минимально возможный суммарный штраф по всем объектам множества М, если в рейсе + на обслуживание объектов этого множества затрачивается время D.

Оптимальное значение критерия Кopt рассматриваемой задачи I-1 определяется по формуле Равенства (2.32) – (2.37) суть рекуррентные соотношения динамического программирования для решения задачи (I-1).

В соответствующей вычислительной процедуре сначала по формулам (2.32) определяются значения В*(1, 0) и В*(1, 1). В соответствии с формулой (2.34) для D{0, 1} величины В*(1, D) полагаются равными +. Далее, на основании формулы (2.35) сначала определяются все значения В*(2, D), затем все значения В*(3, D) и т.д.

Последними по данной формуле для всех возможных значений D определяются величины В*(n - 1, D). Используя формулу (2.36), по известным величинам В*(n - 1, D) определяем значения В*(n, D). Оптимальное значение критерия решаемой задачи находится по формуле (2.37).

Процесс вычислений по соотношениям (2.32) – (2.37) удобно представлять как последовательное заполнение клеток таблицы значений функции В*(i, D). Строки этой таблицы соответствуют возможным значениям параметра i, i{1, 2,…, n}, а столбцы – возможным значениям параметра D, D{0,1, 2,…, A1n }. В каждую клетку (i, D) вносится величина В*(i, D).Таблица заполняется по строкам, в порядке роста их номеров. Заметим, что в процессе счета найденное значение В*(i, D) оказывается бесконечным в том и только том случае, когда при определяемом строкой значении параметра i фиксируемое столбцом значение параметра D невозможно.

Зафиксировав для каждого найденного в процессе вычислений по формуле (2.35) значения В*(i + 1, D) номер компоненты, на которой реализуется минимум правой части этой формулы, и определив затем значение параметра D, на котором достигается минимум правой части (2.37), легко строим искомую оптимальную стратегию.

Будем считать, что функции индивидуального штрафа либо заданы таблично, либо значение каждой из них в любой точке вычисляется путем выполнения ограниченного, не превышающего некоторой константы C, числа элементарных операций. В таком случае общее число выполняемых изложенным алгоритмом элементарных операций имеет верхней оценкой величину, прямо пропорциональную числу клеток в заполняемой таблице, т.е. произведению n ( A1n +1).

ПРИМЕР 2.5. Требуется определить оптимальную стратегию обслуживания пяти стационарных объектов при условиях: 01= 2, 12= 1, 23= 3, 34= 2,45= 1, 54= 2, 43= 2, 32= 2, 21= 1, 10= 3 (значение 10 для синтеза оптимальной стратегии фактической роли не играет); 1 = 1; 2 = 1; 3 = 2; 4 = 3; 5 = 2;

Легко вычисляются необходимые для применения рекуррентных соотношений величины М(j):

Далее подсчитываем значения функции В*(i, D). По условиям решаемой задачи параметр i принимает значения 1, 2, 3, 4, 5; целочисленный параметр D принимает значения из отрезка [0, 9]. Результаты вычислений удобно фиксировать в таблице 2. значений функции В*(i, D), параметру i соответствуют строки таблицы, параметру D – ее столбцы. Символы бесконечности в таблицу не вносим.

По формулам (2.32) и (2.33) получаем: В*(1,0) = 1(25) =20; В*(1,1) = 1(3) =0.

Далее по формуле (2.35) имеем:

В*(2,1) = min{ В*(1,0) + 2 (4); В*(1,1) + 2 (24)} = min{ 20 + 0; 0 + 18} = (минимум правой части рекуррентного соотношения достигается на второй компоненте, что отмечается цифрой в скобках после записи числа 18 в клетку (2,1) таблицы 2.2);

В*(3,0) = В*(2,0) + 3(20) = 36; В*(3,1) = В*(2,1) + 3(21) = 22;

В*(3,2) = min{ В*(2,0) + 3(8); В*(2,2) + 3(22)} = min{ 36 + 0; 0 + 8} = (минимум правой части рекуррентного соотношения достигается на второй компоненте);

В*(3,3) = В*(2,1) + 3(9) = 18; В*(3,4) = В*(2,2) + 3(10) =0.

В*(4,0) = 52; В*(4,1) = 39; В*(4,2) = 26; В*(4,3) = min{ 36 + 11; 18 + 19} = (минимум правой части рекуррентного соотношения достигается на второй компоненте);

(минимум правой части рекуррентного соотношения достигается на второй компоненте);

В*(4,5) = 21; В*(4,6) = 32; В*(4,7) = 33.

Далее по формуле (2.36) находим:

В*(5, 2) = В*(4, 0) + 5(11) = 74; В*(5, 3) = В*(4, 1) + 5(12) = 63; В*(5, 4) = В*(4, 2) + 5(13) = 52; В*(5, 5) = В*(4, 3) + 5(14) = 65; В*(5, 6) = В*(4, 4) + 5(15) = 50; В*(5, 7) = В*(4, 5) + 5(16) = 53; В*(5, 8) = В*(4, 6) + 5(17) = 66; В*(5, 9) = В*(4, 7) + 5(18) = 67.

Согласно (2.37), оптимальное значение критерия рассматриваемой задачи – это минимальное из вычисленных значений В*(5, D). Оно равно 50, соответствующее значение параметра D равно 6. Таким образом, оптимальная стратегия предусматривает, что на непосредственное обслуживание объектов в прямом рейсе должно затрачиваться 6 единиц времени. При этом на обслуживание объекта о5 уходит время 5 = 2, на непосредственное в прямом рейсе обслуживание первых четырех объектов остается 4 единицы времени. При вычислении В*(4,4) минимум правой части реализуется на второй компоненте правой части рекуррентного соотношения; значит объект о4 в прямом рейсе обслуживать не следует, все четыре единицы времени должны быть затрачены на обслуживание в этом рейсе объектов из числа первых трех.

Таблица 2.3. Значения функции В*(i, D).

Ситуация, непосредственно предшествующая той, что описывается парой аргументов (3,4) функции В* единственна – это (2, 2); таким образом, объект о3 должен быть обслужен в прямом рейсе. На непосредственное обслуживание в этом рейсе первых двух объектов остается две единицы времени. Ситуация, непосредственно предшествующая той, что описывается парой аргументов (2, 2) функции В* единственна – это (1, 1), объект о2 должен быть обслужен в прямом рейсе. Оставшаяся единица времени уходит на обслуживание в прямом рейсе объекта о1. Таким образом, оптимальная стратегия в рассмотренном примере Vopt ={1, 2, 3, 5}; объекты оj, где j Vopt, в реализации данной стратегии должны обслуживаться при выполнении прямого рейса, оставшийся объект о4 – при выполнении обратного рейса.

Отметим, что в случае, когда все функции индивидуального штрафа линейны (i(t)= аi t+bi, i = 1, n ), имеется возможность применения перестановочного приема, и характеристик Qj, j {1, 2, …, n-1}, вычислима путем выполнения линейно зависящего от n числа операций. Для любой стратегии V и любого элемента j V переход от обслуживания объекта оj, в прямом рейсе к его обслуживанию в обратном рейсе влечет увеличение индивидуального штрафа по этому объекту на аjМ(j) и уменьшение суммарного штрафа по всем остальным объектам на Qjj. Очевидно, что при реализации оптимальной стратегии объект оj должен обслуживаться в обратном рейсе, если аjМ(j) < Qjj; объект оj должен обслуживаться в прямом рейсе, если аjМ(j) > Qjj; в случае аjМ(j) = Qjj объект оj может быть обслужен в любом из рейсов. Изложенное правило обеспечивает возможность синтеза оптимальной в задаче I-1 с линейными функциями индивидуального штрафа стратегии за время, линейно зависящее от числа подлежащих обслуживанию объектов.

Задача I-2, алгоритм решения. При решении данной задачи используется следующий факт.

Утверждение 4.1. Пусть V – любая стратегия в модели обслуживания I, удовлетворяющая условию k V, и пусть V* = V{k}, здесь k{1, 2, …, n–1}. Тогда t*k(V) > t*k(V*), t*j (V) = t*j (V*) для j t*j(V) для j> k, здесь j{1, 2, …, n–1}.

Доказательство данного утверждения очевидно.

Стратегию, при реализации которой значение максимального из индивидуальных штрафов не превышает константы F, будем именовать F-стратегией.

Для заданной константы F поставим вопрос, существует ли в рассматриваемой задаче I-2 какая-либо F-стратегия. Ответ дает следующий, основанный на утверждении 4.1 и обозначаемый через А(F), алгоритм:

1. Полагаем V = {n}; проверяем, обеспечивает ли стратегия V индивидуальный штраф по объекту оn не больший, чем F; если это так, переходим к п.2; в противном случае в рассматриваемой задаче Fстратегии отсутствуют, ответ на поставленный вопрос отрицательный, 4. Проверяем, обеспечивает ли стратегия V* по объектам оn и оk индивидуальные штрафы, не большие F; если это так, переходим к п.6;

5. Проверяем, обеспечивает ли стратегия V** по объектам оn и оk индивидуальные штрафы не большие F; если это не так, в рассматриваемой задаче F-стратегии отсутствуют, ответ на поставленный вопрос отрицательный, алгоритм работу заканчивает; в случае положительного ответа полагаем V = V** и переходим к п.6;

6. Если k = n – 1, полученное множество V является F-стратегией; ответ на поставленный вопрос положительный, алгоритм работу заканчивает;

в противном случае следует увеличить имеющееся значение k на 1 и Благодаря описанному алгоритму, экстремальная задача I-2 решается методом деления пополам. Процесс решения начинается с назначения левой границы S1 и правой границы W1 диапазона, в котором локализовано искомое оптимальное значение критерия.

Далее выполняется процедура, состоящая не более чем из log2(W1 – S1)+ однотипных этапов. На произвольном k-ом этапе имеющийся отрезок [Sk, Wk], в котором локализовано оптимальное значение критерия, делится пополам; координату середины отрезка обозначаем через Fk. Затем к решаемой задаче применяется алгоритм А(Fk); если получаемый в результате ответ положителен, оптимальное значение критерия локализовано в левом полуотрезке; в противном случае это значение находится в правом полуотрезке. Поэтому в случае положительного ответа полагаем Sk+1 = Sk и Wk+1 = Fk ; в случае отрицательного ответа устанавливаем Sk+1 = Fk + 1 и Wk+1 = Wk. Далее переходим к выполнению следующего этапа. Процесс заканчивается в ситуации, когда в полученном отрезке локализации имеется только одна целочисленная точка.

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

Тогда алгоритм А(F) имеет линейно зависящую от n оценку количества выполняемых элементарных операций и вычислительная сложность изложенной процедуры решения задачи I-2 имеет оценку Сnlog2(W1 – S1), где С – не зависящая от параметров решаемой задачи константа.

Задача II-1, алгоритм решения. Для решения задачи II-1 применим метод динамического программирования. Пусть В'(i, D) – минимально возможная величина суммарного штрафа по объектам совокупности {о1, о2, …, оi} при условии, что в рейсе + общее время, затрачиваемое на обслуживание объектов из этой совокупности равно D. Отметим, что так же, как при рассмотрении задачи I-1, возможные значения параметра D целочисленны и лежат в числовом диапазоне [0, A1n ].

По определению В'(1, 0) – это величина индивидуального штрафа по объекту о в случае, когда его обслуживание реализуется в рейсе -, т.е. завершается в момент времени 0,1 + 1 + Т. В то же время В'(1, 1) – величина индивидуального штрафа по объекту о1, если его обслуживание выполняется в рейсе +, т.е. завершается в момент 0,1 + 1. Получаем:

При D{0, 1} величины В'(1, D) смысла не имеют. Удобно положить Предположим, что все значения В'(i, D) уже найдены. При отыскании значений В'(i + 1, D), где i{1, 2,…, n -1}, надо учитывать две возможности:

1. Объект oi+1 обслуживается в рейсе +. Тогда рассматриваемой паре (i + 1, D) непосредственно предшествует ситуация (i, D - i+1).

2. Объект oi+1 обслуживается в рейсе –. В этом случае рассматриваемой паре непосредственно предшествует ситуация(i, D).

С учетом указанных возможностей получаем:

В'(i + 1, D) = min{В'(i, D - i+1) + i+1(0,1 + 1,2 + … + i,i+1 + D), В'(i, D) + здесь i{1, 2,…, n - 1}.

Вычисляемое значение В' (i + 1, D) оказывается равным + в том и только том случае, когда определяемая парой (i + 1, D) ситуация реально возникнуть не может.

Каждая определяемая по формуле (2.41) величина В'(n, D), D{0, 1, 2,…, A1n }, – это минимально возможный суммарный штраф по всем объектам, если в рейсе + на их обслуживание затрачивается время D. Оптимальное значение критерия Кopt рассматриваемой задачи II-1 определяется по формуле Формулы (2.38) – (2.42) суть рекуррентные соотношения динамического программирования для решения задачи (II-1). Процесс вычислений по этим соотношениям удобно представлять как последовательное заполнение таблицы, строки которой соответствуют значениям параметра i, i{1, 2,…, n}, а столбцы – значениям параметра D, D{0,1, 2,…, A1n }. Таблица заполняется по строкам, в порядке роста их номеров. Зафиксировав в процессе вычислений по формуле (2.41) для каждого найденного значения В' (i + 1, D) номер компоненты, на которой реализуется минимум правой части, и определив значение параметра D, на котором достигается минимум правой части (2.42), легко строим искомую оптимальную стратегию.

Приведенный алгоритм решения задачи II-1 имеет такую же оценку вычислительной сложности, как изложенный выше решающий алгоритм для задачи I- в ее общей постановке.

Задача II-2, алгоритм решения Легко видеть, что для модели II утверждение 4.1 неверно. Поэтому предложенный для задачи I-2 решающий метод к задаче II- неприменим. Задачу II-2 можно решить методом динамического программирования.

Пусть В"(i, D) – минимально возможная величина максимального из индивидуальных штрафов по объектам совокупности о1, о2, …, оi при условии, что в рейсе + общее время, затрачиваемое на обслуживание объектов из этой совокупности, равно D. Так же, как при рассмотрении предыдущих задач, возможные значения параметра D целочисленны и лежат в числовом диапазоне [0, A1n ].

В"(1, 0) – это величина индивидуального штрафа по объекту о1 в случае, когда его обслуживание реализуется в рейсе -, т.е. завершается в момент времени 0,1 + 1 + Т. В то же время В"(1, 1) – величина индивидуального штрафа по тому же объекту о1, если его обслуживание выполняется в рейсе +, т.е. завершается в момент 0,1 + 1.

Поэтому При D{0, 1} величины В"(1, D) смысла не имеют. Полагаем Предположим, что все значения В"(i, D) найдены. Для отыскания величин В"(i+1, D), где i{1, 2,…, n-1}, с учетом имеющихся возможностей обслуживания объекта oi+1 записываем:

здесь i{1, 2,…, n - 1}.

Вычисляемое значение В"(i + 1, D) оказывается равным + в том и только том случае, когда определяемая парой (i + 1, D) ситуация возникнуть не может.

В итоге итерационного процесса каждая вычисленная по формуле (2.46) величина В"(n, D), D{0,1, 2,…, A1n }, – это минимально возможная величина наибольшего из индивидуальных штрафов по всем объектам в ситуации, когда в рейсе + на их обслуживание затрачивается время D. Оптимальное значение критерия Кopt рассматриваемой задачи II-2 определяется по формуле Равенства (2.43) – (2.47) суть рекуррентные соотношения динамического программирования для решения задачи (II-2).

Оценка вычислительной сложности изложенного алгоритма решения задачи (II-2). такая же, как для приведенных общих алгоритмов решения задач I-1 и II-1.

1. В условиях двухпроцессорной задачи мастера требуется построить оптимальное расписание обслуживания заявок 1 – 6 со следующими характеристиками:

а(1) = 4, (1) =1; а(2) = 7, (2) =2; а(3) =8, (3) =3; а(4) =4, (4) =3;а(5) =10, (5) =5;

а(6) =17, (6) =4.

2. Записать рекуррентные соотношения динамического программирования для решения трехпроцессорной задачи мастера.

3. Обобщенная на случай нелинейных функций индивидуального штрафа однопроцессорная задача мастера определяется следующими исходными данными:

обслуживанию подлежат заявки 1,2,3,4; продолжительности обслуживания заявок: (1) = 4, (2) = 1, (3) =3, (4) =1; функции индивидуального штрафа: 1(t) = 4t2, 2(t) = 3t, 3(t) = 2t2+ t, 4 (t) = t2+2t. Требуется найти оптимальное расписание обслуживания.

4. Задача однопроцессорного обслуживания множества заявок с минимаксным критерием определяется следующими исходными данными: обслуживанию подлежат заявки 1,2,3,4,5; продолжительности обслуживания заявок: (1) = 3, (2) = 2, (3) =4, (4) =1, (5) =2; функции индивидуального штрафа: 1(t) = 4t2, 2(t) = 3t, 3 (t) = t2+ t, 4 (t) = t2+2t, 5 (t) = t3+1. Требуется найти оптимальное расписание обслуживания.

5. Задача однопроцессорного обслуживания множества заявок при наличии директивных сроков определяется следующими исходными данными: (1) = 4, d(1)=5;

(2)=3, d(2) = 6; (3)= 5; d(3)=9; (4)= 2, d(4) = 9; (5)=3; d(5)= 10; (6) = 4; d(6)= 12;

(7)= 4; d(7) = 13; (8) = 4, d(8)= 15. Найти расписание, обеспечивающее выполнение в срок максимально возможного числа заявок.

6. Записать соотношения динамического программирования для решения задачи двухпроцессорного обслуживания множества заявок при наличии директивных сроков. В этой задаче для каждой заявки i, i= 1, n, считаются заданными продолжительность обслуживания (i) и директивный срок d(i); требуется построить расписание, минимизирующее число нарушений предписанных заявкам директивных сроков.

7. Каноническая задача однопроцессорного обслуживания потока из шести заявок характеризуется следующими данными: t(1) = 0, (1) = 3, а(1) = 4; t(2)=0, (2) = 4, а(2) = 7; t(3)=1, (3) = 1, а(3) = 8; t(4)=3, (4) = 2, а(4) = 7; t(5) = 5, (5) = 3, а(5) = 3;

t(6)=5, (6) = 2, а(6) = 7. Методом динамического программирования (обратный счет) требуется определить оптимальное расписание обслуживания.

8. Каноническая задача однопроцессорного обслуживания потока из шести заявок характеризуется следующими данными: t(1) = 0, (1) = 2, а(1) = 3; t(2)=1, (2) = 4, а(2) = 7; t(3)=1, (3) = 1, а(3) = 8; t(4)=3, (4) = 2, а(4) = 7; t(5)=5, (5) = 3, а(5) = 3;

t(6)=5, (6) = 2, а(6) = 7. Методом динамического программирования (прямой счет) требуется определить оптимальное расписание обслуживания.

9. В задаче однопроцессорного обслуживания потока заявок с линейными функциями индивидуальных штрафов и директивными сроками в совокупности расписаний, обеспечивающих соблюдение максимального числа сроков, найти последовательность обслуживания с минимальным значением суммарного штрафа по заявкам. Характеристики заявок следующие: t(1) = 0, (1) = 3, 1(t) = t, d(1) = 5; t(2) = 2, (2) = 3, 2(t) = 4t, d(2) = 5; t(3) = 3, (3) = 4, 3(t) = 2t, d(3) =7; t(4) = 4, (4) = 3, 4(t) = 3t, d(4) = 9; t(5) = 6, (5) = 1, 5(t) = 4t, d(5) = 7.

10. Записать рекуррентные соотношения динамического программирования для задачи распределения заявок потока R = {1, 2,..., n} между двумя идентичными параллельными процессорами. Считается, что каждый процессор обслуживает направляемые ему заявки в порядке возрастания их номеров. Каждая заявка i характеризуется тремя целочисленными параметрами: t(i) момент поступления в систему обслуживания (0 = t(1) t(2) … t(n - 1) t(n)); (i) требуемая продолжительность обслуживания любым из процессоров ((i)> 0); a(i) штраф за единицу времени пребывания в системе обслуживания. Минимизируемым критерием является суммарный штраф по всем заявкам.

ГЛАВА 3. ТРУДНОРЕШАЕМЫЕ ЗАДАЧИ.

ПОЛИНОМИАЛЬНО РАЗРЕШИМЫЕ КОНКРЕТИЗАЦИИ,

ПРИБЛИЖЕННЫЕ И ЭВРИСТИЧЕСКИЕ АЛГОРИТМЫ.

В данной главе изучаются вопросы вычислительной сложности задач и алгоритмов. Выделяются класс задач, разрешимых в полиномиальном времени, и класс труднорешаемых задач. Алгоритм решает задачу в полиномиальном времени, если число выполняемых им элементарных операций не превышает Р(L), где Р – некоторый полином от L – объема входной информации по решаемой задаче. Число элементарных операций, гарантирующих получение искомого результата в труднорешаемой задаче, в лучшем случае имеет оценку, экспоненциально зависящую от объема определяющей задачу входной информации. Для ряда труднорешаемых задач дискретной оптимизации в данной главе выделяются полиномиально разрешимые конкретизации; излагаются общие принципы построения приближенных и эвристических алгоритмов, строятся процедуры, позволяющие синтезировать качественные в том либо ином смысле решения за реально приемлемое время.

3.1. Полиномиально разрешимые и NP-трудные задачи.

Различные математические задачи имеют различную трудность. Трудность любой задачи естественно характеризовать сложностью простейшего из алгоритмов ее решения. Для оценки сложности алгоритмов имеются два принципиально разных подхода. При первом подходе оценки отображают сложность создания алгоритма, здесь учитывается количество операторов в записи алгоритма, количество циклов, глубины циклов и т.д. При втором подходе оценки характеризуют сложность реализации алгоритма; такими оценками являются используемый объем памяти и количество элементарных операций, выполняемых при реализации алгоритма (что соответствует времени машинного счета). Именно второй подход является целесообразным при классификации задач по их вычислительной сложности.

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

Необходимый объем памяти и количество элементарных операций, выполняемых при реализации алгоритма, являются функциями от объема входной информации по решаемой индивидуальной задаче. Объем входной информации можно задавать, например, в байтах.

Каждому алгоритму А соотносим функции TА(L) и VА(L), где TА(L) – верхняя оценка количества элементарных операций, а VА(L) – верхняя оценка размера необходимой памяти при решении задачи с объемом входной информации L.

Будем говорить, что задача Z имеет полиномиальную временную сложность (решается в полиномиальном времени, полиномиально разрешима), если для нее существует решающий алгоритм А* такой, что TА*(L) Р1(L); здесь Р1(L) – некоторый полином от одной переменной L. Задача Z имеет полиномиальную емкостную сложность, если для нее существует решающий алгоритм А' такой, что VА'(L) Р2(L);

здесь Р2(L) – некоторый полином от одной переменной L. Отметим следующий очевидный факт: если задача Z имеет полиномиальную временную сложность, то ее емкостная сложность также полиномиальная.

Возможны дальнейшие разбиения классов задач, имеющих полиномиальную временную и емкостную сложность. Так задача Z разрешима в линейном времени, если для нее существует решающий алгоритм А такой, что TА(L) СL; задача Z разрешима в квадратичном времени, если для нее существует решающий алгоритм А такой, что TА(L) СL2; здесь и далее в приводимых оценочных неравенствах С обозначает некоторую фиксированную константу.

Приведем несколько примеров полиномиально разрешимых задач из числа рассмотренных в предыдущих главах: классическая задача о назначениях; задача отыскания кратчайших путей; задача мастера; задача Джонсона для двух станков.

Наряду с классом полиномиально разрешимых задач, имеется обширная совокупность важных в теоретическом и прикладном аспектах задач дискретной математики, для которых не удалось построить полиномиальных решающих алгоритмов, но которые разрешимы в экспоненциально зависящем от объема входной информации времени.

Будем говорить, что задача Z имеет экспоненциальную временную сложность (разрешима в экспоненциальном времени, экспоненциально разрешима), если для нее существует решающий алгоритм А такой, что TА(L) СаL; здесь а – некоторая превышающая единицу константа.

В качестве примеров экспоненциально разрешимых задач приведем задачу о ранце, задачу коммивояжера, каноническую задачу однопроцессорного обслуживания потока заявок, задачи Джонсона для трех и более станков.

Объем входной информации по подлежащей решению индивидуальной задаче нередко оценивается числом определяющих эту задачу параметров. Если все параметры – лежащие в фиксированном диапазоне целые числа, то между верхней оценкой показателя L и числом параметров n имеется линейная взаимосвязь. В таком случае можно считать, что характеристики временной и емкостной сложности решающего алгоритма, являются функциями от n.

TА(n) = n 0,00001сек 0,00002 сек 0,00003 сек 0,00004 сек 0,00005 сек 0,00006 се Таблица 3.1. Затраты времени при полиномиальных и экспоненциальных функциях сложности.

экспоненциальных по вычислительной сложности алгоритмов значительно. Взятая из [7] таблица 3.1 позволяет сравнивать скорости роста нескольких типичных полиномиальных и экспоненциальных функций. В клетках этой таблицы представлены продолжительности решения задач при определяемых столбцами значениях параметра n и определяемых строками функциях временной сложности; быстродействие ЭВМ считается равным 106 операций в секунду.

Принципиальная разница между алгоритмами полиномиальной и экспоненциальной временной сложности проявляется также при анализе влияния быстродействия ЭВМ на размеры реально решаемых задач. Взятая из той же монографии [7] таблица 3.2 показывает, как увеличатся размеры решаемых за один час задач при увеличении быстродействия ЭВМ в сто и тысячу раз в сравнении с современными машинами. Заметим, что для функции TА(n) = 2n увеличение скорости вычислений в 1000 раз приводит к тому, что размер наибольшей решаемой за 1 час задачи возрастает только на 10, в то время как при квадратичной функции временной сложности этот размер увеличивается более чем в 30 раз.

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

Таблица 3.2. Наибольшие размеры задач, решаемых за один час.

Следует отметить, что между понятиями "труднорешаемая задача" и "задача, неразрешимая в реально приемлемом времени" нельзя ставить знак тождества.

Различие между эффективными и неэффективными алгоритмами может иметь иной характер, если размеры решаемых задач невелики (функция T1(n) = 2n, например, принимает при n 20 меньшие значения, чем функция T2(n) = n5). Кроме того, широко известны некоторые имеющие экспоненциальную сложность алгоритмы, хорошо зарекомендовавшие себя в практике решения задач средних и даже больших размеров.

Это объясняется тем, что временная сложность T(L) определена как верхняя граница числа необходимых операций при любом входе объема L, включая и наихудший возможный случай; именно на наихудший случай ориентирована оценка T(L). Оценка же "в среднем" может иметь существенно меньший порядок роста. Такова, в частности, ситуация с симплекс-методом [26] для решения задач линейного программирования;

только в среднем этот метод дает полиномиальную оценку времени счета.

Остановимся на вопросе установления труднорешаемости, т.е. определения невозможности построения для рассматриваемой задачи полиномиального по верхней оценке временной вычислительной сложности алгоритма решения. Будем рассматривать два класса дискретных задач – задачи оптимизации и задачи распознавания.

В каждой задаче распознавания считается определенным некоторый универсум U, в котором выделено подмножество V; по произвольному элементу х из U требуется определить, принадлежит ли х подмножеству V. Приведем два примера.

Пусть U – множество всех натуральных чисел, а подмножество V является совокупностью всех простых чисел. По натуральному числу х требуется определить, является ли оно простым.

Пусть U – множество всех конечных графов, а подмножество V является совокупностью всех гамильтоновых графов [14]. По конечному графу G требуется определить, является ли он гамильтоновым.

Решить задачу распознавания означает ответить "да" или "нет" на поставленный вопрос. В случае, если в задаче распознавания правильным является ответ "да", будем говорить, что эта задача имеет положительное решение.

Для ряда задач распознавания полиномиальные по верхней оценке временной вычислительной сложности алгоритмы известны. В качестве примеров приведем задачу определения по сети с ограниченными пропускными способностями дуг, возможен ли в ней поток заданной мощности [6], и задачу определения по графу, является ли он эйлеровым [14]. Для многих других задач, в том числе важных с точки зрения приложений, таких алгоритмов построить не удалось. К последним относятся, в частности, следующие задачи.

1. ВЫПОЛНИМОСТЬ КНФ. Задана конъюнктивная нормальная форма (КНФ) F от n переменных. Требуется определить, является ли F выполнимой (КНФ выполнима, если существует набор логических значений переменных, обращающий ее в истину).

ТРЕХМЕРНОЕ СОЧЕТАНИЕ. Дано множество М XxYxZ, где X, Y, Z – непересекающиеся множества, каждое из которых состоит из равного числа элементов q. Требуется определить, содержится ли в М состоящее из q элементов подмножество М' такое, что никакие два элемента из М' не имеют ни одной равной координаты.

3. ВЕРШИННОЕ ПОКРЫТИЕ. Заданы n-вершинный граф G и натуральная константа k, k n; координаты х1, х2,..., хq перечисляют номера завершенных обслуживанием заявок из совокупности М(t, S, d).

Если в совокупности М(t, S, d) обслужено только s заявок, где s < q, то хs+1 =хs+2=...= хq = 0. Вектор Х(Q) будем называть вектором-описанием. Доопределим Х() как нульвектор. Если Х – вектор-описание, то пара (Х, t) – это состояние системы в момент времени t. Отметим, что по паре (Х, t) совокупность не обслуженных по состоянию на момент времени t заявок Q определяется однозначно: Q = Q(Х, t).

Пусть dq(Х, t) обозначает минимальную величину суммарного штрафа по всем необслуженным до момента времени t заявкам для системы, находящейся в состоянии (Х, t). При этом считается, что возможными являются только расписания из множества (d,q).

Начальному состоянию системы соответствует вектор-описание Х(V(0)).

Поэтому Пусть Qdq(Х, t) – множество заявок, совпадающее с Q(Х, t), если последняя координата вектора Х нулевая, и состоящее только из заявок множества Q(Х, t) с номерами не больше ( Q(Х, t))+ d в противном случае. При синтезе (d, q)-расписания в ситуации, определяемой парой (Х, t), выбор очередной направляемой на процессор заявки осуществляется только из совокупности Q dq(Х, t).

Соотношение динамического программирования для решаемой задачи (3.9) записывается следующим образом:

dq(Х, t) = { a(i)[max(t, t(i))+(i)-t(i)] + dq(Х(Q(Х, t)) \ {i}), t +(i))} для любого > 0.

Реализация определяемой рекуррентными соотношениями (3.10) - (3.11) вычислительной процедуры осуществляется в порядке убывания значений аргумента t, процесс счета заканчивается отысканием величины dq(Х(V(0)), 0) – оптимального значения критерия в рассматриваемой задаче (3.9). Отметим, что подсчет по формуле (3.10) каждого отдельного значения функции dq(Х, t) выполняется в линейно зависящем от n времени. Число рассматриваемых (d + q + 1)-мерных векторовсостояний Х ограничено сверху величиной nq+12d, поскольку первая и q последних координат этого вектора принимают значения из множества {1, 2,..., n}, а остальные координаты булевы. В итоге получаем, что общее число рассматриваемых наборов значений аргументов функции dq имеет порядок nq+22d, а верхней оценкой временной вычислительной сложности изложенного алгоритма решения задачи (3.9) оказывается О(nq+32d).

Качество оптимального (d, q)-расписания обслуживания входного потока заявок зависит от выбора значений параметров: чем больше d и q, тем шире область возможных дисциплин обслуживания, что позволяет синтезировать расписания меньшей суммарной стоимости. При этом увеличение значения q на единицу предпочтительнее такого же увеличения значения d, ибо в большей степени расширяет класс допустимых расписаний. Вместе с тем, повышение значения q на единицу сопровождается ростом вычислительной сложности предложенного алгоритма в n раз, в то время как повышение на единицу значения d увеличивает число выполняемых элементарных операций лишь в два раза.

Сейчас обратимся к еще одной массовой задаче – классической задаче о ранце (КЗР); рассмотрим вопрос выделения в рамках этой общей модели полиномиально разрешимых частных классов задач.

Для решения КЗР в главе 1 был описан алгоритм Акзр с верхней оценкой числа выполняемых элементарных операций СnW, где n – число имеющихся предметов, W – максимально допустимая величина суммарного веса помещаемых в ранец предметов, а С – константа, не зависящая от конкретных значений n и W. Внешняя простота приведенной оценки не свидетельствует о разрешимости задачи в полиномиально зависящем от объема входной информации времени. Ясно, что увеличение максимально допустимого суммарного веса помещенных в ранец предметов в 10k раз влечет за собой увеличение длины записи параметра W в составе входной информации по задаче только на k десятичных разрядов. В то же время приведенная оценка числа выполняемых алгоритмом Акзр элементарных операций возрастает в 10k раз.

Классическая задача о ранце относится к числу NP-трудных, ибо к ней за полиномиально зависящее от объема входной информации время сводится NP-полная задача "Разбиение" (способ построения по исходным данным задачи "Разбиение" соответствующей КЗР дан в главе 1).

Через Квес[Q] обозначим подкласс задач о ранце с n предметами, в которых вес каждого предмета не превосходит Q(n), здесь Q(n) – многочлен от одной переменной с неотрицательными коэффициентами. Так как суммарный вес всех имеющихся предметов больше W (иначе задача решается тривиальным образом – в ранец следует поместить все предметы), получаем: W < nQ(n). Для задач рассматриваемого подкласса верхней оценкой числа выполняемых алгоритмом Акзр элементарных операций является Сn2Q(n), эта оценка от числа предметов n зависит полиномиально. Получаем, что задачи любого подкласса Квес[Q], где Q(n) – произвольная полиномиальная монотонно возрастающая функция от одной переменной, разрешимы в полиномиальном времени.

Изложим еще один способ решения классической задачи о ранце.

Предлагаемый алгоритм Bкзр основан на последовательном построении списков.

Каждая запись любого списка имеет вид, где М – подмножество предметов, С и V – соответственно суммарная стоимость и суммарный вес предметов подмножества М. Список S0 считается состоящим из одной записи:. Далее поэтапно строятся списки Si для значений i последовательно равных 1, 2,…, n.

Составление каждого очередного списка Si реализуется в два шага. На первом шаге для каждой записи z = списка Si-1 определяется новая запись z* =, записи z и z* включаются в формируемый рабочий список Ri; результатом первого шага является список Ri, содержащий в сравнении со списком Si-1 вдвое больше записей. На втором шаге из списка Ri изымаются: а) все записи, в которых значение третьей компоненты превышает W (нарушено весовое ограничение); б) каждая запись имеют одинаковое число элементов. Каждое независимое множество С из М можно расширить до базы путем поочередного добавления к нему новых элементов, присоединение которых не нарушает независимости, вплоть до момента, когда таких элементов не существует.

Приведем еще один, эквивалентный предыдущим, способ задания матроида.

Матроид – это пара < М, В>, где где М – произвольное конечное множество, а В – семейство его подмножеств, удовлетворяющее аксиомам:

В1) Никакое множество из семейства В не содержится в другом множестве этого семейства.

В2) Если В1 и В2 входят в семейство В, то для любого элемента х из В существует элемент у из В2 такой, что совокупность (В1 \ x) у тоже входит в семейство Элементы семейства В – базы матроида.

Рассмотрим несколько примеров матроидов.

1. Пара, где M – произвольное конечное непустое множество, является матроидом, единственной базой которого служит само множество M.

2. Пусть L – линейное пространство, ML – произвольное конечное непустое подмножество из L, I – множество, элементами которого служат все линейно независимые системы векторов из M и пустое множество. Тогда пара является матроидом с набором независимых множеств I. Такой матроид именуется векторным матроидом, порожденным множеством векторов M. Базами этого матроида являются все базы множества M. В частности, взяв в качестве M множество векторов, являющихся столбцами (строками) некоторой матрицы В, получаем матричный матроид. Ранг матроида равен рангу матрицы В.

3. Пусть G – произвольный конечный неориентированный граф, M – множество всех его ребер. Подмножество ребер Х, ХM, является базой (элементом совокупности В), если это подмножество образует некоторый остов данного графа. Для пары < М, В > аксиомы В1 и В2 выполняются, данная пара образует матроид.

Т е о р е м а 3.3. (Теорема Радо-Эдмондса). Если пара – матроид, то для любой весовой функции применением к данной паре G-алгоритма конструируется множество Х, являющееся независимым множеством с наибольшим весом. Если же пара не является матроидом, то существует такая весовая функция f(x), что конструируемое применением G-алгоритма множество Х не является независимым множеством с наибольшим весом.

Теорема Радо-Эдмондса дает ответ на поставленный для задач класса К* вопрос об условиях, при которых G-алгоритм строит решения, являющиеся оптимальными.

Достаточно интересен следующий вопрос. Пусть в массовой задаче Z жадный алгоритм А строит, вообще говоря, неоптимальные решения (оптимальными они оказываются лишь для некоторых индивидуальных задач - конкретизаций Z). По синтезированному алгоритмом решению произвольной индивидуальной задачиконкретизации Z1 требуется определить, оптимально ли это решение.

В случае, если массовая задача Z – это задача коммивояжера, сформулированный вопрос об оптимальности построенного жадным алгоритмом решения произвольной индивидуальной задачи Z1 не имеет алгоритма получения ответа с полиномиальной верхней оценкой числа выполняемых элементарных операций (считается, что Р NP). Данный факт прямо следует из доказательств теорем 19.5 и 19.6 монографии [17].

Введем понятие -оптимального решения, рассмотрим вопросы синтеза таких решений.

Для произвольной задачи с обозначаемым через К* ненулевым оптимальным значением критерия решение Х назовем - оптимальным, если Дробь{|К* – К(Х) |/ К*} называем относительным отклонением критерия К(Х) при решении Х от своего оптимального значения.

Если для какой-либо труднорешаемой задачи оптимизации построен эвристический алгоритм, то естественно возникает вопрос, существует ли, при котором построенный алгоритм является способом синтеза -оптимальных решений. В случае положительного ответа возникает новый вопрос – каково минимальное значение, при котором алгоритм сохраняет -оптимальность.

Рассмотрим формулируемую следующим образом задачу об упаковке в контейнеры. Задано конечное множество предметов А = {a1,a2,…,an}; каждый предмет ai имеет "размер" v(ai), где v(ai) – рациональное число, принадлежащее отрезку [0,1];

требуется найти разбиение множества А на попарно непересекающиеся подмножества А1, А2,…,Аg такое, чтобы сумма "размеров" элементов каждого подмножества не превосходила 1 и чтобы значение g (число подмножеств в разбиении) было минимально возможным. Здесь мы считаем, что предметы одного подмножества должны упаковываться в один контейнер "размера" 1 и наша цель – использовать как можно меньшее число контейнеров.

Введенная задача NP-трудна в сильном смысле, ибо в частном случае она дает задачу "3-разбиение". С учетом гипотезы Р NP, можно утверждать отсутствие для задачи об упаковке в контейнеры даже псевдополиномиального алгоритма синтеза оптимального решения. Однако имеется несколько весьма простых алгоритмов синтеза для этой задачи -оптимальных решений.

Один из таких алгоритмов известен под названием "Первый подходящий (ПП)". Предположим, что имеется бесконечная последовательность контейнеров размера 1, каждый из них в начальный момент пуст. Предметы множества А распределяем по контейнерам согласно следующему простейшему правилу: очередной (по возрастанию индекса) предмет ai помещается в контейнер с наименьшим номером, у которого сумма размеров уже помещенных в него предметов не превосходит 1 – v(ai).

Иными словами, предмет ai помещается в первый контейнер, куда его поместить можно. Отметим, что алгоритм ПП не начинает заполнять новый контейнер до тех пор, пока можно использовать контейнеры, уже начатые заполнением.

Обозначим через ХПП решение задачи об упаковке в контейнеры, конструируемое изложенным алгоритмом. Число нужных при этом решении контейнеров К(ХПП) удовлетворяет неравенству Действительно, в противном случае в построенном решении обязательно найдутся два непустых, но загруженных менее чем на половину контейнера, что невозможно. То, что указанная граница – наилучшая из возможных, следует из рассмотрения задачи с множеством предметов А = {a1,a2,…,an}, где v(ai) = (1/2) +,.

i=1, n. Так как никакие два предмета не могут быть помещены в один контейнер, общее число нужных контейнеров равно n. В то же время суммарный размер предметов равен (n/2) + n; если выбрать достаточно малым, суммарный размер окажется сколь угодно близким к n/2.

Оценим, как К(ХПП) может отличаться от минимально необходимого числа контейнеров К*. Очевидно неравенство Из соотношений (3.14) - (3.15) получаем, что К(ХПП) 2К*. Таким образом, алгоритм ПП для решения задачи упаковки в контейнеры является -оптимальным при = 1. Более тонкие рассуждения (см. [7]) дают возможность установить оптимальность алгоритма ПП для = 7/10.

Очевидно, что алгоритм ПП можно модифицировать, введя, например, такое правило размещения: каждый следующий предмет ai помещается в тот контейнер, содержимое которого ближе всего к 1 – v(ai), но не превосходит эту величину; если имеется несколько таких контейнеров, то из них выбирается имеющий минимальный номер. Такой алгоритм можно назвать "Наилучший из подходящих (НП)". К сожалению, оказывается, что алгоритм НП не является существенно лучшим, чем алгоритм ПП; характеристики этих алгоритмов практически совпадают.

Сейчас предположим, что предметы совокупности А упорядочены не произвольно (как это считалось ранее), а по уменьшению размеров. Процедура применения алгоритма ПП к упорядоченному таким образом списку предметов называется "Первый подходящий в порядке убывания (ПППУ)". Решение, получаемое этой процедурой, обозначим ХПППУ. Тогда К (ХПППУ) - число нужных при этом решении контейнеров. Минимально необходимое число контейнеров в рассматриваемой задаче по-прежнему обозначаем К*. Имеет место следующий результат.

Т е о р е м а 3.4 (Теорема Джонсона). Для любой задачи об упаковке в контейнеры выполняется неравенство Более того, существуют задачи об упаковке в контейнеры, для которых Сейчас рассмотрим классическую задачу о ранце при условиях и задачу о ранце с дробимыми предметами, отличающуюся от классической заменой условия (3.18) на В задаче (3.16)-(3.17)-(3.18') считается, что предметы в ранец можно помещать не только целиком, но и частями. Для этой задачи известен очень простой способ синтеза оптимального решения – алгоритм Данцига [8]. Этот алгоритм заключается в следующем. Для каждого i-го предмета вычисляется показатель i = сi / vi; далее предметы помещаются в ранец последовательно, в порядке убывания показателя i, до тех пор, пока остается выполненным ограничение (3.17); первый предмет, который нельзя поместить в ранец целиком, делится на две части так, что первая (помещаемая в ранец) часть имеет вес, обеспечивающий выполнение условия (3.17) как точного равенства. Вторая часть разделенного на части предмета в ранец не помещается, так же как и все следующие далее предметы.

Для задачи (3.16)-(3.18) алгоритм Данцига может трактоваться как следующая эвристическая процедура: для каждого i- го предмета вычисляем показатель i = сi / vi;

помещаем в ранец предмет с наибольшим значением этого показателя (если таких предметов несколько - первый из них по номеру), каждый следующий (по убыванию показателя i) предмет помещается в ранец, если это позволяет сделать ограничение (3.17). Изложенную процедуру именуем эвристическим алгоритмом Данцига (ЭАД).

Рассмотрим следующий пример классической задачи о ранце:

здесь М – натуральная константа, удовлетворяющая ограничению М 3.

Для приведенной задачи ЭАД строит решение Х =(1,0); обеспечиваемое этим решением значение критерия равно 2. В то же время оптимальным является решение Х* = (0,1), обеспечивающее значение критерия М. Так как константа М может быть сколь угодно большой, ЭАД не является - оптимальным ни при каком значении.

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

при ограничениях Если к данной задаче применить алгоритм Bкзр, то получим, что оптимальным решением является совокупность предметов с множеством номеров М(!) = {1, 2, 3, 6, 7}, а оптимальное значение критерия С(!) равно 777. В процессе реализации алгоритма приходится построить списки, суммарное число записей в которых оказывается равным 91. Естественная идея упрощения заключается в замене нулем младшего разряда в каждом из параметров сi. В рассматриваемой задаче получаем следующий критерий:

290х1 + 70х2 + 150х3 + 220х4 + 130х5 + 80х6 + 150х7 max.

При новой критериальной функции получаем М(!) = {1, 3, 4, 6}, а оптимальное значение критерия С(!) равно 740. Здесь при реализации алгоритма Bкзр приходится построить списки, суммарное число записей в которых оказывается равным 36, т.е.

практически втрое меньше, чем раньше. В то же время отличие в значении критерия около 5%; если для полученного множества {1, 3, 4, 6} вычислить значение первоначальной критериальной функции, то получим 768 (отличие от оптимума порядка 1%).

В общем случае, если если при округлении отбросить в числах сi последние t разрядов, то отклонение от оптимального значения критерия не будет превышать 10tn.

Время, необходимое для работы алгоритма при решении исходной задачи не превосходит kс*n3. После отбрасывания t разрядов оценка временных затрат принимает вид kс*n310-t.

Если решение Х задачи о ранце с n предметами построено алгоритмом Bкзр после того, как в числах сi отброшены последние t разрядов, разность К* – К(Х) не превышает 10tn. При этом К* не меньше, чем с*. Получаем, что найденное решение Х является -оптимальным при некотором (10tn) / с*. Отсюда С учетом последнего неравенства, верхняя оценка числа выполняемых алгоритмом Bкзр элементарных операций kс*n310-t путем замены параметра с* преобразуется к виду kn4/.

Будем говорить, что алгоритм является полиномиальной приближенной схемой (ППС) для массовой задачи оптимизации Z, если по начальным данным индивидуальной задачи Z0 и > 0 он выдает -оптимальное решение этой задачи за время, ограниченное полиномом (зависящим от ) от одной переменной – объема входной информации по решаемой задаче.

Таким образом, нами определена ППС для решения классической задачи о ранце; полином, зависящий от, имеет здесь вид (kn4) /. Полученная оценка полиномиальна относительно n и 1/. Это достаточно удачная ситуация, ибо сделанное определение ППС допускает полином, в котором наибольшей степенью переменной n является, например, 1/.

Алгоритм решения задачи оптимизации А именуем полностью полиномиальной приближенной схемой (ПППС), если время его работы ограничено сверху полиномом от двух переменных, объема входной информации по решаемой задаче и 1/.

В силу полученной оценки вычислительной сложности, определенная нами ППС для решения классической задачи о ранце является ПППС.

Т е о р е м а 3.5. В предположении Р NP при любом > 0 для задачи коммивояжера нет решающей ППС.

Положим противное; допустим, что при некотором 0 > 0 имеется ППС, решающая задачу коммивояжера. Покажем, что в таком случае существует способ решения задачи "Гамильтонов цикл" за полиномиальное время.

По произвольному конечному ориентированному графу G с множеством вершин {1, 2,…,n} строим (nxn)- матрицу S={sij}, определяющую задачу коммивояжера.

Полагаем, что все элементы главной диагонали матрицы S нулевые; в случае i j элемент sij этой матрицы равен 1 тогда и только тогда, когда в графе G имеется дуга (i, j); если i j и дуги (i, j) в графе нет, элемент sij полагаем равным 2+n0.

Применим к построенной задаче коммивояжера ППС, конструирующую 0оптимальное решение этой задачи. Утверждаем, что этой схемой в построенной задаче коммивояжера будет найдено решение с суммарной длиной обхода n тогда и только тогда, когда в исходном графе G гамильтонов цикл имеется. Если применением ППС в задаче коммивояжера найдено решение с суммарной длиной обхода n (решений меньшей длины в построенной задаче существовать не может), то граф G, очевидно, гамильтонов. Докажем справедливость обратного утверждения. Предположим противное, т.е. что граф G гамильтонов, а применением ППС строится решение задачи коммивояжера с суммарной длиной обхода большей, чем n. В таком случае суммарная длина обхода не меньше n + 1+ n0, ибо реализуется по меньшей мере один элементарный переход длины 2+n0. Вместе с тем, так как граф G гамильтонов, оптимальное значение критерия в построенной задаче коммивояжера равно n. Разность между значением критерия для решения, построенного применением ППС, и оптимальным его значением оказывается не меньше n0 + 1, а относительное отклонение критерия задачи при найденном ППС решении от оптимального его значения оказывается не меньшим 0 + 1/n. Но это противоречит утверждению о том, что применяемая ППС строит 0-оптимальное решение. Получаем, что применением ППС в построенной задаче коммивояжера решение с суммарной длиной обхода n строится тогда и только тогда, когда в исходном графе G гамильтонов цикл имеется.

Таким образом, рассматриваемая ППС в полиномиальном времени решает проблему определения по произвольному графу, является ли он гамильтоновым. В предположении Р NP это невозможно. Методом от противного теорема доказана.

Многие алгоритмы решения оптимизационных задач, в том числе задач комбинаторной оптимизации, основаны на принципе локального поиска. Его суть достаточно проста.

– произвольная задача дискретной оптимизации. Предполагаем, что для каждого X из D определена окрестность G(Х), при этом XG(Х). Решения, принадлежащие окрестности G(Х), это в том либо ином смысле близкие X решения. Алгоритмы локальной оптимизации имеют следующую общую структуру:

1. Находим исходное допустимое решение Х0, Х0D; полагаем k =0;

2. По имеющемуся допустимому решению Хk определяем окрестность этого решения G(Хk); перебором принадлежащих окрестности решений находим решение Х*, оптимизирующее значение критерия при условии, что X G(Хk). Если К(Хk)= К(Х*), то Хk - локальный оптимум. В противном случае переходим к п.3.

3. Полагаем k = k +1;

4. Полагаем Хk = Х* и переходим к п.2.

Разработка конкретных алгоритмов локального поиска предусматривает несколько принципиальных этапов. Во-первых, нужно определить процедуру определения исходного допустимого решения. Иногда оказывается целесообразным осуществлять поиск, отправляясь из нескольких начальных точек (далее выбирается лучшее из полученных решений). Во-вторых, для рассматриваемой задачи нужно выбрать подходящий способ определения окрестностей; надо иметь в виду, что число точек в каждой совокупности G(Х) должно быть относительно небольшим (поиск оптимума в окрестности осуществляется перебором). Вместе с тем, если окрестности слишком малы, то процесс поиска экстремума оказывается малоэффективным.

Отметим, что симплекс-метод решения задач линейного программирования может трактоваться как локальный поиск; совокупность D – вершины многогранника ограничений, окрестность каждой точки Х из D включает вершины, смежные с вершиной Х.

В задаче коммивояжера понятие k-окрестности (k – натуральное число, фиксирующее размер окрестности, k 2) определим следующим образом: гамильтонов цикл С* принадлежит k-окрестности гамильтонова цикла С, если С* можно получить из С путем замены не более чем k дуг. Выполненные эксперименты показывают, что использование систем окрестностей при k =2 малоэффективно, при k = 3 получаются достаточно хорошие (в среднем) результаты; переход к значению k = 4 существенно увеличивает время вычислений и мало улучшает качество получаемых результатов.

3.4. Эвристические алгоритмы для задач синтеза расписаний обслуживания.

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

Рассмотрим общие схемы некоторых эвристических алгоритмов, прежде всего для введенной в главе 2 канонической задачи однопроцессорного обслуживания потока заявок; наложение каких-либо дополнительных ограничений на модель обслуживания здесь не предполагается.

Следует указать две сферы приложений эвристических алгоритмов: 1) синтез расписаний приемлемого для практического использования качества; 2) получение нижних оценок, которые оказываются необходимыми для точного решения задач синтеза оптимальных расписаний методом ветвей и границ [13]. Вторая сфера предполагает многократное использование эвристического алгоритма в процессе решения одной задачи; он должен обладать достаточным быстродействием, хотя получаемые оценки могут быть относительно грубыми.

В канонической модели однопроцессорного обслуживания заявки потока R = {1, 2,..., n} считаются пронумерованными в порядке их поступления (0 = t(1) t(2)...

t(n)). Дополнительно полагаем, что заявки, поступающие на обслуживание одновременно, получают очередные номера в порядке убывания показателя µ(i) = а(i)/(i).

Первый эвристический алгоритм тривиален, он основан на принципе «первый пришел – первым обслуживается (ПП-ПО)» Результатом применения алгоритма ПППО, с учетом принятого способа нумерации заявок, всегда является расписание = (1, 2,..., n). Как правило, более качественными, оказываются расписания, конструируемые µ-алгоритмом, предусматривающим, что в каждый момент принятия решения по загрузке освободившегося процессора из совокупности ожидающих обслуживания выбирается заявка с наибольшим значением показателя µ = а(i)/(i).

Изложим идею следующего эвристического алгоритма, назовем его (p,q)алгоритмом, здесь p и q – небольшие натуральные числа (n > p q). На первом этапе работы алгоритма рассматривается начальный отрезок входного потока (подпоток R1), содержащий заявки 1, 2,..., p. Любым точным методом, эффективно работающим благодаря выбранному небольшому значению параметра p, строится минимизирующая суммарный штраф последовательность 1 обслуживания заявок этого подпотока;

начальный, длины q, отрезок последовательности 1 считаем начальным отрезком синтезируемого расписания обслуживания * заявок исходного потока R = {1, 2,..., n}; заявки, нашедшие свое место в расписании * из потока R изымаются, получаемый в результате поток обозначаем R1; момент завершения обслуживания заявок, входящих в построенную начальную часть расписания * обозначим Т(*,1). На втором этапе заявки потока R1, поступившие не позднее момента Т(*,1), переупорядочиваются в порядке убывания значений показателя µ(i), получаемый поток обозначаем R(1); далее рассматривается начальный отрезок потока заявок R(1) (подпоток R2), содержащий p заявок; выбранным точным методом строится минимизирующая суммарный штраф последовательность обслуживания заявок этого подпотока 2; начальный, длины q, отрезок последовательности 2 считаем следующим от начала отрезком синтезируемого расписания * обслуживания заявок потока R; заявки, нашедшие свое место в расписании * из потока R изымаются, получаемый в результате поток обозначаем R2;

момент завершения обслуживания заявок, входящих в построенную к данному моменту начальную часть расписания * обозначим Т(*,2). На третьем этапе заявки потока R2, поступившие не позднее момента Т(*,2), переупорядочиваются в порядке убывания значений показателя µ(i), получаемый поток обозначаем R(2) ; далее рассматривается начальный отрезок потока R (2), содержащий p заявок, и т.д., вплоть до момента либо естественного завершения процесса, либо выполнения после некоторого k-го этапа условия Т(R, k) t(n)). При реализации последнего варианта заявки, не вошедшие в сформированную часть расписания, приписываются к ней справа в порядке убывания показателя µ(i).

Легко видеть, что верхней оценкой временной вычислительной сложности изложенного алгоритма (с учетом сортировок) является Сnlog2n, где С – не зависящая от n константа.

Существенна зависимость множителя С от выбора определяющих качество алгоритма значений параметров p и q. Пусть оптимальные решения получаемых частных задач с p заявками синтезируются методом динамического программирования.

Тогда число элементарных операций, выполняемых при решении каждой частной задачи прямо пропорционально р22р. Общее число подлежащих решению задач с p заявками обратно пропорционально q. Получаем, что константа С прямо пропорциональна р22р и обратно пропорциональна q. Чем больше значение p и меньше значение q, тем выше ожидаемое качество решения и тем больше трудоемкость алгоритма его синтеза.

Реально вместо изложенной канонической (p, q)-процедуры целесообразно применение ее естественных модификаций. Так в случае, когда на k+1-ом этапе в совокупность рассматриваемых р заявок подпотока входят только уже поступившие заявки, а первая поступающая позднее момента времени Т(*,k) заявка имеет большее значение показателя µ(i), то эту заявку следует включить в число перспективных к включению на данном этапе.

Концепция (p,q)-алгоритма играет существенную роль и для периодов с относительно большим горизонтом планирования, когда точной может быть информация о моментах поступления только идущих вначале заявок, для последующих заявок моменты прибытия известны как ожидаемые средние значения. Тогда реализация этапов синтеза (p,q)-алгоритмом расписания обслуживания синхронизируется с поступлением уточненных данных о моментах прибытия последующих заявок. С учетом периодичности поступления таких данных выбираются значения параметров p и q.

Идея следующего эвристического алгоритма, именуемого алгоритмом вставки, тоже достаточно проста. На первом этапе определяем оптимальную последовательность 1 обслуживания заявок 1 и 2 в предположении, что других заявок нет; при этом подсчитываются суммарные штрафы по двум указанным заявкам для обеих возможных последовательностей их обслуживания. На втором этапе: если заявка 3 поступает ранее момента завершения обслуживания первой в 1 заявки, подсчитываются суммарные штрафы для трех последовательностей, получаемых из приписыванием заявки 3 к 1 слева, справа и ее вставкой в промежутке между первым и вторым элементом этой последовательности; если заявка 3 поступает между моментами завершения обслуживания первой и второй заявки последовательности 1, суммарные штрафы подсчитываются для двух последовательностей, получаемых из приписыванием заявки 3 справа и ее вставкой между двумя имеющимися элементами последовательности; если заявка 3 поступает не ранее момента завершения обслуживания второй заявки последовательности 1, приписываем заявку 3 к 1 справа.

Через 2 обозначаем ту из последовательностей, для которой суммарный штраф минимален. При определении расположения произвольной заявки k составленную на предыдущем этапе последовательность k-2 разбиваем на две последовательные части k-2 и *k-2, где k-2 – максимально возможная по числу элементов начальная часть такая, что реализация расписания k-2 завершается не позднее момента прибытия заявки k; далее из k-2 путем вставки заявки k на место между частями k-2, *k-2 и на все места правее указанного получаем ряд последовательностей обслуживания; для каждой из полученных последовательностей вычисляем суммарный штраф, последовательность с минимальным значением суммарного штрафа обозначаем k-1.

Итогом работы алгоритма является последовательность обслуживания n-1.