Графический метод динамического программирования с использованием кусочно-линейных функций Беллмана Гафаров Евгений Рашидович

Содержание к диссертации

Введение

1 Графический метод точного решения 9

1.1 Сведения о методах решения задач комбинаторной оптимизации 10

1.2 Описание графического метода точного решения 12

1.3 Графический алгоритм решения задачи 1 (no-idle) \ max Tj 16

1.4 Графический алгоритм решения задачи l\dj = d\ WjTj 24

2 Графический метод приближенного решения 34

2.1 Описание модификации графического метода для поиска приближенного решения 35

2.2 Полная полиномиальная аппроксимацонная схема для задачи l\dj = d\ J WjTj 36

2.3 Дополнительные сведения о приближенном решении задач 40

3 Алгоритмы решения задач теории расписаний

3 3.1 Классические одноприборные задачи теории расписаний 45

3.2 Одноприборные задачи с обратными критериями оптимизации 49

3.3 Одноприборные задачи с одним невозобновимым ресурсом 65

3.4 Задача одноколейной железной дороги с двумя станциями 74

3.5 Графические алгоритмы решения одноприборных задач 92

3.6 Сравнение графических алгоритмов и классических алгоритмов динамического программирования 99

3.7 Результаты численных экспериментов 101

Графические алгоритмы решения задач типа Ранец 103

4.1 Графические алгоритмы решения задачи об инвестициях 103

4.2 Графические алгоритмы решения задачи о размере партии продукции 117

О сложности решения некоторых задач комбинаторной оптимизации 120

5.1 Задача минимизации времени выполнения работ проекта с учетом ограничения на ресурсы 120

5.2 Задача балансировки производственной линии 147

5.3 Задача о двух параллельных не взаимозаменяемых приборах 154

5.4 Алгоритм решения RCPSP в программном продукте 1С: Управление строительной организацией 162

5.5 Программные продукты для автоматизированного составле ния расписаний в учебных заведениях 163

Заключение 167

Список использованных источников 1

• Графический алгоритм решения задачи 1 (no-idle) \ max Tj
• Дополнительные сведения о приближенном решении задач
• Графические алгоритмы решения одноприборных задач
• Задача балансировки производственной линии

Введение к работе

Актуальность темы.

В диссертационной работе представлен метод решения задач комбинаторной оптимизации, являющийся модификацией метода динамического программирования, в котором на каждой стадии строятся кусочно-линейные функции Беллмана¹. На основе данного метода построены алгоритмы точного и приближенного решения задач теории расписаний² и задач типа Ранец.

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

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

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

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

bellman, R.E. 1957. Dynamic Programming. Princeton University Press, Princeton, NJ. Republished 2003: Dover, ISBN 0-486-42809-5

²Танаев B.C., Шкурба В.В., Введение в теорию расписаний. М.: Наука, 1975.

³Оптнер С.Л. Системный анализ для решения проблем бизнеса и промышленности. М.: Советское радио, 1969.

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

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

Цель работы заключается в:

исследовании задач комбинаторной оптимизации и, в частности, задач теории расписаний;

выявлении их сложности (NP-трудности, полиномиальной разрешимости);

нахождении свойств оптимальных решений исследуемых задач;

разработке нового эффективного метода решения исследуемых задач;

построении на его основе алгоритмов точного и приближенного решения.

Научная новизна.

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

для некоторых задач алгоритмы, основанные на графическом методе (GrA), имеют полиномиальную трудоемкость, в то вре-

⁴Гэри М., Джонсон Д.Вычислительные машины и труднорешаемые задачи. М.: Мир, 1982.

мя, как исходные алгоритмы динамического программирования (DPA) - псевдополиномиальную. Или же трудоемкость GrA существенно меньше трудоемкости DPA;

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

GrA можно просто модифицировать в полную полиномиальную аппроксимационную схему (FPTAS);

с помощью GrA можно решать примеры с нецелочисленными параметрами;

и другие.

1. На основе данного метода предложены алгоритмы точного и приближенного решения задач типа Ранец: задачи об инвестициях и задачи минимизации штрафа за невыпущенную продукцию.

2. Установлена NP-трудность в сильном или обычном смыслах 7 классических и вновь сформулированных задач теории расписаний с одним прибором.

