Вероятностный анализ алгоритмов построения кратчайших расписаний для многостадийных систем тема автореферата и диссертации по математике, 01.01.09 ВАК РФ

На правах рукописи

Корякин Роман Александрович

ВЕРОЯТНОСТНЫЙ АНАЛИЗ АЛГОРИТМОВ ПОСТРОЕНИЯ КРАТЧАЙШИХ РАСПИСАНИЙ ДЛЯ МНОГОСТАДИЙНЫХ СИСТЕМ

Специальность 01.01.09 — дискретная математика и математическая кибернетика

Автореферат

диссертации на соискание ученой степени кандидата физико-математических наук

Иркутск — 2005

Работа выполнена в Институте математики им. С. Л. Соболева СО РАН

Научный руководитель:

доктор физико-математических наук, профессор Севастьянов Сергей Васильевич

Официальные оппоненты:

доктор физико-математических паук Кузьмин Олег Викторович

кандидат физико-математических наук, доцент Хамисов Олег Валерьевич

Ведущая организация:

Институт вычислительной математики и математической геофизики СО РАН

Защита состоится 14 октября 2005 г в 11 часов на заседании диссертационного совета Д212.074.01 в Иркутском государственном университете по адресу: СбЮОЗ, г. Иркутск, бульвар Гагарина, 20.

С диссертацией можно ознакомиться в библиотеке Иркутского государственного университета (бульвар Гагарина 24).

Автореферат разослан " " сдс*. 2005 г.

Ученый секретарь диссертационного совета, к.ф.-м.п., доцент

Аргучипцева Маргарита Александровна

¿gg- .„WW

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

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

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

Сформулированные вопросы обосновывают актуальность направления, получившего в течение последних 40 лет широкое развитие в дискретной оптимизации — направление построения асимптотически точных алгоритмов точного и приближённого (с гарантированными оценками точности) решения NP-трудных задач в стохастической постановке (т. е. ко' Chen В Potts С N , Woegmger G J. A Review of Machine Scheduling: Complexity, Algorithms and АрртоттаШйу // Handbook of Combinatorial Optimization. 1998. V. 3 P. 21 169.

РОС. НАЦИОНАЛЬНАЯ БИБЛИОТЕКА СП«1

о*

гда входные данные представлены в виде некоторым образом распределённых случайных величин)2. В теории расписаний для многостадийных систем это направление на текущий момент развито слабо. Наличие всего лишь несколько разрозненных результатов, относящихся к наиболее простым моделям, таким как "Flow Shop" 3, обосновывает актуальность более широкого исследования, обозначения и реализации новых подходов к стохастическим задачам теории расписаний.

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

Цель работы, состоит в применении методов исследования асимптотических свойств NP-трудных задач теории расписаний с помощью вероятностного анализа. В частности, эти методы состоят в вероятностном анализе уже существующих алгоритмов решения этих задач, построении новых алгоритмов на основе информации о входных данных, а также в исследовании асимптотических свойств широких классов расписаний. В данной диссертации проиллюстрировано применение полученных методов и подходов к исследованию таких классических задач теории расписаний как задача о сборочной линии, "Open Shop", "Flow Shop", "Job Shop"c критерием

2Гимади Э X , Гпебов Н И , Перепелппд В А Алгоритмы с оценками для яадач дискретной оптимизации / / Пробтемы кибернетики 1975. № 31 С 35 42

■'Gourgdnd М . Grangeon N , Norre S A Review of the Static Stochastic Flow Shop Scheduling Problem I ■ Juurn of Deawon Systems 2000 Д>9 P 183 214

• •• .......! 4

! A'.KitfMi..i t ' <»<*4<]»>>n "J

• Па m «V

минимум длины расписания (Стах).

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

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

Принципиально новым является детерминированный алгоритм решения задачи компактного суммирования векторов, к которой сводятся многие задачи теории расписаний [1]. Этот алгоритм основан на активном и эффективном использовании информации о структуре входных данных задачи. Подобный подход может быть применён к разрешению многих вопросов, возникающих при исследовании NP-трудных задач дискретной оптимизации в стохастической постановке.

Таким образом, на защиту выносятся следующие результаты:

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

2. Для стохастических задач о сборочной линии, "Job Shop" и "Flow Shop" построены эффективные алгоритмы, которые для широкого класса распределений исходных длительностей операций с высокой вероятностью находят перестановочные расписания с гарантированными оценками длины. Полученные оценки значительно лучше известных ранее оценок для соответствующих детерминистских задач [1].

3. Выявлен широкий класс распределений входных данных стохастической задачи "Open Shop" для которых с высокой вероятностью может быть построено оптимальное расписа-

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

4. Для стохастических задач о сборочной линии и "Flow Shop" рассмотрен алгоритм линейной трудоёмкости, строящий произвольное перестановочное расписание. Доказано, что для широкого класса распределений входных данных каждой из задач отношение длины такого расписания к оптимуму с высокой вероятностью стремится к единице (при возрастании количества работ) [3].

