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

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

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

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

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

С учётом вышесказанного, общая задача теории расписаний, включающая в себя формулировки всех рассматриваемых в диссертации задач2, формулируется следующим образом. Работы Ji,., Jn выполняются на машинах Mi,., Mm. Каждая работа Jj (j = 1 ,., п) состоит из т операций oij,., omj. Операция Оц (г = 1,., mj = 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, то мы можем сказать, что доля худших случаев составляет ½тп-ю часть всех возможных входов задачи.

Но дело в том, что большинство рассматриваемых задач в детерминированных постановках не так просты: в них длительности операций предполагаются любыми числами из интервала [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. BARANY I. A Vector-sum Theorem and its Application to Improving Flow Shop Guarantees // Math. Oper. Res. 1981. — No. 6. — P. 445 452.

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. 266 290.

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 С.