3. Разработаны алгоритмы точного и приближенного решения, основанные на предложенном методе, для 8 исследуемых задач теории расписаний.

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

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

Теоретическая и практическая значимость.

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

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

Апробация работы. Результаты диссертационной работы докладывались и обсуждались на собрании Отделения энергетики, машиностроения, механики и процессов управления РАН 18 декабря 2012г., на научных семинарах отдела математических проблем распознавания и методов комбинаторного анализа Вычислительного Центра РАН, семинарах кафедры системного анализа факультета ВМК МГУ им. М.В.Ломоносова (руководитель семинара академик РАН Кур-жанский А.В.), общемосковском научном семинаре "Математические методы анализа решений в экономике, бизнесе и политике" в Высшей школе экономики 18 декабря 2013г., семинарах Института проблем управления РАН, на международных конференциях: INCOM2009 (Москва, 2009), INCOM2012 (Бухарест, 2012), EURO2010 (Лиссабон, 2010), PMS2010 (Тур, 2010), PMS2012 (Лювен, 2012), УИК2012 (Москва, 2012), OPTIMA2011 (Петровач, 2011), OPTIMA2012 (Лиссабон, 2012), ЕССО2010 (М алага, 2010) и многих других.

Публикации. По теме диссертации опубликовано 57 печатных работ в том числе 19 в изданиях из списка, рекомендованного ВАК РФ [6-24]. Получено два свидетельства о регистрации программ для ЭВМ (№ 2013660198, № 2014660877).

Структура и объем работы. Диссертация состоит из введения, пяти глав, заключения, указателя основных обозначений и списка использованных источников (158 наименований). Содержит 26 таблиц и 9 иллюстраций. Общий объем диссертации составляет 191 страниц.

Графический алгоритм решения задачи 1 (no-idle) \ max Tj

Пусть Т = {\t\_i — Р1,ц_1 — pi,... } - множество всех точек излома из таблицы функции Ф (t) и Т = {tj_l}tf_l}...} - множество всех точек излома из таблицы функции Ф2(). Объединим оба множества Т1 и Т2 в одно Т, где Т = { і, 2,... ,te}, t\ Ьі .. . ,te. Рассмотрим каждый интервал (ti}ti+i]} г=1,2,...,е — 1, и сравним на них функции Ф (t) и Ф2(). Пусть интервал ( , +i] содержит интервал ( _!, ] из таблицы функции Ф1 ) и интервал (ty_i,ty } из таблицы функции Ф2(). Тогда фі( ) = ( - г ) wf + bf и Ф2() = (t - tf_x) uf + bf. Если функции Ф1 ) и Ф2() не пересекаются на интервале (ti,ti+i\, то добавим в таблицу функции Fi(t) колонку с этим интервалом со значением b = min{6 , by } и соответствующим значением и (it или Uy ). Если же данному интервалу принадлежит точка пересечения і!" функций Ф1 ) и Ф2(), то добавим две колонки (U,t "] И (t ",ti+i\.

Данный шаг может быть выполнен за 0(m/_i) операций. Шаг 3.5. Если в таблице функции Fi(t) есть два интервала ( }tf] и ( f, f+1], uf = uf+1 nbf + uf- (tf - tf 1) = bf+1, тогда примем tf := tf+1 и удалим из таблицы колонку к + 1. Шаг 3.6. Пусть т - количество колонок в таблице F[(t) и для к, 1 к ті, выполняется bf UB bt+. Тогда вычислим tfB такое, что UB = (tf8 — tf l)uf + bf. В колонке с интервалом (tf 1,tf] (колонка к), примем tf = tfB и удалим колонку к + 1,к + 2,... ,т.

Шаг 3.7. Если / = п, то перейдем на Шаг 4, иначе / := / +1 и перейдем на Шаг 3. Шаг 4. В таблице функции Fn(t): определим колонку с интервалом (tn,tn+1], где tkn 0 t +l. Оптимальное значение целевой функции F = &п+1 + (о- )Ч+1 Очевидно, что в результате работы GrA будет найдено то же оптимальное значение целевой функции, что и в DPA. Поэтому GrA находит оптимальное решение. Покажем, что все функции Fi(t), I = 1, 2,. .. ,п, являются непрерывными кусочно-линейными функциями на интервале (—оо,-7 }.

Очевидно, что функция F\{t) является непрерывной и кусочно-линейной функцией с одной точкой излома. В соответствии с Шагом 3 обе функции Ф (t) и Ф (t) также являются непрерывными и кусочно-линейными. Поэтому функция F2(t) = тахІФ1 ), Ф2()} также является непрерывной и кусочно-линейной. Аналогично можно показать, что все функции Fi(t), I = 1, 2,..., п, обладают этими свойствами.