Практическая ценность. Модели, рассматриваемые в теории расписаний, имеют происхождение от задач составления расписаний: движения поездов, самолётов, общественного транспорта; занятий учебных групп в ВУЗе; выполнения вычислительных задач на ВЦ общего пользования; операций на станке с программным управлением; заданий в годовом плане предприятия; передачи пакетов данных в комьютерных сетях, и т. п. И хотя теоретические модели в большой степени идеализированы и абстрагированы от многих практических ограничений, всё же они обладают некоторой "остаточной" практической ценностью. В диссертации рассмотрены наиболее типичные и часто встречающиеся на практике структуры входных данных задач теории расписаний. Все результаты, изложенные в диссертации, связаны с построением и анализом эффективных алгоритмов, т.е. таких алгоритмов, которые имеют сравнительно небольшую временную сложность, и следовательно, способны решать задачи достаточно большой размерности (т.е. такой, какая часто возникает в практических задачах). Это обосновывает практическую ценность полученных результатов.

Личный вклад автора состоит в демонстрации возможностей применения вероятностного анализа к цеховым задачам на построение кратчайших расписаний. Автором разработан новый полиномиальный алгоритм решения задачи ком-

пактного суммирования векторов, возникающей при решении задач теории расписаний в классических постановках. Показана полиномиальная разрешимость NP-трудной задачи "Open Shop", то есть возможность найти оптимальное решение для почти всех входов этой задачи. Обнаружены новые свойства перестановочных расписаний моделей сборочной линии и "Flow Shop".

Апробация. Результаты диссертации были представлены на международных конференциях и симпозиумах, в частности, на Втором международном симпозиуме по стохастическим алгоритмам — SAGA'03 (Хэтфилд, Великобритания, 2003), международной конференции по дискретному анализу и исследованию операций — DAOR'2004 (Новосибирск, 2004), международной конференции по исследованию операций — OR'2004 (Тилбург, Нидерланды, 2004).

Публикации. Основные результаты диссертации опубликованы в работах [1]-[6], из них: 1 статья в центральном журнале из перечня ВАК РФ, 2 статьи в зарубежных сборниках, 1 препринт.

Структура и объём работы. Диссертационная работа состоит из введения, трёх глав, приложения и списка литературы, включающего 58 наименований. Общий объём диссертации — 98 страниц, включая 2 рисунка и 5 таблиц.

КРАТКОЕ СОДЕРЖАНИЕ РАБОТЫ

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

Рассматриваемые в диссертации задачи теории расписаний характеризуются количеством работ п, количеством машин т, длительностями операций рг} (j = 1,... ,п\ i = 1,... ,т). Приняты обозначения для максимальной машинной нагрузки (¿max) и максимальной длительности операции (ртах)• Требуется найти расписание S = {.%}, минимизирующее функционал

CmaxiS) = max(Si; + pl})

(sy > 0 — время начала выполнения операции рг}). Для различных задач теории расписаний существуют различные ограничения, накладываемые на выполнение операций. Для всех рассматриваемых в диссертации задач теории расписаний величина /Шах является нижней оценкой оптимума.

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

Определение 1. Событие А(п) выполняется с высокой вероятностью, если

Р{Л(ж)} = 1 - о(1), п-+ оо.

Основная часть диссертации делится на три главы. В главе 1 рассматривается задача компактного суммирования векторов, к которой сводятся многие задачи теории расписаний5. Пусть s — некоторая норма в Rd, и пусть конечное семейство векторов X = {х\,..., хп} С Rd удовлетворяет условию

п

J> = o. (1)

г=1

' Fi'H'7'1 А М . Reed В Probabilistic Analysts of Algorithms 11 Probabilistic Methods for Algorithmic Diicrete Mathematics Springer, 1998 P 36-92

^Sevabtianov S V On Some Geometric Methods m Scheduling Theory a Survey '/ Discrete Appl Math. 1994. №55. P 59 82.

Требуется решить следующую задачу минимизации:

Таким образом, задача компактного суммирования векторов Х\,... ,хп заключается в отыскании такого порядка их суммирования, чтобы все частичные суммы оставались в пределах шара (в норме в) минимально возможного радиуса.

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

= (Р2, ~ Р13,Рз3 ~ Р13, ■ ■ ■ I Ртз ~ Р\3) € Шт'\

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

a) рг* >Рг3 {г = 1, • • • ,го; з = 1,... ,п);

b) р * < Ртах (» = 1,... ,т; 3 = 1.....п);

c) Е"=1 Рг* = ¿тах (« = 1, - . - , ш).

В результате процедуры выравнивания векторы е3 преобразуются в векторы

которые обладают свойством "YT3=\ е* — Чем точнее оценка радиуса компактного суммирования векторов {е*}, тем точнее оценка длины расписания для задачи теории расписаний с длительностями операций р* Эта оценка остаётся в силе и для рп; сохраняется также и допустимость расписания для исходной задачи.

'Sevastianov S V. Vector Summation in Bnnach Space and Polynomial Algorithms /or Flow Shops and Open Shops // Math, of Oper. Res. 1995. A' 20 P. 90 103.

к

в

e*j = {p\, - p\vp% -p\v • • • ,Pm, -p\3) e r-\

В главе 1 диссертации предлагается два алгоритма: алгоритм Л\ 2, осуществляющий процедуру выравнивания, и алгоритм осуществляющий компактное суммирование векторов семейства Е* = {е*}"=1 в норме ё, определяемой соотношением

шах

< тах |ж(г)|, тах |ж(г) — х{1) \ > , I г г,] J

где х({) — г-я координата вектора х. В результате вероятностного анализа алгоритмов А\.ч, Л\ з был выявлен класс распределений обладающий следующими свойствами.

I. {рг]} (г = 1,..., т; 3 = 1,..., п) — независимые одинаково распределённые случайные величины с невырожденным абсолютно непрерывным распределением Р.

II. Закон распределения Р таков, что при п —► оо

