Содержание к диссертации
Введение
1 Компактное суммирование векторов 19
1.1 Предварительные сведения 19
1.2 Формулировки результатов 23
1.3 Алгоритмы Лі.2, Ai.z 27
1.3.1 Необходимые обозначения 27
1.3.2 Описание алгоритма Л\.2 28
1.3.3 Описание алгоритма Ai.z 29
1.4 Доказательство теоремы 33
1.4.1 Процедура выравнивания 33
1.4.2 Суммирование больших векторов 35
1.4.3 Оценка радиуса суммирования 38
1.4.4 Асимптотическая оптимальность 40
1.4.5 Вспомогательные доказательства 49
1.5 Приложения для стохастических задач теории расписаний 60
1.5.1 Задача Open Shop 60
1.5.2 Задача Flow Shop 62
1.5.3 Задача о сборочной линии 63
1.5.4 Задача Job Shop 64
1.6 Заключительные замечания к главе 1 65
2 Достаточные условия полиномиальной разрешимости за дачи Open Shop 69
2.1 Предварительные сведения 69
2.2 Описание алгоритма Лг.і 70
2.3 Формулировки результатов 73
2.4 Доказательства 76
2.5 Заключительные замечания к главе 2 78
3 Произвольные перестановочные расписания в задачах о сборочной линии и Flow Shop 80
3.1 Предварительные сведения 80
3.2 Формулировки результатов 82
3.3 Доказательства 84
3.4 Заключительные замечания к главе 3 87
Приложение 89
Литература 91
- Доказательство теоремы
- Приложения для стохастических задач теории расписаний
- Формулировки результатов
- Формулировки результатов
Введение к работе
Общая характеристика работы и обзор результатов диссертации
В диссертации рассматриваются задачи, относящиеся к классическим многостадийным моделям теории расписаний. Задачи теории расписаний появляются там, где необходимо упорядочить некоторый процесс в рамках заданных ограничений (т.е. составить допустимое расписание для выполнения этого процесса), с тем чтобы полученное расписание было оптимальным по тем или иным критериям. В настоящее время исследуется множество разнообразных моделей теории расписаний (см., например, обзор [28]), хотя подавляющее большинство этих моделей описывают весьма далекие от реальных условий "идеальные" ситуации. Тем не менее, в течение последних 20 и более лет теория расписаний бурно развивается, и в её рамках создаётся множество практических приложений для оптимизации реальных процессов.
Многостадийные системы теории расписаний в некотором упрощенном обобщении характеризуются наличием множества работ, которые необходимо выполнить на данном множестве машин1. Каждая работа
1 Также вместо слов "работа-машина" используются термины "деталь-станок" или "требование-прибор". В данной диссертации автор ограничивается использованием более привычных ему тер-
состоит из операций, для каждой из которых определено подмножество машин, способных выполнить эту операцию. Длительность выполнения каждой операции на данной машине может быть заданной и известной заранее: в этом случае мы будем называть постановку задачи детерминистской. Если же эта информация заранее не известна, то длительности операций предполагаются случайными величинами, о распределении которых, возможно, что-то известно. Такие постановки мы будем называть стохастическими.
С учётом вышесказанного, общая задача теории расписаний, включающая в себя формулировки всех рассматриваемых в диссертации задач2, формулируется следующим образом. Работы Ji,..., Jn выполняются на машинах М\,... ,Мт. Каждая работа Jj (j = 1,..., п) состоит из т операций oij,..., omj. Операция Oij (і = 1,..., га; j = 1,..., n) выполняется на машине Мі в течение времени рц > 0. На процесе выполнения операций накладываются определённые ограничения (свои для каждой конкретной модели), определяющие множество допустимых расписаний. Пусть Sij Є R+ обозначает время начала выполнения операции (. Требуется найти расписание S = {s^ \ і = 1,..., га; j = 1,..., п}, удовлетворяющее заданным ограничениям на выполнение операций и минимизирующее время Cmax(S) выполнения всех операций:
Cmax{S) = max(sy + pi5). (1)
В диссертации рассматриваются задачи для трёх базовых моделей: сборочная линия, Job Shop и Open Shop, а также важный частный случай модели Job Shop, обозначаемый Flow Shop. Общими для всех рассмат-
минов.
2за исключением задачи Job Shop, полная формулировка которой приведена в 1.5.4.
риваемых задач являются следующие два ограничения на выполнение операций:
(Li) не допускаются прерывания операций;
(L2) никакие две операции не могут выполняться одновременно на одной машине.
Выполнение операций в задачах Job Shop и Open Shop помимо условий {L\)-{L,2) ограничивается ещё одним условием:
(з) никакие две операции одной работы не могут выполняться одновременно.
Все четыре перечисленные задачи теории расписаний в общем случае являются Л/'Р-трудными, в связи с чем возникло два направления их исследования. Первое направление — разработка полиномиальных приближённых алгоритмов, которые находят некоторое не обязательно оптимальное расписание, но длина которого гарантированно ограничена некоторой верхней оценкой, близкой к нижней оценке оптимума. Второе направление — это поиск полиномиально разрешимых классов задачи, то есть, таких бесконечных подмножеств примеров исходной задачи, для которых существует алгоритм, находящий оптимальное решение задачи за полиномиальное время. В обоих направлениях рассматриваемые классические многостадийные задачи теории расписаний исследованы довольно глубоко (в детерминистской постановке), о чём свидетельствует, например, уже упомянутый обзор [28]. Действительно, на настоящий момент уже найден достаточно широкий полиномиально разрешимый класс задачи Open Shop, а для задач о сборочной линии, Job Shop и Flow Shop построены эффективные приближённые алгоритмы с гарантированны-
ми оценками точности решения. Заметим, что все результаты для задач в детерминистской постановке связаны с исследованием поведения алгоритма в так называемых худших случаях, то есть, выводятся оценки поведения алгоритма (его трудоёмкости, точности, требуемой памяти, и т. п.), справедливые для всех без исключения примеров рассматриваемой задачи.
В первом направлении верхние оценки исследуемых характеристик алгоритма определяется именно поведением алгоритма в худших случаях, и если такие "худшие случаи" редки, то есть надежда, что на большинстве примеров алгоритм будет иметь существенно лучшие характеристики. Во втором направлении худшие случаи, на которых алгоритм не находит оптимального расписания, попросту удаляются из рассмотрения при определении данного полиномиально разрешимого класса. Ясно, что чем меньше таких худших случаев, тем точнее верхние оценки длины расписания из первого направления исследований и тем шире полиномиально разрешимые классы из второго направления. Поэтому возникает довольно естественный вопрос: какова доля таких худших случаев среди всех возможных входов задачи?
На этот вопрос было бы легче ответить, если бы общее количество возможных входов задачи было в каком-то смысле ограничено. Например, если известно, что все длительности операций могут принимать значения из интервала [0,ж], а полиномиально разрешимый класс определяется совокупностью входов, когда хотя бы одна из (ran) длительностей операций превышает величину х/2, то мы можем сказать, что доля худших случаев составляет 1/2тп-ю часть всех возможных входов задачи.
Но дело в том, что большинство рассматриваемых задач в детерминированных постановках не так просты: в них длительности операций предполагаются любыми числами из интервала [0; со). Такое предположение о диапазоне значений длительностей операций является наиболее общим и, конечно, исключает возможность ответа на поставленный выше вопрос. В реальных же практических задачах этот диапазон значительно сужается: обычно существуют заранее известные границы, в пределах которых скорее всего и окажется значение длительности конкретной операции. Любая дополнительная информация всегда полезна, и хотелось бы её использовать, но проблема в том, что детерминистская постановка не приемлет формулировок в терминах "скорее всего" в силу их неточности. Как только длительность хотя бы одной операции выходит за эти границы, в рамках детерминистской постановки мы вынуждены их расширять. Хотя именно такие длительности, как правило, определяют худшие случаи для конкретной задачи, и очень часто их относительно немного, по сравнению с типичными случаями (т.е., попадающими в упомянутые границы).
Поэтому, если мы хотим каким-то образом ответить на поставленный вопрос о доле худших случаев среди всех возможных входов задачи, мы вынуждены отказаться от детерминированной постановки и обратиться к стохастической, т.е. решать задачу в предположении, что все длительности операций суть некоторым образом распределённые случайные величины. Но если ясно, что значит "решить задачу в детерминистской постановке" (в нашем случае это "найти такое решение, которое минимизирует функционал (1)" ), то, на первый взгляд, не совсем ясно, что
значит решить задачу в стохастической постановке: ведь в этом случае сам функционал (1) становится случайной величиной.
В течение более чем сорока лет исследований сформировалось несколько подходов к рассмотрению стохастических задач дискретной оптимизации (куда входят и задачи теории расписаний), один из которых и используется в диссертации. Впервые задача дискретной оптимизации в стохастической постановке (а именно, известная задача коммивояжера) была рассмотрена А.А. Воровковым в 1962 г. [2]. В работе был построен алгоритм, находящей такое решение, на котором целевая функция задачи удовлетворяла некоторым нижней и верхней оценкам "почти всегда" при п — со. При этом под термином "почти всегда" понималась близкая к единице веорятность того, что обе эти оценки верны. Следуя подходу А.А. Боровкова, в 1969 г. [11] В.А. Перепелица и Э.Х. Гимади впервые дали формальное определение асимптотически точного алгоритма, которое буквально заключается в следующем. Пусть рассматривается задача на минимум целевой функции Z, Z*(I) — оптимальное значение функции Z для входа /, а алгоритм А находит для этого входа решение со значением Za(I)- Тогда алгоритм А называется асимптотически точным (при п —* оо, где п — некоторый параметр задачи), если существуют такие неотрицательные величины еп и 6п, что
V(ZA(I) < (1 + en)Z*(I)) >l-Sn, lim єп = 0, lim 6п = 0. (2)
п—юо п—>оо
В последующие годы асимптотически точные алгоритмы были построены для многих задач дискретной оптимизации (см., например [5], [б], [29], [41]). Определение понятий, связанных с понятием асимптотически точных алгоритмов, можно найти в обзоре Э.Х. Гимади, Н.И. Глебо-
ва и В.А. Перепелицы [4]. Из западной литературы стоит выделить обзоры Л. Сломински [47], а также Б. Рида и А. Фриза [34]. Б. Рид и А. Фриз обобщают понятие асимптотически точного алгоритма. Ведь выражение под знаком вероятности в (2) — это, вообще говоря, некоторое событие, зависящее от п. Если при этом вероятность наступления такого события стремится к единице с ростом п, то, согласно терминологии Рида и Фриза, оно происходит с высокой вероятностью (см. определение 1 ниже). Таким образом, асимптотически точный алгоритм есть не что иное, как алгоритм, находящий такое решение для данной задачи, которое с высокой вероятностью близко к оптимуму. Именно этот подход к решению задач в стохастических постановках используется в диссертации. Строя алгоритмы решения различных задач теории расписаний, мы устанавливаем свойства полученных с их помощью расписаний, справедливые с высокой вероятностью.
Хотелось бы также сказать несколько слов о других существующих подходах к решению стохастических задач, подчеркнуть их отличия от уже рассмотренного. Один из таких подходов заключается в том, чтобы минимизировать математическое ожидание целевой функции, являющейся случайной величиной. Например, в [36] содержится детальный обзор исследований стохастической задачи Flow Shop, в которой целевой функцией является математическое ожидание длины расписания (т.е., математическое ожидание функционала (1)). Заметим, что минимизация математического ожидания длины расписания мало что говорит нам о фактической длине расписания. Легко привести пример распределения случайной величины, такой что вероятность превышения ею своего ма-
тематического ожидания в два раза равна некоторому значению а из интервала (0,1). Таким образом, нахождение некоторого расписания Si, математическое ожидание длины которого минимально или близко к минимуму в классе всех допустимых расписаний задачи, не гарантирует нам никакой верхней оценки этой длины. Более того, может существовать расписание 5г, математическое ожидание длины которого больше, чем у расписания Si, но для длины которого существует верхняя оценка, имеющая место с вероятностью 1 и которую длина расписания Si превышает с ненулевой вероятностью. В этом смысле расписание , предпочтительнее. Но как уже замечалось выше, когда шла речь о подходах к исследованию ЛЛР-трудных задач теории расписаний, актуальны две ситуации: либо когда выделяется класс полиномиально разрешимых случаев, либо когда находится приближённое решение с верхней оценкой длины расписания. Поэтому предпочтительнее было бы в качестве приближённого решения иметь всё-таки расписание і%, а не Si, являющееся продуктом минимизации длины математического ожидания.
Ещё один существующий подход к постановке и решению стохастических задач заключается в минимизации целевой функции в смысле стохастического порядка. Случайная величина X стохастически меньше, чем случайная величина Y, если для любого t
(Х >t)< Р(У > t).
В рамках этого подхода находится расписание, длина которого стохастически минимальна или близка к стохастическому минимуму в классе допустимых расписаний задачи. К сожалению, такой подход не даёт непосредственного инструмента для получения верхних оценок погрешности
алгоритма. Можно лишь гарантировать, что оценка длины, справедливая для некоторого расписания, будет верна и для расписания стохастически минимальной длины. Примеры использования описанного подхода (в применении к стохастической задаче Flow Shop) можно найти в [33], [38], [42].
* * *
Итак, к решению стохастических задач теории расписаний мы применяем первый из описанных подходов и используем при этом следующее определение К. Рида и А. Фриза [34].
Определение 1. Событие А(х) выполняется с высокой вероятностью, если
F{A(x)} = 1 - о(1), х -* со.
Все результаты диссертации формулируются и доказываются в смысле определения 1, причём всегда в качестве х будет выступать количество работ п. Под вероятностным анализом алгоритма решения задачи теории расписаний в диссертации понимается, во-первых, рассмотрение задачи в стохастической постановке, во-вторых, чёткое описание классов распределений исходных длительностей операций, и в-третьих, представление и обоснование результатов, справедливых с высокой вероятностью при возрастающем количестве работ.
В диссертации применяются три подхода к исследованию задач теории расписаний с помощью вероятностного анализа. Первый подход применяется, когда для детерминисткой постановки данной задачи уже существует точный или приближённый алгоритм, но который применим только для определённого класса входов задачи, который описывается
некоторыми соотношениями между входными данными. Тогда задача вероятностного анализа заключается в том, чтобы выявить такие классы распределений входных данных, для которых эти соотношения выполнялись бы с высокой вероятностью. Таким образом, подход исключает какое-то вмешательство в данный алгоритм, анализируются уже готовые условия, при которых его можно применять для эффективного решения задачи.
Именно этот подход используется в главе 2 диссетрации, в которой мы рассматриваем алгоритм решения задачи Open Shop, разработанный СВ. Севастьяновым в [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 — в журнале "Дискретный анализ и исследование операций",
— в препринтах Института математики СО РАН им. С.Л. Соболева,
— в тезисах конференций.
Результаты диссертанта по теме диссертации опубликованы в работах [53]-[57].
Результаты, представленные в диссертации, докладывались автором:
на Втором международном симпозиуме по стохастическим алгоритмам — SAGA'03 (Хэтфилд, Великобритания, 2003);
на международной конференции по дискретному анализу и исследованию операций — DAOR'2004 (Новосибирск, 2004);
на международной конференции по исследованию операций — OR'2004 (Тилбург, Нидерланды, 2004).
Структура работы
Диссертация состоит из введения, трёх глав и приложения. Каждая глава состоит из нескольких разделов, некоторые разделы в свою очередь состоят из параграфов. Первый раздел каждой главы содержит предварительные сведения, последний — заключительные замечания и открытые вопросы.
Во введении дается общая характеристика работы, приводится обзор результатов и вводятся основные понятия и определения.
В первой главе рассматривается специфический случай задачи компактного суммирования векторов, к которой сводится целый класс задач теории расписаний. Строится полиномиальный алгоритм решения этой
задачи и проводится его вероятностный анализ. В конце главы формулируется несколько следствий для задач теории расписаний.
Во второй главе проведён вероятностный анализ точного алгоритма решения задачи Open Shop, выделены классы распределений исходных длительностей операций, на которых этот алгоритм строит расписание оптимальной длины с высокой вероятностью.
В третьей главе для задач о сборочной линии и Flow Shop предлагается простой алгоритм, строящий расписания за линейное время. Проводится вероятностный анализ этого алгоритма, показывается, что построенные им расписания удовлетворяют свойству асимптотической оптимальности.
В приложении приводятся некоторые результаты теории вероятностей, используемые в доказательствах результатов диссертации.
Нумерация.
При изложении материала используются такие структурные элементы как теоремы, леммы, следствия. Все эти "теоремоподобные" элементы имеют общую нумерацию. Например, если после теоремы с номером 2.5 идет следствие, то оно получает номер 2.6, а следующее за ним утверждение — номер 2.7, и т.д. Цифра 2 показывает, что эти утверждения находятся во второй главе. Иногда доказательства заканчиваются квадратиком () в конце строки. Определения нумеруются независимой сквозной нумерацией. Такие элементы как рисунки, таблицы и вынесенные формулы, имеют независимую нумерацию, которая начинается заново в каждой главе. Полный номер того или иного элемента состоит из двух чисел: номера главы и номера элемента внутри главы.
Доказательство теоремы
Применяя те же рассуждения, что и при рассмотрении шага 0 алгоритма, выводим условия В левых частях неравенств (1.25), (1.26) стоят величины вида /max — U. объединить в одно: Остаётся заметить, что по определению нормы \\$, векторов ej и величин U Лемма 1.3 доказана. Из описания алгоритма Л\2 вытекает следующая Лемма 1.4 Имеют место следующие соотношения: Лемма 1.4 буквально означает, что в результате процедуры выравнивания число "больших" векторов не увеличится, а к семейству "малых" векторов, возможно, добавятся новые элементы, причём все "малые" векторы, содержавшиеся в нём до процедуры выравнивания, останутся неизменными. Легко видеть, что условия выполнения алгоритма А\.$ совпадают с условиями выполнения шага 2 алгоритма и заключаются в том, что "малых" векторов должно быть достаточно много для того, чтобы для каждого вектора e j Є L П E построить последовательности {v\3 }tLi в цикле A\ и {v\Г }tifc +2 в цикле Лг- При каждом выполнении цикла А\ (А2) данный вектор h изменяется на вектор е , где г определяется процедурой Add. При этом вектор е выбирается из множества GnoiJ, к), если —h Є S(J,k) П L, и из множества Gi-i(J,k) в случае —h Є Gi(J,k). Цикл заканчивается, как только оказывается, что h Є Gi(J, к) (і = 1,2; J, к определяются в ходе процедуры Add и при каждом выполнении цикла могут быть различны). Последнее означает, что \\h\\ 2/2- Напомним, что перед началом цикла А\ выполнялось равенство /г = ej/2, где є] Є L П 7 . Таким образом, если предположить, что перед началом выполнения цикла А\ —h Є S(J,k) П L, то для завершения цикла необходимо, чтобы "малых" векторов из множества Gno{J,k) хватило для того, чтобы на каком-то шаге цикла оказалось —h Є Gno(J,k), и чтобы впоследствии "малых" векторов из множества Gi-i(J,k) хватило для того, чтобы на каком-то шаге цикла оказалось —h Є G/_i(J, к) (I = n0, no- 1,...,3). Пусть h обозначает вектор, полученный из вектора h после fc-ro обхода цикла А\ (Лг) в алгоритме А\.г. Введём обозначения: (I = no — 1,... ,2). Итак, для того, чтобы показать, что циклы Лі, Ач выполняются за конечное число шагов, нужно убедиться в выполнении неравенств Глава 1.
КомпактноеКомпактное суммирование векторов (I = 2,..., по — 1), из которых следуют неравенства (1.29). Каждое неравенство из (1.30) предполагает предельный случай, а именно: все векторы из семейства Е ПЬ имеют одинаковое направление, одинаковый модуль, равный максимально возможной величине етах; более того, предполагается, что при каждом выполнении циклов Аі, Ач вектор е о выбирается из одного и того же множества Gi(J, к) и имеет минимальную величину по модулю: yi-\. Доказательство неравенств (1.30) для описанного предельного случая повлечёт за собой и выполнение за конечное число шагов циклов Ао,А\, Аі для всех других ситуаций. В связи с этим замечанием в дальнейшем будем считать, что (J, к) фиксированы. Заметим, что в неравенствах из (1.30) участвуют мощности семейств векторов из Е , поэтому их можно проверить только если уже получены выходные данные алгоритма Л\.2- Лемма (1.4) позволяет перейти к аналогичным семействам векторов из Еп, позволяя, таким образом суммирование векторов (I = 2,..., по — 1), из которых следуют неравенства (1.29). Каждое неравенство из (1.30) предполагает предельный случай, а именно: все векторы из семейства Е ПЬ имеют одинаковое направление, одинаковый модуль, равный максимально возможной величине етах; более того, предполагается, что при каждом выполнении циклов Аі, Ач вектор е о выбирается из одного и того же множества Gi(J, к) и имеет минимальную величину по модулю: yi-\. Доказательство неравенств (1.30) для описанного предельного случая повлечёт за собой и выполнение за конечное число шагов циклов Ао,А\, Аі для всех других ситуаций. В связи с этим замечанием в дальнейшем будем считать, что (J, к) фиксированы. Заметим, что в неравенствах из (1.30) участвуют мощности семейств векторов из Е , поэтому их можно проверить только если уже получены выходные данные алгоритма Л\.2- Лемма (1.4) позволяет перейти к аналогичным семействам векторов из Еп, позволяя, таким образом, проверять условия выполнимости обоих алгоритмов перед началом их выполнения. Итак, нами доказана следующая Лемма 1.5 Алгоритм Л\,з выполняется за конечное число шагов, если выполняются условия Пусть выполнены условия (1.23) и (1.31). Проанализируем, достаточно ли этих условий, чтобы оценка радиуса суммирования (1.14) векторов из І? согласно перестановке 7г была верна. Рассмотрим внимательнее циклы Лі, Л 2 алгоритма Лі.з и проанализируем структуру перестановки 7т7 (j = 1,..., \L П Е \). В первых &i позициях перестановки 7rJ находятся номера векторов v\f , в (к + 1)-ой позиции — вектор е Є ЬГ\Е„. Заметим, что суммирование векторов с номерами из перестановки 7Г7 происходит из шара радиуса г/2 (согласно описанию алгоритма Аі.з). Согласно условиям (1.31) последовательность і \\ Ylt=ivt \\ \. монотонно возрастает, fci причем
Приложения для стохастических задач теории расписаний
В данном разделе перечислены получаемые с помощью алгоритмов -4i.2, Ді.з результаты двух видов: условие построения оптимального расписания в стохастической задаче Open Shop и абсолютные оценки точности для стохастических задач Flow Shop, Job Shop и задачи о сборочной линии. Все новые алгоритмы получаются из известных ранее алгоритмов решения задач теории расписаний путём замены в них процедуры выравнивания и процедуры компактного суммирования векторов на алгоритмы .До, Лі.з соответственно. В нижеследующих разделах главы 1 такие алгоритмы мы будем называть "модифицированными" без каких-либо специальных оговорок. Задача Open Shop уже была сформулирована нами в неявном виде во введении. В частности, в этой задаче не задаётся никаких дополнительных ограничений на порядок выполнения операций. Задача Open Shop Найти расписание, удовлетворяющее условиям {L\) — (L3) и минимизирующее функционал (1) Более подробные сведения о задаче Open Shop содержатся в главе 2. Обозначим через Л\л модифицированный алгоритм решения задачи Open Shop m машинами и п работами из [45]. Теорема 1.17 Пусть длительности операций стохастической задачи Open Shop с т машинами и п работами удовлетворяют условиям I—II. с высокой вероятностью является достаточным для построения алгоритмом «4.1.4 оптимального расписания длины lmax. Трудоёмкость алгоритма AIA we превышает 0(т2п2). За последние 20 лет было построено несколько алгоритмов, которые находят оптимальное расписание для задачи Open Shop при условии вида тах (" )Ртах)5 верны для задачи Open Shop в любой постановке. Чем меньше величина (m,pmax), тем шире этот класс. Однако для рассматриваемой стохастической задачи алгоритм AIA [56] превосходит разработанные ранее по широте класса полиномиально разрешимых случаев и не уступает им в трудоёмкости. Результаты перечислены в нижеследующей сравнительной таблице. Помимо условий (Ьі)-(Ьз), сформулированных во введении, для задачи Flow Shop требуется ещё одно условие, заключающееся в том, что каждая из работ Jj (j = 1,..., п) выполняется на машинах Mi,..., Mm последовательно:
Найти расписание, удовлетворяющее условиям (Li) — (L4) и минимизирующее функционал (1) Обозначим через Аія модифицированный алгоритм решения задачи Flow Shop m машинами и п работами из [45]. Теорема 1.18 Пусть длительности операций стохастической задачи Flow Shop с т машинами и п работами удовлетворяют условиям I—II. Тогда алгоритм Ai.s с высокой вероятностью строит расписание S с оценкой длины за время 0(т2п2). Сравнительная таблица, аналогичная по смыслу таблицам 1.1 и 1.2, приводится ниже. Перечислены только те результаты, в которых абсолютная погрешность алгоритма не зависит от Zmax и имеет вид /(га,ртах). Таблица 1.3. Задача Flow Shop Ограничения на выполнения операций в задаче о сборочной линии требуют выполнения условий (Li)-(L2), сформулированных во введении, а также условия (L ), заключающегося в том, что последняя выполняемая операция каждой работы Jj — это операция, выполняемая на машине Мт. (Ьь) smi sij +Pij (і = 2,..., га; j = 1,..., n). Задача о сборочной линии Найти расписание, удовлетворяющее условиям (Za), (L2), (5) и минимизирующее функционал (1) Обозначим через Лі.в модифицированный алгоритм решения задачи о сборочной линии т машинами и п работами из [43]. Теорема 1.19 Пусть длительности операций стохастической задачи о сборочной линии с т машинами и п работами удовлетворяют условиям I—II. Тогда алгоритм 4і.б с высокой вероятностью строит расписание S длины за время 0(т2п2). Ниже приводится сравнительная таблица известных результатов по применимости к рассматриваемой стохастической задаче о сборочной линии. В задаче Job Shop, являющейся естественным обобщением уже рассмотренной в 1.5.2 задачи Flow Shop, каждая работа имеет т$ m операций и выполняется последовательно на машинах Мж. ... ,Мж.г., и перестановка 7Tj = (яд,.. .,7Tjrj) задаёт порядок выполнения работы J у. (L6) Sij Si-ij + РІ-IJ (j = 1,..., n; і = 7Tij,..., -rrjrj). Задача Job Shop Найти расписание, удовлетворяющее условиям (L{) — (Ьз),(Ьб) и минимизирующее функционал (1)
Формулировки результатов
Пока построенное расписание, естественно, не имеет оптимальной длины, но зато является допустимым. Следующая серия действий преобразует полученное расписание в расписание длины /тах (но уже не обязательно допустимое). Для этого расписание машины Mi "обрезается"в момент времени Zmax и обрезанный "хвост" расписания помещается в начало (момент времени 0). После этой процедуры длина расписания на машине М\ в точности равна /тах, и кроме того, расписание машины Mi удовлетворяет условию (Li) (в силу определения величины Ді). На г-том шаге расписание машины МІ обрезается в момент времени lmax и обрезанный "хвост" помещается в начало. Если все выполняемые на машине МІ операции оказались в "хвосте", то расписание машины МІ снова обрезается в момент времени lmax и уже новый "хвост"помещается в начало. Рано или поздно на машине Мг- получится расписание длины /Шах, в котором, возможно, не выполнено условие (Li), из-за того, что перед последним обрезанием расписания в момент lmax выполнялась какая-то операция. Тогда расписание машины МІ сдвигается вправо на величину 5І — минимальную величину, при сдвиге на которую вправо в расписании машины МІ на момент Zmax приходится конец какой-либо операции. Опять расписание машины МІ обрезается в момент времени /тах и обрезанный "хвост" помещается в начало. В конце концов, на машине МІ составлено расписание длины Zmax с выполненным условием (Bi). Расписания на машинах Mi+i,,.., Mm сдвигаются вправо на величину 5». После 771 шагов составлено, наконец, расписание длины tmaxj в котором, возможно, не выполнено условие (Ьз). Нетрудно видеть также, что #2 = 0 (в силу определения величин Ai и Дг, на сумму которых сдвига Глава 2. О полиномиальной разрешимости задачи Open Shop ется вправо расписание машины Мг). Трудоёмкость алгоритма не превышает 0{mn). Нетрудно заметить, что условие (з) будет выполняться для расписания, построенного алгоритмом Дг.ь если общий сдвиг вправо (до обрезания) расписания машины Мт (который равен в точности Ai + А2 + ...+ Это даёт нам условие допустимости расписания, которое, таким образом, задаёт класс полиномиально разрешимых примеров задачи
Open Shop: где г}(т) = А2 +... + Am + Am+i + S3 +... + Sm. Чтобы прийти к условию (2.1), остаётся заметить, что величина г](т) может быть оценена сверху величиной т2 [45], а также вспомнить, что на протяжении описания алгоритма в качестве длительностей операций {pij} выступали отношения Итак, для того, чтобы сформулировать задачу Open Shop с п работами и т машинами в стохастической постановке, мы полагаем все исходные длительности операций р независимыми случайными величинами (имеющими, вообще говоря, различные распределения). Пусть Еру = IMj и bij = (Epij — Hij\r) ,г для некоторого г 1. Обозначим Заметим, что для г = 2 величина Ъц представляет собой квадратный корень из дисперсии случайной величины р , а величина В{П — квадратный корень из суммы дисперсий случайных величин pn,... ,РІП- Рассмотрим теперь ряд условий на распределения величин р . (Bi) Все случайные величины {pij \ і = 1,2,..., m;j = 1,2, ...п} имеют невырожденные распределения, и для некоторого г 1 существуют моменты К А. bj Оказывается, при п — со неравенство (2.1) выполняется с высокой вероятностью, т. е. как только Ру удовлетворяют условиям (Bi) — (.82)- Следует заметить, что величины /тах и ртах возрастают при п — со и, следовательно, за-висят от п. Ниже формулируется главный результат главы 2.
Теорема 2.1 ДАЛ стохастической задачи Open Shop с возрастающим числом работ п, фиксированным числом машин тис длительностями операций, удовлетворяющими условиям (В{) — (В2), алгоритм А2.1 с высокой вероятностью строит оптимальное расписание, длина которого совпадает с максимальной машинной нагрузкой. Рассмотрим более внимательно условия {В\) — (і?г). Прежде всего заметим, что условие (1) рассматривается для каждой машины неза висимо. Поэтому добавление или удаление константного числа машин с длительностями операций, удовлетворяющими условию (Ві), не повлияет на верность утверждения теоремы 2.1. Оба условия в совокупности являются достаточными. Несмотря на то, что условие (В\) не необходимое, оно является достаточно слабым: ему удовлетворяет большинство известных распределений, например, такие распределения как пуассоновское, нормальное, экспоненциальное, равномерное. Условие (Бг) также не очень сильное. Например, легко видеть, что оно выполняется для независимых одинаково распределённых случайных величин, для которых существует конечный момент порядка г . Действительно, в этом случае при п —» со имеем: Следовательно, условие (Дг) превращается в что, очевидно, выполняется. Условия (1)-(.62) теоремы 2.1 на распределения длительностей операций не всегда могут быть легко проверены. Вместо этих условий мы предлагаем условие (Вз) — более слабое, но легче проверяемое. (Bz) Ha машине МІ (І = 1,..., m) длительности операций являются независимыми одинаково распределёнными невырожденными случайными величинами, причём существует 6 . Легко видеть, что из выполнения условия (Вз) моментально следует выполнение условий (В{) — (В2).
Формулировки результатов
Напомним, что через Z» мы обозначаем нагрузку машины МІ, через lmax — максимальную машинную нагрузку, а через pmax максимальную длительность операции: Пусть 7Г = {7Гі,..., 7ГП} — некоторая перестановка индексов {1,... , п}. Расписание S„ назовём перестановочным расписанием, если все работы выполняются на каждой машине в порядке 7Г. Как для задачи о сборочной линии, так и для задачи Flow Shop будем находить решение, используя один и тот же алгоритм. Алгоритм «4з.1« Строим перестановочное расписание согласно перестановке 7Г = {1,... , п}. Пусть исходные длительности операций удовлетворяют следующему условию. пределённые невырожденные случайные величины с конечной дисперсией а2 со. Сформулируем теперь основные результаты главы 3. Теорема 3.1 Для стохастической задачи Flow Shop с т машинами, п работами и длительностями операций, удовлетворяющими условию (Р) расписание S, построенное алгоритмом Лзл, с высокой вероятностью является асимптотически оптимальным, а длина этого расписания Cmax(S) с высокой вероятностью удовлетворяет следующей Теорема 3.2 Для стохастической задачи о сборочной линии с т машинами, п работами и длительностями операций, удовлетворяющими условию (Р) расписание S, построенное алгоритмом Азл, с высокой вероятностью является асимптотически оптимальным, а длина этого расписания Cmax(S) с высокой вероятностью удовлетворяет следующей оценке: Стохастическая задача о сборочной линии ранее в мировой практике не рассматривалась. Что же касается стохастической задачи Flow Shop, то хочется отметить два относительно недавн работы выполняются на каждой машине в порядке 7Г. Как для задачи о сборочной линии, так и для задачи Flow Shop будем находить решение, используя один и тот же алгоритм. Алгоритм «4з.1« Строим перестановочное расписание согласно перестановке 7Г = {1,... , п}. Пусть исходные длительности операций удовлетворяют следующему условию. пределённые невырожденные случайные величины с конечной дисперсией а2 со. Сформулируем теперь основные результаты главы 3. Теорема 3.1 Для стохастической задачи Flow Shop с т машинами, п работами и длительностями операций, удовлетворяющими условию (Р) расписание S, построенное алгоритмом Лзл, с высокой вероятностью является асимптотически оптимальным, а длина этого расписания Cmax(S) с высокой вероятностью удовлетворяет следующей Теорема 3.2 Для стохастической задачи о сборочной линии с т машинами, п работами и длительностями операций, удовлетворяющими условию (Р) расписание S, построенное алгоритмом Азл, с высокой вероятностью является асимптотически оптимальным, а длина этого расписания Cmax(S) с высокой вероятностью удовлетворяет следующей оценке:
Стохастическая задача о сборочной линии ранее в мировой практике не рассматривалась. Что же касается стохастической задачи Flow Shop, то хочется отметить два относительно недавних близких по содержанию к утверждению теоремы 3.1 результата. Рассматривая в качестве исходных длительностей операций независимые случайные величины, равномерно распределённые в отрезке [0,1], Ф. Каминский и Д. Симчи-Леви [39] исследуют стохастическую задачу Flow Shop, но в качестве целевой функции рассматривают сумму длин расписаний по всем машинам (в то время как в нашей постановке в качестве целевой функции выступает максимум длин расписаний по всем машинам, который мы и называем длиной расписания). Они анализируют известный эвристический алгоритм, суть которого в том, что на всех машинах работы выстраиваются в возрастающем порядке их суммарных длительностей, и показывают, что Глава, 3. Произвольные перестановочные расписания где ZSPT представляет собой значение целевой функции, полученное на выходе этого алгоритма, a Z оптимум среди перестановочных расписаний задачи Flow Shop. Авторы статьи [51] усиливают этот результат, устанавливая соотношение Z Более того, они рассматривают гораздо более их близких по содержанию к утверждению теоремы 3.1 результата. Рассматривая в качестве исходных длительностей операций независимые случайные величины, равномерно распределённые в отрезке [0,1], Ф. Каминский и Д. Симчи-Леви [39] исследуют стохастическую задачу Flow Shop, но в качестве целевой функции рассматривают сумму длин расписаний по всем машинам (в то время как в нашей постановке в качестве целевой функции выступает максимум длин расписаний по всем машинам, который мы и называем длиной расписания). Они анализируют известный эвристический алгоритм, суть которого в том, что на всех машинах работы выстраиваются в возрастающем порядке их суммарных длительностей, и показывают, что Глава, 3. Произвольные перестановочные расписания где ZSPT представляет собой значение целевой функции, полученное на выходе этого алгоритма, a Z оптимум среди перестановочных расписаний задачи Flow Shop. Авторы статьи [51] усиливают этот результат, устанавливая соотношение Z Более того, они рассматривают гораздо более широкий класс распределений исходных длительностей операций. Точное определение сходимости п.н. (почти наверное) можно найти, например, в [3]. Доказательство теоремы 3.2. Длина перестановочного расписания Sn для задачи о сборочной линии может быть записана следующим образом [43]: (j = 1,..., п) и норму , определяемую для х = (#i,..., хт-\) соотношением то из оценки (3.6) вытекает оценка для длины расписания, имеющая
Похожие диссертации на Вероятностный анализ алгоритмов построения кратчайших расписаний для многостадийных систем