Пусть найдена функция Fi(t), представленная в Табл. 1.8. Согласно операциям, представленным на Шаге 3 для данной функции имеем Ъ\ = bf bf bf bst+1 Ьр+1 = UB. Тогда количество колонок в таблице функции F[(t) меньше или равно количеству различных значений Ьр+ плюс 1.

GrA может быть модифицирован так, чтобы концы рассматриваемых интервалов были целыми точками. Для этого если точка t " полученная на Шаге 3.3. не целая, то в таблицу функции F[(t) необходимо включить две колонки с интервалами: ( , [ "J] и (Г П й-і]- Обозначим этот алгоритм GrA-I.

Очевидно, что трудоемкость GrA зависит полиномиально от количества колонок ш/ + 1. Согласно описанию GrA-I все значения Щ в таблице функции Fiit) являются целыми. Тогда в таблице Fi[t) не более UB + 2 колонок, т.к. Щ Є [О, UB] и Щ - целые числа. GrA-I может быть модифицирован так, чтобы рассматривать только интервал [0, d]. Так как все рассматриваемые Ц - целые числа, то в таблице функции будет не более d + 1 колонок.

Тогда трудоемкость Шага 3 - 0(mm{UB} d}) операций для каждого / = 1,2,...,п. Тогда трудоемкость GrA-I - 0(пmin{F ,d}) операций, т.к. \UB F UB.

Напомним, что трудоемкость альтернативной реализации DPA -0(nmin{ i, F }) операций, что соответствует трудоемкости GrA-I. Несмотря на то, что трудоемкость графического алгоритма не лучше, в Главах 2 и 3 приводятся некоторые его преимущества. Стоит заметить, что алгоритмам GrA-I и DPA требуется одинаковый объем памяти 0(min{UB,d}).