где /(п) — правильно меняющаяся функция порядка к > 2. Определение и основные свойства правильно меняющихся функций содержатся в приложении диссертации. Основным результатом главы 1 является следующая

Теорема 1.2 Пусть матрица Р = (ргз) размера т х п состоит из неотрицательных случайных величин {рг]}. удовлетворяющих условиям I—II. Тогда

1) существует алгоритм Л\ 2, который при фиксированном тип—* оо с высокой вероятностью выполняет процедуру

2(Р,Р*У,

2) существует алгоритм Л\ з; который при фиксированном т ип —у оо с высокой вероятностью находит такой порядок 7г суммирования векторов из семейства Е*. что

к

тах

к=1,. ,,п

XX

.7=1

^х ||е;||4 + о(1).

А г=\,. ,п

Временнйе сложности алгоритмов Л\ 2 и Л\.з не превышают 0(п2т2).

Величина етах/2 (где еШах = тахг=1)...!„ ||е*||з) — половина максимальной нормы вектора — является нижней оценкой оптимума задачи компактного суммирования векторов. Таким образом, при заданных ограничениях на распределения входных данных теорема 1.2 даёт полиномиальный алгоритм решения этой NP-тpyднoй задачи, причём полученное решение с высокой вероятностью отличается от оптимума не более, чем на величину о(1), не зависящую от етах-

Построение алгоритма Л\ 2 (раздел 1.3) и доказательство теоремы 1.2 (раздел 1 4) основаны на главной идее алгоритма (раздел 1 3), которая заключается в следующем. Векторы е* делятся на большие (норма которых не меньше определённой величины) и малые (все остальные). Суммирование строится так, чтобы каждый из больших векторов попадал своей серединой в начало координат или в некоторую его окрестность, ограниченную шаром радиуса Я\ = о(1). В этом случае все большие векторы оказываются в пределах шара радиуса етах/2 4- Я,\. Совпадение траектории суммирование с началом очередного проходящего через середину большого вектора обеспечивается за счёт малых векторов, добавляемых к концу только что просуммированого. В ходе доказательства теоремы 1.2 показывается, что с высокой вероятностью количества малых векторов достаточно для заполнения всех промежутков между большими векторами. Более того, даже после того, как все большие векторы будут просуммированы, останется некоторое количество малых векторов. Эти малые векторы суммируются известным алгоритмом С. В. Севастьянова7 в пределах радиуса /?2+-Й1, причём с высокой вероятностью < етах/2.

В разделе 1.5 главы 1 результат теоремы 1.2 применяется

'Севастьянов С В О компактном суммировании векторов // Дискр мат 1991 Т 3, № 3

С. 66 72

к следующим задачам на построение кратчайших расписаний для многостадийных систем: "Open Shop", "Flow Shop", "Job Shop", задача о сборочной линии. Все перечисленные задачи являются jVP-трудными. Известные ранее алгоритмы решения этих задач модифицируются путём замены в них процедур выравнивания и компактного суммирования векторов из Е* на алгоритмы А\ц и Л 1.3 соответственно (в результате чего получаются алгоритмы Д1.4 — А\л) При этом предполагается, что распределения входных данных удовлетворяют условиям X—XX; результаты формулируются в терминах определения 1 при п —> оо.

Для задачи "Open Shop" получен наиболее широкий (на настоящий момент) класс полиномиально разрешимых случаев, определяемый соотношением

(теорема 1.17). Для задач о сборочной линии, "Flow Shop" и "Job Shop" получены приближённые решения со следующими гарантированными оценками точности соответственно:

Cmax(S') < ¿max + 1.5(m - l)pmax + о(1) (теорема 1.18);

Стах(5) < ¿max + 1-5?W + о(1)

(теорема 1.19);

<?max(S) < Ux + (Г - 1)(2.5Г - 1)Ршах. + о(1),

где г — максимальное число операций одной работы (теорема 1.20). Все полученные оценки являются на настоящий момент рекордными (таблицы 1.2-1.5).

Глава 2 содержит вероятностный анализ известного алгоритма Л2.1 решения задачи "Open Shop" с п работами и т машинами6. Алгоритм Ai.\ находит оптимальное решение задачи при следующем условии на входные данные:

/шах > (2.5т - 2)pmax + о( 1)

(2)

^max ^ WI Ртах-12

Таким образом, во второй главе решается задача определения класса распределений входных данных, для которого условие (3) выполняется с высокой вероятностью. В качестве характеристик, определяющих класс распределений входных данных, выступают математические ожидания длительностей операций (/%), а также величины Ьгз = (Щрг] — (для некоторого г > 1). Кроме того,

Выявленный класс распределений ргз определяется следующими условиями.

{В\)Все случайные величины имеют невырожденные распределения, и для некоторого г > 1 существуют моменты бу .

(В2) Для каждого г = 1,2,... ,т выполнены асимптотические соотношения (п —► оо):

Условия (В\)-(В2) гораздо шире, чем условия I—II из главы 1, и не исключают случай различных распределений входных данных. Поэтому в главе 2 анализируется условие (3), достаточное для всех возможных входов задачи "Open Shop", а не более слабое условие (2), достаточное с высокой вероятностью лишь для одинаково распределённых исходных длительностей операций, удовлетворяющих условиям I—II. Результатом вероятностного анализа алгоритма А2.1 явилась следующая

Теорема 2.1 Для стохастического задачи "Open Shop" с возрастающим числом работ п, фиксированным числом машин тис длительностями операций, удовлетворяющим

Вгп = о (An), п ■ max Еf = о (Аггп).

условиям (В[) — (£2), алгоритм Д2.1 с. высокой вероятностью строит оптимальное расписание длины, равной максимальной машинной нагрузке.

В главе 2 также приводится вытекающее из условий (В\) — (В^), легко проверяемое условие (Вз) и соответствующее этому условию следствие.

(Вз) На машине Мг (i = 1,... ,т) длительности операций являются независимым,и одгтаково распределёнными невырожденными случайными величгтамгь с мат,ематическим ожиданием дг и дисперсией а2 < оо.

Следствие 2.2 Для стохастической задачи "Open Shop" с возрастающим чгилом работ п. фиксированным числом машин тис длительностями операций, удовлетворяющим условию (Вз). алгоритм А21 с высокой вероятностью строит оптимальное расписание длины,, равной максимальной машинной нагрузке.

В главе 3 рассматриваются задачи о сборочной линии и "Flow Shop" и исследуются асимптотические свойства перестановочных расписаний для этих задач. Перестановочные расписания характеризуются тем, что порядок выполнения работ на каждой машине один и тот же. Интересен тот факт, что известные ранее алгоритмы приближённого решения этих задач на выходе дают именно перестановочные расписания. Сами по себе эти алгоритмы нетривиальны и имеют трудоёмкость 0(т2п2).

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

целевой функции на выдаваемом им решении с высокой вероятностью удовлетворяет соотношению

Cmax(S)-OPT ОРТ

при любом € > 0 (Определение 2), где ОРТ — оптимум задачи.

В результате вероятностного анализа алгоритма Аз i выявлен следующий класс распределений входных данных.

(Р) {рг] > 0 | г = 1,..., т; j = 1,..., п} — независимые одинаково распределённые невырожденные случайные, величины с конечной дисперсией с2 < оо.

В теореме 3.1 показана асимптотическая оптимальность алгоритма А31 для задачи "Flow Shop" с распределениями исходных длительностей операций, удовлетворяющими (Р).

Теорема 3.1 Для стохастической задачи "Flow Shop" с т машинами, п работами и длительностями операций, удовлетворяющими условию (Р) расписание S, построенное алгоритмом A31, с высокой вероятностью является асимптотически оптимальным, а длина этого расписания Cmax{S) с высокой вероятностью удовлетворяет следующей оценке:

Cmax(S) < (т - 1)Ртах + + /тах'

Задача "Flow Shop" неоднократно рассматривалась в различных стохастических постановках и с различными целевыми функциями. Исследование стохастической задачи "Flow Shop" на построение кратчайшего расписания в терминах определения 1 проводится впервые.

В теореме 3.2 доказывается аналогичный результат для задачи о сборочной линии с оценкой длины полученного алгоритмом A31 расписания

Cmax('S') < Ртах + + ^тах-

Задача о сборочной линии рассмотрена и исследована в стохастической постановке впервые.

В приложении диссертации приводятся используемые при доказательствах результатов определение и свойства правильно меняющихся функций (I), а также неравенства симметризации (II) и Леви (III).

Публикации по теме диссертации

[1] Корякин Р.А., Севастьянов С.В. О стохастической задаче компактного суммирования векторов // Дискретный анализ и исследование операций. - 2005. - Т. 12, № 1. -С. 71-100.

[2] Корякин Р.А., Севастьянов С.В. О стохастической задаче компактного суммирования векторов. - Новосибирск: Изд-во Ин-та математики, 2004. - 30 с.

[3] Koryakin R.A. On Asymptotic Optimality of Permutation Schedules in Stochastic FIovj Shops and Assembly Lines // Operation Research Proceedings 2004. - Springer, 2005. - P. 200-206.

[4] Koryakin R.A. On Asymptotic Optimality of Permutation Schedules in Stochastic Flov) Shops and Assembly Lines // International Conference on Operation Research (OR2004).

- Tilburg, 2004. - P. 100.

[5] Koryakin R.A., Sevastyanov S.V. On the Compact Vector Summation in Stochastic Machine Scheduling // Материалы международной конференции "Дискретный анализ и исследование операций (DAOR2004). - Новосибирск, 2002. - С. 172.

[6] Koryakin R.A. On the Stochastic Open Shop Problem // Lect. Notes in Сотр. Science. - Springer, 2003. - Vol. 2827.

- P. 117-124.

Корякин Роман Александрович

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

Автореферат диссертации на соискание учёной степени кандидата физико-математических наук

Подписано в печать 04.07.2005. Формат 60x84 1/16. Усл. печ. л. 1. Заказ N 273. Тираж 100 экз.

С --—-

к

Отпечатано в ИПЦ "Юпитер" 630501, НСО, п. Краснообск

я

* i

»14647

РНБ Русский фонд

2006-4 15739

Введение

Общая характеристика работы.

Главные результаты диссертации.

Публикации и апробация результатов исследований

Структура работы.

1 Компактное суммирование векторов

1.1 Предварительные сведения.

1.2 Формулировки результатов.

1.3 Алгоритмы Л1.2, Л1.3.

§ 1.3.1 Необходимые обозначения.

§ 1.3.2 Описание алгоритма Л\.2.

§ 1.3.3 Описание алгоритма И.1.3.

1.4 Доказательство теоремы 1.2.

§ 1.4.1 Процедура выравнивания.

§ 1.4.2 Суммирование больших векторов.

§ 1.4.3 Оценка радиуса суммирования.

§ 1.4.4 Асимптотическая оптимальность.

§ 1.4.5 Вспомогательные доказательства.

Общая характеристика работы и обзор результатов диссертации

В диссертации рассматриваются задачи, относящиеся к классическим многостадийным моделям теории расписаний. Задачи теории расписаний появляются там, где необходимо упорядочить некоторый процесс в рамках заданных ограничений (т.е. составить допустимое расписание для выполнения этого процесса), с тем чтобы полученное расписание было оптимальным по тем или иным критериям. В настоящее время исследуется множество разнообразных моделей теории расписаний (см., например, обзор [28]), хотя подавляющее большинство этих моделей описывают весьма далекие от реальных условий "идеальные" ситуации. Тем не менее, в течение последних 20 и более лет теория расписаний бурно развивается, и в её рамках создаётся множество практических приложений для оптимизации реальных процессов.

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

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

С учётом вышесказанного, общая задача теории расписаний, включающая в себя формулировки всех рассматриваемых в диссертации задач2, формулируется следующим образом. Работы Ji,., Jn выполняются на машинах Mi,.,Mm. Каждая работа Jj (j = 1 ,.,п) состоит из т операций oij,., omj. Операция Оц (г = 1,., m; j = 1,., п) выполняется на машине Mi в течение времени рц > 0. На процесс выполнения операций накладываются определённые ограничения (свои для каждой i конкретной модели), определяющие множество допустимых расписаний. Пусть Sij G R+ обозначает время начала выполнения операции Oij. Требуется найти расписание S = {s^-1 i = 1,., га; j = 1,., п}, удовлетворяющее заданным ограничениям на выполнение операций и минимизирующее время CmeLX(S) выполнения всех операций:

Cmax(S) = max(Sy + Pij). (1) bj

В диссертации рассматриваются задачи для трёх базовых моделей: сборочная линия, Job Shop и Open Shop, а также важный частный случай модели Job Shop, обозначаемый Flow Shop. Общими для всех рассматминов.

2за исключением задачи Job Shop, полная формулировка которой приведена в § 1.5.4. риваемых задач являются следующие два ограничения на выполнение операций:

L\) не допускаются прерывания операций;

L2) никакие две операции не могут выполняться одновременно на одной машине.

Выполнение операций в задачах Job Shop и Open Shop помимо условий (Li)-(L2) ограничивается ещё одним условием:

L3) никакие две операции одной работы не могут выполняться одновременно.

Все четыре перечисленные задачи теории расписаний в общем случае являются Л/'Р-трудными, в связи с чем возникло два направления их исследования. Первое направление — разработка полиномиальных приближённых алгоритмов, которые находят некоторое не обязательно оптимальное расписание, но длина которого гарантированно ограничена некоторой верхней оценкой, близкой к нижней оценке оптимума. Второе направление — это поиск полиномиально разрешимых классов задачи, то есть, таких бесконечных подмножеств примеров исходной задачи, для которых существует алгоритм, находящий оптимальное решение задачи за полиномиальное время. В обоих направлениях рассматриваемые классические многостадийные задачи теории расписаний исследованы довольно глубоко (в детерминистской постановке), о чём свидетельствует, например, уже упомянутый обзор [28]. Действительно, на настоящий момент уже найден достаточно широкий полиномиально разрешимый класс задачи Open Shop, а для задач о сборочной линии, Job Shop и Flow Shop построены эффективные приближённые алгоритмы с гарантированными оценками точности решения. Заметим, что все результаты для задач в детерминистской постановке связаны с исследованием поведения алгоритма в так называемых худших случаях, то есть, выводятся оценки поведения алгоритма (его трудоёмкости, точности, требуемой памяти, и т. п.), справедливые для всех без исключения примеров рассматриваемой задачи.

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

На этот вопрос было бы легче ответить, если бы общее количество возможных входов задачи было в каком-то смысле ограничено. Например, если известно, что все длительности операций могут принимать значения из интервала [0, х], а полиномиально разрешимый класс определяется совокупностью входов, когда хотя бы одна из (тп) длительностей операций превышает величину х/2, то мы можем сказать, что доля худших случаев составляет 1/2тп-ю часть всех возможных входов задачи.

Но дело в том, что большинство рассматриваемых задач в детерминированных постановках не так просты: в них длительности операций предполагаются любыми числами из интервала [0; со). Такое предположение о диапазоне значений длительностей операций является наиболее общим и, конечно, исключает возможность ответа на поставленный выше вопрос. В реальных же практических задачах этот диапазон значительно сужается: обычно существуют заранее известные границы, в пределах которых скорее всего и окажется значение длительности конкретной операции. Любая дополнительная информация всегда полезна, и хотелось бы её использовать, но проблема в том, что детерминистская постановка не приемлет формулировок в терминах "скорее всего" в силу их неточности. Как только длительность хотя бы одной операции выходит за эти границы, в рамках детерминистской постановки мы вынуждены их расширять. Хотя именно такие длительности, как правило, определяют худшие случаи для конкретной задачи, и очень часто их относительно немного, по сравнению с типичными случаями (т.е., попадающими в упомянутые границы).