Заключение по первой главе Можно выделить следующие преимущества GrA над DPA: с помощью GrA можно решать примеры с нецелочисленными параметрами; время работы GrA на двух примерах со множеством числовых параметров Р и множеством параметров {&-1(У=Ы6 Є Р}, / 1, совпадает, в то время, как время работы DPA будет в 10 раз больше на втором примере, т.е. с помощью GrA, можно решать примеры "большого масштаба"; принимаются во внимание внутренние свойства задачи (например, для задачи о Ранце может оказаться, что предмет с наименьшей удельной стоимостью не оказывает влияние на функцию Беллмана); известно, что GrA для некоторых задач имеет полиномиальную трудоемкость, в то время, как исходный алгоритм DPA - псевдополиномиальную. Или же GrA существенно сокращает трудоемкость DPA (например, для задачи максимизации суммарного взвешенного запаздывания) .

Необходимо отметить, что для некоторых классов примеров рассматриваемых задач трудоемкость GrA равна трудоемкости DPA. Можно привести примеры задач с нецелочисленными параметрами, для которых трудоемкость GrA является экспоненциальной.

Дополнительные сведения о приближенном решении задач

Приближенное решение (значения управляемых параметров) может быть получено обратным ходом из таблиц, полученных на Шаге 3.6 следующим образом. В таблице значений параметра хп: определим колонку Й", п+1], где tkvn 0 tkvn+l. Если 1, то в таблице хп-\ необходимо рассмотреть колонку с интервалом \ъ х ,tn J, где t х рп t х -39 Иначе если x n+l = 0, в таблице хп-\ необходимо рассмотреть колонку с интервалом (fc,fc+1], где fc 0 fc+1. Таким образом можно получить все значения управляемых параметров за 0(nlog(n/e)) операций. Пусть функции Fi(t), I = 1,2,...,п, получены оригинальным GrA, а функции Fl (t), I = 1,2,...,п, получены представленным модифицированным алгоритмом. Теорема 2.1 С помощью модифицированного GrA приближенное реше-ние может быть найдено за 0(—) операций, причем F (1 + e)F . Доказательство: 1) Покажем, что для всех t Є (/1_ /2_ ] выполняется \FtA(t) -Fi(t)\ 5/2. Необходимо рассмотреть результат вычисления выражения \Fl (t) — Fi(t)\ только в точках излома t , х,. .. , 2_ . В этих точках неравенство \F}(t) — Fi(t)\ 5/2 выполняется. Причем эти точки - концы линейных фрагментов функций Fi{t) и F}(t), т.е. неравенство выполняется и для других точек t. 2) Покажем, что для каждого /, / = 1,2,...,п, и для каждого t Є (—оо, +оо) выполняется \Fi(t) — Fi(t)\ 1-5/2. Очевидно, что неравенство выполняется для 1=1. Пусть неравенство выполняется / — 1, 1 / п, т.е. для t Є ( —оо,+оо) выполняется \F xit) — F/_i(t) (/ — 1)5/2. Пусть функции Ф it) и Ф it) получены с использованием функции Fi-iit), а функции ф1 ) и / 2() - с помощью функции F it). Тогда \ф1 )-Ф1 )\ (/ - 1)5/2 и \ф2 ) - Ф2() {1- 1)5/2. Поэтому \FtA(t) - Fi(t)\ \ітт{фгіі),ф2іі)} + 5/2) - пііпІФ1 ), Ф2()} /2. Тогда, согласно индукции, неравенство \F[ it)—Fiit)\ 1-5/2 выполняется. -40 3) Согласно 1) выполняется \F — F (0)\ 5/2. Согласно 2) выполняется \F (0) — Fn(0) п 5/2, где Fn(0) = F . Тогда выполняется F -F n-6 пЩ 1, т.е. F (1 + e)F .

Трудоемкость модифицированного GrA зависит линейно от п и от количества колонок в таблицах функций F}(t). Количество колонок на каждой стадии не превышает О(-). Тогда трудоемкость модифицированного GrA - 0(—) операций.

Если для задачи можно построить GrA с трудоемкостью 0(naUB) операций, тогда для задачи можно построить FPTAS, трудоемкость которого 0{п + -—) операций, где UB - верхняя оценка, которая не более чем в 0(w ) раз больше оптимального значения целевой функции, вычисляемая за О ь1) операций, где а, /3, 7 константы. Таким образом трудоемкость FPTAS зависит от относительной погрешности и найденного значения верхней оценки, т.е. от /3. Для частных случаев -В — 1, В — 1G и задачи l\dj = dl WjTj, рассматриваемых в следующей главе, имеем верхнюю оценку, для которой /3 = 0, при этом для других задач, рассмотренных в следующей главе /3 = 1, т.е. UB/LB = п.

В работе [106] предложена следующая техника по минимизации трудоемкости алгоритмов приближенного решения. Если для задачи существует

FPTAS с трудоемкостью P(L, , j ): где L - длинна входа, UB, LB - из ив вестные верхняя и нижняя оценки, и значение -г-Б не ограничено некоторой константой, тогда техника позволяет за P(L, log log- g) операций найти такие значения UBQ И LBO7 ЧТО LBQ F 7 o 3L o, т.е. такие верхнюю и нижнюю оценки, что отношение тт не превышает константу 3. С использованием таких значений UBQ И LBQ трудоемкость FPTAS может быть сокращена до P(L, -) операций, где Р - тот же полином. С использованием этой техники трудоемкость FPTAS для задач 1 (no-idle) 11 max J2 wjTj и 111 Yl GTj может быть сокращена до 0(п2 log log n+ -) операций.

Заметим, что классические DPA, представленные в предыдущей главе также могут быть модифицированы в FPTAS. Трудоемкость такой FPTAS в O(log-) больше трудоемкости FPTAS, основанной на GrA. Некоторые другие преимущества FPTAS, основанных на GrA представлены в следующей главе. Заключение по второй главе Графический метод может быть модифицирован для поиска приближенного решения с гарантированной относительной погрешностью є и трудоемкость, полиномиально зависящей от размерности задачи и є (FPTAS). В Главах 3 и 4 представлены FPTAS для задач теории расписаний и задач типа Ранец. Показано, что трудоемкость таких FPTAS меньше трудоемкости FPTAS, основанных на DPA.

Графические алгоритмы решения одноприборных задач

Доказательство проведем сведением ЗАДАЧИ РАЗБИЕНИЯ к частному случаю задачи l(nd)\\max 2wjTj за полиномиальное время. Без потери Лемма 3.7 Для каждого примера задачи 1 (nd) \ max Е wjTj существует оптимальное расписание вида 7Г = (G,H), где все требования j Є Н запаздывают, а все требования і Є G не запаздывают. Все требования из множества G обслуживаются в порядке невозрастания значений —, Рз а все требования из множества Н обслуживаются в порядке неубывания значений —. Рз Доказательство: 1) Предположим, что существует оптимальное расписание вида 7Г = (7ід, j, 7Г2, г, 7Гз), при котором требование j запаздывает, а требование і не запаздывает. Для расписания 7г = (7Гі, і, j, 7Г2, тгз) выполняется: F(7ir) - F(TT) WjiTjin ) - Tjfr)) + wt(Tt(7ir) - ВД) = Wjipi) + (0) 0. Получили противоречие, так как для расписания ж значение целевой функции больше, а значит расписание 7Г не оптимальное. Повторив необходимое число раз подобное преобразование расписания, мы получим оптимальное расписание вида 7Г = (G, Н). 2) Рассмотрим оптимальное расписание вида 7Г = (G,H): где все тре бования j Є Н запаздывают, а все требования і Є G не запаздывают. Покажем, что все требования j Є Н обслуживаются в порядке неубывания значений —. Предположим, что существует оптимальное расписание Pj 7Г = (7Гі, ji, j2,7Г2), при котором требования ji и j2 запаздывают и j± , т.е. w,- т,-2р . Для расписания 7Г = (7ГЬj2,Ji,7r2), выполняется F(TT ) - F(TT) = ( (тг ) - Тп(тг)) + ( (тгО - Т,-2(тг)) Wj1pj2 — Wj2 min{pj1,Tj2(7r)} 0. Получили противоречие, а значит, расписание 7Г = (7Гі, ji, j 2, 7Г2) не оптимальное. После необходимого количества преобразований расписания 7Г получим оптимальное расписание, при котором все требования множества Н будут упорядочены в порядке неубывания величин —. 3) Рассмотрим оптимальное расписание вида 7Г = (G,i7), где все требо вания j Є Н запаздывают, а все требования і Є G не запаздывают. По кажем что все требования і Є G могут обслуживаться в порядке невоз растания значений — при оптимальном расписании. Для всех требований Pj і Є G выполняется di 2 Pk, иначе, если di pk-, то расписание кєс кєс 7rf = (G \ {і},і,і7) "лучше" (т.е. для данного расписания значение целе вой функции больше), а следовательно, получено противоречие. Поэтому все требования і Є G могут быть обслужены в любом порядке (в том чис -бі ле, и в порядке невозрастания величин —) так как при любом порядке обслуживания все требования из G не запаздывают. Следствием является следующая лемма. Лемма 3.8 Для каждого примера задачи 1 (nd) max 7} существует оптимальное расписание вида 7Г = (G,H), где все требования j Є Н запаздывают, а все требования і Є G не запаздывают. Все требования из множества G обслуживаются в порядке неубывания продолжительности обслуживания (SPT, shortest processing time), а все требования из множества Н обслуживаются в порядке невозрастания продолжительности обслуживания (LPT, longest processing time).

Лемма 3.9 Для частного случая (3.3), все оптимальные расписания являются каноническими, или могут быть сведены к каноническим расписаниям, если упорядочить первые п требований в расписании по правилу LPT. Доказательство: 1) Покажем, что одно из двух требований, V m или У щ-х-, запаздывает при любом оптимальном расписании. Предположим, что оба требования не запаздывают при некотором оптимальном расписании тг = (тгі, V2n,7T2, У2п-іі тгз, і), гДе запаздывают только требования из частичного расписания 7Г4. Будем рассматривать только оптимальные расписания вида 7Г = (G,H), где все требования j Є Н запаздывают, а все требования і Є G не запаздывают (см. лемму 3.8).

Задача балансировки производственной линии