Поэтому, если мы хотим каким-то образом ответить на поставленный вопрос о доле худших случаев среди всех возможных входов задачи, мы вынуждены отказаться от детерминированной постановки и обратиться к стохастической, т.е. решать задачу в предположении, что все длительности операций суть некоторым образом распределённые случайные величины. Но если ясно, что значит "решить задачу в детерминистской постановке" (в нашем случае это "найти такое решение, которое минимизирует функционал (1)" ), то, на первый взгляд, не совсем ясно, что значит решить задачу в стохастической постановке: ведь в этом случае сам функционал (1) становится случайной величиной.

В течение более чем сорока лет исследований сформировалось несколько подходов к рассмотрению стохастических задач дискретной оптимизации (куда входят и задачи теории расписаний), один из которых и используется в диссертации. Впервые задача дискретной оптимизации в стохастической постановке (а именно, известная задача коммивояжера) была рассмотрена A.A. Боровковым в 1962 г. [2]. В работе был построен алгоритм, находящей такое решение, на котором целевая функция задачи удовлетворяла некоторым нижней и верхней оценкам "почти всегда" при п —► оо. При этом под термином "почти всегда" понималась близкая к единице веорятность того, что обе эти оценки верны. Следуя подходу A.A. Боровкова, в 1969 г. [11] В.А. Перепелица и Э.Х. Гимади впервые дали формальное определение асимптотически точного алгоритма, которое буквально заключается в следующем. Пусть рассматривается задача на минимум целевой функции Z, Z*(I) — оптимальное значение функции Z для входа /, а алгоритм А находит для этого входа решение со значением Za(I). Тогда алгоритм А называется асимптотически точным (при п —оо, где п — некоторый параметр задачи), если существуют такие неотрицательные величины еп и 6п, что

HZa(I) < (1 + £n)Z*(I)) > 1 -6п, lim £n = 0, lim Sn = 0. (2) п—юо n—>oо

В последующие годы асимптотически точные алгоритмы были построены для многих задач дискретной оптимизации (см., например [5], [б], [29], [41]). Определение понятий, связанных с понятием асимптотически точных алгоритмов, можно найти в обзоре Э.Х. Гимади, Н.И. Глебова и В.А. Перепелицы [4]. Из западной литературы стоит выделить обзоры J1. Сломински [47], а также Б. Рида и А. Фриза [34]. Б. Рид и А. Фриз обобщают понятие асимптотически точного алгоритма. Ведь выражение под знаком вероятности в (2) — это, вообще говоря, некоторое событие, зависящее от п. Если при этом вероятность наступления такого события стремится к единице с ростом п, то, согласно терминологии Рида и Фриза, оно происходит с высокой вероятностью (см. определение 1 ниже). Таким образом, асимптотически точный алгоритм есть не что иное, как алгоритм, находящий такое решение для данной задачи, которое с высокой вероятностью близко к оптимуму. Именно этот подход к решению задач в стохастических постановках используется в диссертации. Строя алгоритмы решения различных задач теории расписаний, мы устанавливаем свойства полученных с их помощью расписаний, справедливые с высокой вероятностью.

Хотелось бы также сказать несколько слов о других существующих подходах к решению стохастических задач, подчеркнуть их отличия от уже рассмотренного. Один из таких подходов заключается в том, чтобы минимизировать математическое ожидание целевой функции, являющейся случайной величиной. Например, в [36] содержится детальный обзор исследований стохастической задачи Flow Shop, в которой целевой функцией является математическое ожидание длины расписания (т.е., математическое ожидание функционала (1)). Заметим, что минимизация математического ожидания длины расписания мало что говорит нам о фактической длине расписания. Легко привести пример распределения случайной величины, такой что вероятность превышения ею своего математического ожидания в два раза равна некоторому значению а из интервала (0,1). Таким образом, нахождение некоторого расписания математическое ожидание длины которого минимально или близко к минимуму в классе всех допустимых расписаний задачи, не гарантирует нам никакой верхней оценки этой длины. Более того, может существовать расписание ¿2, математическое ожидание длины которого больше, чем у расписания 51, но для длины которого существует верхняя оценка, имеющая место с вероятностью 1 и которую длина расписания превышает с ненулевой вероятностью. В этом смысле расписание ¿>2 предпочтительнее. Но как уже замечалось выше, когда шла речь о подходах к исследованию ЛЛР-трудных задач теории расписаний, актуальны две ситуации: либо когда выделяется класс полиномиально разрешимых случаев, либо когда находится приближённое решение с верхней оценкой длины расписания. Поэтому предпочтительнее было бы в качестве приближённого решения иметь всё-таки расписание а не б'х, являющееся продуктом минимизации длины математического ожидания.

Ещё один существующий подход к постановке и решению стохастических задач заключается в минимизации целевой функции в смысле стохастического порядка. Случайная величина X стохастически меньше, чем случайная величина У, если для любого £

Р(Х > «) < Р(У > Ь).

В рамках этого подхода находится расписание, длина которого стохастически минимальна или близка к стохастическому минимуму в классе допустимых расписаний задачи. К сожалению, такой подход не даёт непосредственного инструмента для получения верхних оценок погрешности алгоритма. Можно лишь гарантировать, что оценка длины, справедливая для некоторого расписания, будет верна и для расписания стохастически минимальной длины. Примеры использования описанного подхода (в применении к стохастической задаче Flow Shop) можно найти в [33], [38], [42]. * *

Итак, к решению стохастических задач теории расписаний мы применяем первый из описанных подходов и используем при этом следующее определение К. Рида и А. Фриза [34].

Определение 1. Событие А(х) выполняется с высокой вероятностью, если

Р{Л(ж)} = 1 - о(1), х —> оо.

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

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

Именно этот подход используется в главе 2 диссетрации, в которой мы рассматриваем алгоритм решения задачи Open Shop, разработанный C.B. Севастьяновым в [45], и проводим его вероятностный анализ. Этот алгоритм строит допустимое оптимальное расписание для задачи Open Shop при определённых условиях на исходные длительности операций. Мы выявляем довольно широкий класс распределений исходных длительностей операций, для которых эти условия выполняются с высокой вероятностью, и следовательно, с высокой вероятностью для задачи Open Shop может быть эффективно построено оптимальное расписание.

Второй подход имеет более сложную природу: он заключается в том, что для конкретной задачи строится алгоритм, все или почти все шаги которого могут быть выполнены не всегда, но при определённых условиях на входные данные, причём для разных шагов эти условия могут быть разными. Если в рамках первого подхода невыполнение условий на входные данные могло привести всего лишь к построению недопустимого расписания (алгоритм выдаст результат в любом случае), то в рамках второго при невыполнении условий хотя бы на одном шаге алгоритм выдаст ошибку. Однако если все условия выполнены, то решение автоматически получается допустимым, именно с таким расчётом и строится алгоритм. Задача вероятностного анализа в рамках этого подхода заключается в выявлении такого класса распределений исходных длительностей операций, для которого все условия, от которых зависит правильное выполнение всех шагов алгоритма, выполняются с высокой вероятностью. Ещё раз подчеркнём разницу между первым и вторым подходом: в первом случае мы анализируем выход алгоритма, т.е. будет ли выдаваемое алгоритмом решение допустимым для данной задачи или нет, а во втором случае — сам алгоритм и выдаст ли он какое-либо решение вообще.

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

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

В главе 3 мы применяем этот подход к двум стохастическим задачам: задаче о сборочной линии и Flow Shop, — и исследуем класс перестановочных расписаний, т.е. таких расписаний, в которых все работы выполняются на каждой машине в одном и том же порядке. Оказывается, что для достаточно широкого класса распределений исходных длительностей операций отношение длины перестановочного расписания к оптимуму с высокой вероятностью стремится к единице. Рассмотрение класса перестановочных расписаний обусловлено тем, что для задачи о сборочной линии оптимальное расписание совпадает с оптимальным перестановочным расписанием [43], а для задачи Flow Shop все известные эффективные приближённые алгоритмы строят также перестановочные расписания.

Главные результаты диссертации

• Построен алгоритм, который с высокой вероятностью находит приближённое решение частного случая стохастической задачи компактного суммирования векторов для широкого класса распределений координат исходных векторов. Радиус суммирования отличается от минимально возможного (половины максимальной нормы вектора) не более, чем на исчезающе малую (с ростом количества векторов) величину. Трудоёмкость алгоритма не превышает 0(т2п2).

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

• Выявлен широкий класс распределений входных данных стохастической задачи Open Shop, для которых с высокой вероятностью может быть построено оптимальное расписание за время 0(т2п2). В рамках данного класса длительности различных операций могут иметь, вообще говоря, различные распределения.

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

Публикации и апробация результатов исследований

Диссертант является автором 5 научных работ. По теме диссертации опубликовано 5 работ, в том числе: 1 — в международных изданиях,

1 — в журнале "Дискретный анализ и исследование операций",

1 — в препринтах Института математики СО РАН им. С.Л. Соболева,

2 — в тезисах конференций.

Результаты диссертанта по теме диссертации опубликованы в работах [53]-[57].

Результаты, представленные в диссертации, докладывались автором:

• на Втором международном симпозиуме по стохастическим алгоритмам — БАСА'ОЗ (Хэтфилд, Великобритания, 2003);

• на международной конференции по дискретному анализу и исследованию операций — БА011'2004 (Новосибирск, 2004);

• на международной конференции по исследованию операций — ОЫ'2004 (Тилбург, Нидерланды, 2004).

Структура работы

Диссертация состоит из введения, трёх глав и приложения. Каждая глава состоит из нескольких разделов, некоторые разделы в свою очередь состоят из параграфов. Первый раздел каждой главы содержит предварительные сведения, последний — заключительные замечания и открытые вопросы.

1. БЕЛОВ И.е., Столин Я.С. Алгоритм в одномаршрутной задаче календарного планирования // Математическая экономика и функциональный анализ. - М.: Наука, 1974. - С. 248-257.

2. БОРОВКОВ A.A. К вероятностной постановке двух экономических задач // ДАН СССР 1962.- т. 146, вып. 5. - С. 983-986.

3. Боровков A.A. Теория вероятностей / М.: "Эдиториал УРСС", 1999. 472 С.

4. Гимади Э.Х., Глебов Н.И., Перепелица В.А. Алгоритмы с оценками для задач дискретной оптимизации // Проблемы кибернетики. 1975. - №1. - С. 35-42.

5. ГИМАДИ Э.Х. О некоторых математических моделях и методах планирования крупно-масштабных проектов // Труды Ин-та математики. Модели и методы оптимизации. 1988. - № 10. - С. 89-115.

6. ДУШИН Б.И. Замечание об алгоритме для одномаршрутной задачи Джонсона // Кибернетика. 1980. - №2. - С. 129-131.

7. ИБРАГИМОВ А.И., Линник Ю.В. Независимые и стационарно связанные величины / М.: Наука, 1965. 524 С.

8. КАДЕЦ М.И. Об одном свойстве векторных ломаных в п-мерном пространстве // Успехи мат. наук. 1953. - № 8. - С. 139-143.

9. Перепелица В.А., Гимади Э.Х. К задаче нахождения минимального гамильтонова контура на графе со взвешенными дугами // Дискретный анализ. 1969. - № 15. - С. 7-65.

10. СЕВАСТЬЯНОВ C.B. Об асимптотическом подходе к некоторым задачам теории расписаний // Управляемые сисетмы. 1975. - № 14.- С. 40-51.

11. Севастьянов C.B. О приближённом решении некоторых задач теории расписаний // Методы дискретного анализа. 1978. - № 32.- С. 66-75.

12. СЕВАСТЬЯНОВ C.B. Приближённые алгоритмы в задачах Джонсона и суммированяи векторов // Управляемые системы. 1980. - № 20. - С. 64-73.

13. Севастьянов C.B. О компактном суммировании векторов // Дискр. мат. 1991. - Т. 3, № 3. - С. 66-72.

14. Ширяев А.Н. Вероятность / М.: Наука, 1980. 575 С.

15. BANASZCZYK W. The Steinitz Constant of the Plane //J. Reine Angew. Math. 1987. - Vol. 373. - P. 218-220.

16. BARÄNY I. A Vector-sum Theorem and its Application to Improving Flow Shop Guarantees // Math. Oper. Res. 1981. - No. 6. - P. 445452.

17. Chen, B., Potts, C.N., Woeginger, G.J. A Review of Machine Scheduling: Complexity, Algorithms and Approximability // Handbook of Combinatorial Optimization. Boston, MA: Kluwer Acad. Publ., 1998. - Vol. 3. - P. 21-169.

18. Coffman E.G.,Jr., Lueker G.S., Rinnooy Kan A.H.G. Asymptotic Methods in the Probabilistic Analysys of Sequencing and Packing Heuristics // Management Science. 1988. - Vol. 34. - P. 266290.

19. Danil'chenko A.M., Levchenko S.N., Panisev A.V. An Approximate Algorithm for the Three-Machine Problem // Automat. Remote Control. 1985. - Vol. 46. - P. 896-902.

20. FlALA T. Near Optimal Algorithm for the Three Machine Problem // Alkamaz. Mat. Lapok. 1977. - No. 3. - P. 389-398 (Hungarian).

21. FlALA T. An Algorithm for the Open-Shop Problem // Math. Oper. Res. 1983. - No. 8. - P. 100-109.

22. Gonzalez T., Sahni S. Open Shop Scheduling to Minimize Finish Time // J. ACM. 1976. - Vol. 23. - P. 665-679.

23. Gourgand M., Grangeon N., Norre S. A Review of the Static Stochastic Flow Shop Scheduling Problem // Journ. of Decision Systems.- 2000. No. 9. - P. 183-214.

24. Gross W. Bedingt konvergente Reihen // Monatsch. Math. Phys. -1917. Vol. 28. - P. 221-237.

25. Lee C.-Y., Cheng T.C.E., Lin B.M.T. Minimizing the Makespan in the 3-machine Assembly-type Flowshop Scheduling Problem // Management Science. 1993. - Vol. 39. - P. 616-625.

26. PlERSMA N. A probabilistic analysis of the capacitated facility location problem // J. Comb. Optim. 1999. - No. 3. - P. 31-50.

27. PlNEDO M. Minimizing the Expected Makespan in Stochastic Flow Shops // Oper. Res. 1982. - Vol. 30. - P. 148-162.

28. Potts C.N., Sevast'janov S.V., Strusevich V.A., Van Wassenhove L.N., Zvaneveld C.M. The Two Stage Assembly Scheduling Problem: Complexity and Approximation // Oper. Res. -1995. Vol. 43. - P. 346-355.

29. Sevastianov S.V. On Some Geometric Methods in Scheduling Theory: a Survey // Discrete Appl. Math. 1994. - Vol. 55. - P. 59-82.

30. SLOMINSKI L. Probabilistic Analysis of Combinatorial Algorithms: A Bibliography with Selected Annotations // Computing. 1982. - Vol. 28. - P. 257-267.

31. STEINITZ E. Bedingt konvergente Reihen und convexe Systeme // J. Reine Angew. Math. 1913. - Vol. 143. - P. 128-175.

32. SviRIDENKO M.I. A Note on Permutation Flow Shop Problem // Annals of Oper. Res. 2004. - Vol. 129. - P. 247-252.

33. Williamson, D.P., Hall, L.A., Hoogeveen, J.A., Hurkens, C.A.J., Lenstra, J.K., Sevastianov, S.V., Shmoys, D.B. Short shop schedules // Oper.Res. 1997. - Vol. 45, No. 2. - P. 288-294.

34. Xia C.H., Shanhikumar J.G., Glynn P.W. On the Asymptotic Optimality of the SPT Rule for the Flow Shop Average Completion Time Problem // Oper. Res. 2000. - Vol. 48. - P. 615-622.

35. Yurinsky V. Sums and Gaussian Vectors // Lecture Notes in Math. -Springer, 1995. Vol. 1617.Публикации автора

36. KORYAKIN R.A. On the Stochastic Open Shop Problem // Stochastic Algorithms: Foundations and Applications // Lect. Notes in Сотр. Science. Springer, 2003. - Vol. 2827. - P. 117-124

37. Корякин P.А., Севастьянов С.В. О стохастической задаче компактного суммирования векторов // Препринт N® 149. Новосибирск: Изд-во Ин-та математики, 2004. - 30 С.