Одна из первых публикаций [149] по задачам одноколейной железной дороги относится к 70-м годам ХХ-го века. Расширенный обзор литературы по этим задачам можно найти, например, в [124]. Краткий обзор результатов исследования задач с несколькими станциями, на которых поезда могут разъехаться, представлен в работе [147].

Похожая задача рассматривается в работе [60]. В данной задаче последовательность движения поездов в каждом направлении фиксирована, задана безопасная дистанция между парами поездов, которую необходимо соблюдать. Задача является NP-трудной.

В публикации [70] рассмотрена еще одна похожая задача, которая имеет следующие отличия от STRSP2: поезда могут пропускать другие поезда между сегментами, т.е. не вы полняется уСЛОВИе "ДЛЯ Любых І Є N[ И j Є N z ВЫПОЛНЯеТСЯ С{ Sj или Cji Si"; - веса Wji и директивные сроки dy не рассматриваются; - рассматриваются другие целевые функции и подходы к решению. Также похожая задача возникает на речном транспорте и связана с проходом кораблями цепочки шлюзов. Если в каждом шлюзе может находиться не более одного судна, и ширина канала не позволяет судам разойтись, то получим задачу STRSP2. Задача оператора шлюза рассмотрена в работе [66], в которой рассматривается один шлюз с фиксированным временем его прохождения. При этом одновременно несколько судов могут находится в шлюзе. Для каждого судна задано время прибытия к шлюзу. Критерий оптимизации - минимизация суммарного времени ожидания судов в очереди. В работе [66] представлен алгоритм динамического программирования решения данной задачи и некоторых ее обобщений. Трудоемкость представленного алгоритма - 0(п5) операций. Данная задача может быть сведена к одноприборной задачи обслуживания требований "блоками" 1\р — batch; Ъ = n; rf,pi = р\ J WjFj [66]. Сведение STRSP2 к одноприборной задаче теории расписаний Q Введем обозначения: ртах = max {pq} и Р = pq. q=l,2,...,Q q=i Лемма 3.10 Пусть для поезда j Є N[ время прибытия на станцию назначения определяется как Cj = Sj + Р, а поезд і Є N[ - следующий за ним поезд. Тогда существует допустимое расписание, в котором Si = max{?v,SV +Pmax}7 СІ = Si + P, т.е. поезд г начинает движение -78 со станции отправления в момент max{?v,Sj/ + pmax} и движется без остановок. Доказательство: Пусть Sq-,, Sq,q = 1,2,... ,Q - моменты начала прохождения отрезка q поездами j и і соответственно. Чтобы доказать допустимость рассматриваемого расписания, достаточно показать, что Sq, Sq, + pq,q = 1,2,... ,Q, т.е. поезд і начинает движение по сегменту q, ко q-1 q-1 гда поезд j уже прошел его. Имеем Sq, = Sj + Pi и Sq = Si + 2 Pi = 1=1 1=1 q-l max{ri ,Sj +Pmax} + Pi Sq, + pq, т.е. лемма верна. П i=i Лемма 3.10 определяет периодичность отправления поездов с одной станции, если в расписании они следуют друг за другом. Необходимо отметить, что max{?Y, Sy + рш&х} самый ранний из возможных моментов отправления для поезда і , т.к. для участка пути q величина pq = pmax- Получаем Sq = Sq, +pq и, следовательно, \Cj — CV pm%x для любых поездов j ,i , принадлежащих одному из множеств N[ или N z.

Из Леммы можно сделать также следующий вывод. Для указанных выше целевых функций существует оптимальное расписание, при котором поезда движутся без остановок, т.е. начав движение во время Sj поезд j прибывает на станцию назначения во время Cj = Sj + Р. Далее мы будем рассматривать только расписания данного вида.

Лемма 3.11 Для любых двух поездов j и г , принадлежащих одному из множеств N[ или Щ выполняется \Sj — Si \ pmax и \Cj — Су\ рШах Пусть последовательность поездов (j[,ji 2,...,j n) задает очередность движения поездов между станциями. Очевидно, что допустимому расписанию соответствует одна и только одна последовательность поездов. Таким образом, оптимальное расписание соответствует оптимальной последовательности поездов. Для заданной последовательности расписание можно построить следующим образом: