Новый алгоритм решения двухмашинной задачи open shop и его приложение к одной задаче маршрутизации

Антонина Храмова

Новый алгоритм решения двухмашинной задачи open shop и его приложение к одной задаче маршрутизации

Задача open shop является классической многостадийной задачей теории расписаний и была впервые рассмотрена в 1976 году Гонзалезом и Сани. В этой работе было доказано, что задача NP-трудна в общем случае, но также был приведён линейный алгоритм решения задачи на двух машинах. С тех пор было предложено несколько алгоритмов для двухмашинной задачи open shop с различными идеями работы и структурными свойствами результирующего расписания. Одним из результатов работы является качественно новый алгоритм решения этой задачи. Задачей open shop с маршрутизацией называют обобщение классической задачи open shop и известной задачи коммивояжёра, в котором работы расположены в вершинах некоторого рёберно-взвешенного графа (транспортной сети), и машине, для того, чтобы выполнить работу, необходимо переместиться в вершину, в которой эта работа находится, за время, соответствующее весу ребра. На начало работы все машины находятся в одной из вершин сети (базе), и после выполнения всех работ они должны вернуться туда же. База может быть фиксированной, то есть, задаваться как часть входа, либо нефиксированной, то есть, определяться в ходе работы алгоритма. Известно, что задача open shop с маршрутизацией с фиксированной базой NP-трудна даже в случае двух машин и двухвершинной транспортной сети, а для вариации с нефиксированной базой единственным результатом полиномиальной разрешимости является алгоритм для случая, если транспортная сеть является деревом. В работе предложен линейный алгоритм для случая, если транспортная сеть является циклом, который является обобщением предложенного алгоритма для классической задачи open shop. Следствиями указанных результатов являются полиномиальная разрешимость двухмашинной задачи open shop с маршрутизацией и нефиксированной базой, во-первых, на кактусе с независимыми временами перемещения, и во-вторых, на произвольном графе с однородными временами перемещения в случае, если задача коммивояжёра на графе транспортной сети решается за полиномиальное время. Также с помощью алгоритма Кристофидеса-Сердюкова доказано существование 1.5-приближённого алгоритма для двухмашинной задачи open shop с маршрутизацией и нефиксированной базой на произвольном графе с однородными временами перемещения.

Математика

Дипломы

Вуз: Новосибирский национальный исследовательский государственный университет (НГУ)

ID: 60920a2ee4dde50001d3c49e

UUID: e6b1a160-8f7b-0139-2ede-0242ac180005

Язык: Русский

Опубликовано: около 3 лет назад

Просмотры: 42

18.84

Антонина Храмова

Комментировать 0

Рецензировать 2

Скачать - 299,3 КБ

Поделиться работой

МИНИСТЕРСТВО НАУКИ И ВЫСШЕГО ОБРАЗОВАНИЯ РОССИЙСКОЙ ФЕДЕРАЦИИ ФЕДЕРАЛЬНОЕ ГОСУДАРСТВЕННОЕ АВТОНОМНОЕ ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ ВЫСШЕГО ОБРАЗОВАНИЯ «НОВОСИБИРСКИЙ НАЦИОНАЛЬНЫЙ ИССЛЕДОВАТЕЛЬСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ»(НОВОСИБИРСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ, НГУ) Механико-математический факультет Кафедра теоретической кибернетики Направление подготовки 02.03.01 — Математика и компьютерные науки ВЫПУСКНАЯ КВАЛИФИКАЦИОННАЯ РАБОТА МАГИСТРА Храмовой Антонины Павловны Новый алгоритм решения двухмашинной задачи open shop и его приложение к одной задаче маршрутизации «К защите допущена» Заведующий кафедрой, д.ф.-м.н., проф. Ерзин А. И./ Научный руководитель к.ф.-м.н. с.н.с ИМ СО РАН Черных И. Д./ (подпись, МП) « » 2020 г. (подпись, МП) « Дата защиты: « Новосибирск, 2020 » 2020 г. » 2020г.

СОДЕРЖАНИЕ ПЕРЕЧЕНЬ ОБОЗНАЧЕНИЙ 3 ВВЕДЕНИЕ 5 1. Предварительные сведения 9 2. Алгоритмы для задачи O2||Cmax 11 2.1. Алгоритм Гонзалеза-Сани . . . . . . . . . . . . . . . . . . . . . . 11 2.2. Алгоритм Пинедо-Шраге . . . . . . . . . . . . . . . . . . . . . . . 12 2.3. Алгоритм де Верра . . . . . . . . . . . . . . . . . . . . . . . . . . 13 2.4. Алгоритм Сопера . . . . . . . . . . . . . . . . . . . . . . . . . . . 15 2.5. Новый алгоритм . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16 3. Задача Open Shop с маршрутизацией и нефиксированной базой 18 3.1. Алгоритм для задачи на цикле и его доказательство . . . . . . . 18 3.2. Следствия теоремы . . . . . . . . . . . . . . . . . . . . . . . . . . 21 ЗАКЛЮЧЕНИЕ 23 ЛИТЕРАТУРА 25 2

ПЕРЕЧЕНЬ ОБОЗНАЧЕНИЙ Обозн. Расшифровка J Множество всех работ в примере задачи. n Мощность множества J , если явно не указано иного. Jj j-ая работа, Jj ∈ J . Mi i-ая машина, i = 1, 2. aj , bj Операции работы Jj на M1 и M2 соответственно; также длины этих операций. x→y Операция y может быть выполнена только после операции x. `i Нагрузка машины Mi . `max = max `i . dj Длина работы Jj , dj = aj + bj . dmax = max dj . Cmax (S) Длина расписания S для задачи open shop. C Стандартная нижняя оценка на длину расписания для задачи open shop; C = max{`max , dmax }. Ti , Ti∗ Обход и длина оптимального обхода транспортной сети машиной Mi . T∗ T ∗ = T1∗ в случае, если T1∗ = T2∗ . Rmax (S) Длина расписания S для задачи open shop с маршрутизацией. Нижняя оценка на длину расписания для задачи open shop R с маршрутизацией и нефиксированной базой; R = max{`max + Ti∗ , dmax }. S(π) Раннее расписание, строящееся по упорядоченному списку работ π так, как описано в параграфе 2.5. 3

Следующие обозначения используются в трёхместной записи задач теории расписаний ... Обозн. Om Расшифровка ... для m-машинной задачи open shop (на I месте). ROm ... для m-машинной задачи open shop с маршрутизацией. G=X ... для задач с транспортной сетью G структуры X (II). variable − depot ... для задач с нефиксированной базой. Qtt ... для задач с однородными временами перемещения. Rtt ... для задач с независимыми временами перемещения. easy − T SP ... для задач с транспортной сетью, на которой задача коммивояжёра разрешима за полиномиальное время. Cmax Длина расписания для задачи без маршрутизации (III). Rmax Длина расписания для задачи с маршрутизацией. 4

ВВЕДЕНИЕ Задача open shop была впервые рассмотрена в работе [1] и является одной из классических в области теории расписаний. В рамках задачи требуется построить расписание выполнения множества работ несколькими машинами. Каждая машина должна выполнить единственную операцию каждой работы, причём длительность выполнения любой операции известна заранее. Операции одной работы могут быть выполнены в произвольном порядке, в отличие от похожей известной задачи flow shop, в которой каждая следующая машина не может приступить к некоторой работе раньше, чем предыдущая машина закончит её выполнять. Ни одна машина не может выполнять более одной операции за раз, также как и ни одна работа не может выполняться на двух машинах одновременно. Цель задачи — минимизировать длину расписания, равную Cmax , величине, соответсвующей времени завершения последней операции. В традиционной трёхместной системе обозначения задач теории расписаний [2] задача open shop на m машинах обозначается Om||Cmax . Известно, что задача O3||Cmax NP-трудна [1]. Однако оптимальное решение чуть более простой задачи O2||Cmax может быть найдено за линейное время. Существует несколько алгоритмов для поиска этого решения, начиная с уже упомянутой работы Гонзалеза и Сани [1] и продолжая алгоритмами Пинедо и Шраге [3], де Верра [4] и Сопера [5]. Эти алгоритмы и свойства соответствующих расписаний описываются в главе 2 этой работы. Одним из результатов этой работы является новый алгоритм для задачи O2||Cmax . Хотя результирующее расписание по своим свойствам похоже на расписание, получаемое алгоритмом Сопера, новый алгоритм обладает несколькими преимуществами. Во-первых, его описание и доказательство оптимальности значительно проще по сравнению с предложенными Сопером, а 5

во-вторых, этот алгоритм возможно применить для решения более общей задачи — задачи open shop с маршрутизацией. Задача open shop с маршрутизацией впервые представлена в работах [6, 7] и может быть описана следующим образом. Каждая работа расположена в некоторой вершине транспортной сети, задаваемой неориентированным рёберно-взвешенным графом G. Вес ребра — это время, затрачиваемое машиной на перемещение между двумя соответствующими вершинами. Чтобы выполнить работу, машина должна переместиться по рёбрам транспортной сети в вершину, где эта работа находится. Считается, что по одному ребру одновременно может передвигаться неограниченное количество машин. Все машины начинают работу в одной вершине — базе — и должны вернуться в эту вершину по завершению выполнения всех операций. Цель задачи — минимизировать длину расписания Rmax , величину, соответствующую моменту завершения последнего действия некоторой машины, будь то перемещение в базу либо выполнение операции, расположенной в базе. Задача на m машинах обозначается ROm||Rmax . Если в постановке требуется указать структуру X (дерево, цикл и т. п.) транспортной сети G, то используется запись ROm|G = X|Rmax . Таким образом, задача open shop с маршрутизацией является обобщением как классической задачи open shop (если все рёбра траспортной сети нулевого веса), так и метрической задачи коммивояжёра (если все операции нулевой длины), и поэтому задача в общем случае NP-трудна в сильном смысле. Более того, даже “простейший” подслучай этой задачи RO2|G = K2 |Rmax тоже является NP-трудным, как было доказано в первой работе по open shop с маршрутизацией [6]. Другой важный результат в этой связи — FPTAS для этого “простейшего” случая [8], который частично основывается на структурных 6

свойствах оптимального расписания, получаемого по алгоритму ГонзалезаСани. В работе [9] предложены два новых направления исследования постановки с маршрутизацией: 1. Кроме фиксированной базы, то есть заданной по условию, можно также рассматривать нефиксированную базу, то есть определяемую в результате работы алгоритма. Во втором случае используется запись ROm|variable− depot|Rmax . 2. Время перемещений разных машин по одному и тому же ребру не обязательно должно совпадать. В частности, можно рассмотреть однородные времена перемещений, то есть, для любых двух машин Mi1 и Mi2 существует скаляр k > 0 такой, что по любому ребру время перемещения машиной Mi1 в k раз дольше, чем то же время пемещения машиной Mi2 . Также можно говорить о независимых временах перемещения. В трёхместной записи задачи используются обозначения Qtt или Rtt соответственно. Очевидно, что в общем случае задача RO2|variable − depot|Rmax NPтрудна в сильном смысле, поскольку содержит задачу коммивояжёра в качестве подслучая. В работе [9] также доказано, что задача RO2|Rtt, G = tree, variable − depot|Rmax полиномиально разрешима. Однако до сих пор ничего не было известно о сложности задачи RO2|variable − depot|Rmax , или её Qtt- и Rtt-обобщений, в случае, когда соответствующая задача коммивояжёра может быть решена за полиномиальное время в силу особенностей структуры транспортной сети G или её матрицы расстояний. Мы используем обозначение easy − T SP для такой ситуации, по аналогии с [10], где был приведён 34 -приближённый алгоритм для задачи RO2|easy − T SP |Rmax . 7

В работе предложен оптимальный линейный алгоритм для задачи RO2|Rtt, G = cycle, variable − depot|Rmax , из которого можно вывести новый линейный алгоритм для классической задачи open shop, о котором было сказано ранее. Важным следствием этого результата является полиномиальная разрешимость двух задач: RO2|Qtt, easy − T SP, variable − depot|Rmax , что отвечает на поставленный выше вопрос о сложности задачи маршрутизации с условием easy − T SP , и RO2|Rtt, G = cactus, variable − depot|Rmax , что покрывает упомянутый результат из [9]. Также приводится приближённый результат для задачи RO2|Qtt, variable − depot|Rmax . Работа организована следующим образом. В главе 1 приведены некоторые понятия и обозначения, необходимые для последующего изложения. Глава 2 представляет собой обзор всех известных алгоритмов для задачи O2||Cmax со сравнением структурных свойств соответствующих расписаний, который завершается новым алгоритмом. Глава 3 содержит основной результат работы: описание алгоритма для задачи open shop с маршрутизацией и независимыми временами перемещения, его доказательство и следствия о полиномиальной разрешимости связанных задач. 8

1. Предварительные сведения Ниже приведены несколько определений и обозначений, широко распространённых в теории расписаний и активно использующихся в последующих главах этой работы. Через J = {Jj |j = 1, . . . , n} обозначается множество из n работ. Все рассматриваемые в работе задачи сформулированы в системе из двух машин M1 и M2 . Обозначим за aj , bj две операции работы Jj ∈ J , выполняющиеся соответственно машинами M1 и M2 . Иногда с помощью aj и bj мы будем обозначать не только сами операции, но и их длины. Нагрузка машины Mi — это сумма длин всех операций, назначенных на эту машину, обозначается за `i . При этом `max = max `i . Также определим i=1,2 длину j-ой работы dj = aj + bj и величину dmax = max dj . Jj ∈J Для задачи open shop определим её стандартную нижнюю оценку: C = max{`max , dmax }. Никакое допустимое расписание задачи open shop не может быть короче, чем C, а достижение расписанием этой оценки доказывает его оптимальность. Многие алгоритмы для двухмашинной задачи open shop предполагают построение раннего расписания. Это расписание, для которого задан порядок выполнения операций на каждой машине и каждой работе, и в котором каждая операция начинается в наиболее ранний момент, допускаемый этим порядком. Несложно заметить, что такое расписание можно построить за линейное время. Многие обозначения, например, уточняющие особенности постановки той или иной задачи теории расписаний, используются в ходе работы в соответствии с их определением во введении. Некоторые понятия и обозначения 9

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

2. Алгоритмы для задачи O2||Cmax 2.1. Алгоритм Гонзалеза-Сани Первый алгоритм для задачи O2||Cmax был предложен Т. Гонзалезом и С. Сани в работе [1] — в той же, в которой задача была впервые рассмотрена. Основная идея решения в том, чтобы разделить множество работ на два подмножества и по определённому правилу выбрать одну работу, порядок выполнения операций в которой будет отличаться от прочих. В результате составления раннего расписания с учётом этой работы будет получено допустимое и оптимальное решение. Описание алгоритма дано в том виде, как оно приведено в [11]. Алгоритм AGS : 1. Разделить J на два подмножества J1 = {Jj |aj ≤ bj } и J2 = J \ J1 . 2. Выбрать две работы Jp и Jq такие, что ap = max aj и bq = max bj . Jj ∈J1 Jj ∈J2 3. Если ap < bq , то пусть S — раннее расписание с порядком выполнения операций {aj |Jj ∈ J1 \ {Jp }} → {aj |Jj ∈ J2 } → ap на машине M1 и bp → {bj |Jj ∈ J1 \ {Jp }} → {bj |Jj ∈ J2 } на машине M2 , причём операции из одного подмножества выполняются в произвольном порядке, хотя и совпадающим на двух машинах. Для любой работы, кроме Jp , порядок выполнения операций aj → bj . aj |Jj ∈ J1 \ {Jp } bp ap aj |Jj ∈ J2 bj |Jj ∈ J1 \ {Jp } bj |Jj ∈ J2 Рис. 1. Схема раннего расписания S в случае ap < bq . Иначе, пусть S — раннее расписание с порядком выполнения операций 11

aq → {aj |Jj ∈ J2 \ {Jq }} → {aj |Jj ∈ J1 } для машины M1 и {bj |Jj ∈ J2 \ {Jq }} → {bj |Jj ∈ J1 } → bq для машины M2 . Для любой работы, кроме Jq , порядок выполнения операций bj → aj . aq aj |Jj ∈ J2 \ {Jq } bj |Jj ∈ J2 \ {Jq } aj |Jj ∈ J1 bj |Jj ∈ J1 bq Рис. 2. Схема раннего расписания S в случае ap ≥ bq . 4. Output S. Работа Jp в первом случае и работа Jq во втором случае называется диагональной, за расположение её операций в указанном раннем расписании. Заметим, что в случае ap < bq , в силу выбора подмножеств, либо машина M1 простаивает перед выполнением операции ap , либо машина M2 простаивает во время выполнения блока операций работ из множества J2 ; никаких других простоев в расписании нет. В первом случае, длина расписания Cmax (S) = max{`2 , dp }, а во втором имеем Cmax (S) = `1 . Так или иначе, Cmax (S) = C, а значит, решение оптимально. Аналогичные рассуждения верны и для случая ap ≥ bq . 2.2. Алгоритм Пинедо-Шраге Этот алгоритм был представлен в 1982 г. математиками Пинедо и Шраге. Если в алгоритме Гонзалеза-Сани мы использовали ранние расписания, то здесь строится плотное расписание. В нём для машины Mi задан упорядоченный список Li = (j1 , j2 , . . . , jn ) неповторяющихся индексов, каждый из которых соответствует операции некоторой работы Jjk , k = 1, . . . , n. В любой момент времени t, в который расписание на отрезке [0, t] уже построено, а 12

машина Mi простаивает, на неё назначается первая доступная операция из списка Li . Алгоритм AP S [3, теорема 2.1.1]: 1. Выбрать работу Jk с самой длинной операцией. Не умаляя общности считаем, что это операция bk . 2. Построить плотное расписание S такое, что список L1 начинается с k, а список L2 заканчивается индексом k — то есть, операция bk откладывается настолько долго, насколько это возможно. Все остальные операции могут располагаться в списке в любом порядке. 3. Output S. В таком расписании только одна операция может выполняться после простоя: ведь если машина Mi простаивает до того, как выполнена операция работы Jj , то другая машина должна была выполнять свою операцию работы Jj во всё время простоя на машине Mi ; иначе работа Jj была бы доступной раньше, что привело бы к противоречию с плотностью расписания. Доказательство оптимальности решения легко следует из этого его свойства и выбора операции bk . 2.3. Алгоритм де Верра В алгоритме де Верра [4], вместо того, чтобы определять порядок выполнения для каждой операции, множество всех работ J разбивается на три непересекающихся подмножества, и порядок выполнения определяется для этих самых подмножеств. То есть, в отличие от алгоритма Гонзалеза-Сани, в котором тоже происходит разделение всех работ на три подмножества, в 13

алгоритме де Верра допускается разный порядок выполнения операций на двух машинах в рамках одного подмножества. Следующее описание алгоритма де Верра может быть найдено в [12]. Алгоритм AW : 1. Найти индекс s ≥ 2 некоторой работы такой что s−1 P dj ≤ `max и j=1 s P dj > j=1 `max . 2. Определить три подмножества работ: J1 = {J1 , J2 , . . . , Js−1 }, J2 = {Js }, and J3 = {Js+1 , . . . , Jn }. Несложно убедиться в том, что P dj ≤ `max , k = 1, 2, 3. Jj ∈Jk P P 3. При необходимости перенумеровать подмножества так что aj ≥ bj J ∈J J ∈J j 1 j 2 P P и bj ≥ aj . Jj ∈J1 Jj ∈J3 4. Построить раннее расписание S такое, что у машины M1 порядок выполнения подмножеств J1 → J2 → J3 , а у машины M2 этот порядок J2 → J3 → J1 . Порядок выполнения операций внутри каждого подмножества произвольный. Для любой работы Jj ∈ / J1 порядок выполнения операций соответствует aj → bj , а для любой другой работы порядок b j → aj . 5. Output S. Как и в алгоритме AGS , из построения подмножеств следует, что либо машина M1 простаивает во время выполнения операций из подмножества J3 , и тогда машина M2 вообще не простаивает и Cmax (S) = `2 , либо машина M2 простаивает во время выполнения операций из подмножества J1 , откуда следует Cmax (S) = max{dmax , `1 }. В обоих случаях Cmax (S) = C, что и требуется. 14

2.4. Алгоритм Сопера В расписании Сопера сохраняется идея выбора диагональной работы, но её роль в построении этого расписания в некоторым смысле обратная. Если в алгоритме AGS сначала выбиралась диагональная работа, а потом вокруг неё строилось всё остальное расписание, то алгоритм Сопера производит циклический поиск по всем расписаниям типа flow shop для n − 1 из n работ, где единственная нерассматриваемая работа меняется на каждой итерации. Как только в результате такого поиска будет найдено “хорошее” flow shop расписание, недостающая работа добавляется в него в качестве диагональной. Далее в этом параграфе считаем Jj = Jj mod n . За St0 обозначим переста- новочное расписание для двухмашинной задачи flow shop на множестве работ J \ {Jt−1 } с порядком работ (Jt , Jt+1 , . . . , Jn , J1 , . . . , Jt−2 ). Индекс k(t) соответствует критической работе в расписании St0 , то есть, такой работе, что k(t) t−2 P P 0 aj + bj . Cmax (St ) = j=t j=k(t) S Алгоритм A [5]: 1. Полагая t = 1, вычислить Cmax (St0 ). 2. while Cmax (St0 ) > max{`1 , `2 } or t ≤ k(1) do (a) Переопределить t ← t + 1. 0 (b) Вычислить Cmax (St0 ) = Cmax (St−1 )−at−1 +bt−2 , поскольку критический путь остаётся таким же. 3. Построить расписание S для задачи O2||Cmax по расписанию St0 , выполняя операцию bt−1 до начала выполнения всех операций в St0 на машине M2 , а операцию at−1 — после завершения выполнения всех операций в St0 на M1 . 15

4. Output S. Корректность алгоритма AS и оптимальность соответствующего расписания доказывается рядом технических выкладок и вытекает из нескольких очевидных неравенств, основывающихся на устройстве просматриваемых перестановочных flow shop расписаний. 2.5. Новый алгоритм Для списка работ π = (J1 , J2 , . . . Jn ) определим раннее расписание S(π) такое, что: (a) у машины M1 порядок выполнения операций a2 → a3 · · · → an → a1 ; (b) у машины M2 порядок выполнения операций b1 → b2 → b3 · · · → bn ; (c) для любой работы кроме J1 порядок выполнения операций aj → bj . Обозначение π +k используется для смещённого списка (Jk , Jk+1 , . . . , Jn , J1 , . . . , Jk−1 ). Рассмотрим следующий алгоритм для задачи O2||Cmax . Алгоритм A: 1. При необходимости перенумеровать машины таким образом, чтобы выполнялось `1 ≤ `2 . 2. Пусть π = (J1 , J2 , . . . Jn ) — произвольный список работ. Построить расписание S(π). 3. Если Cmax (S(π)) = C, то Output S(π). Иначе, (a) Пусть Jk — работа, которая выполняется после последнего построя на машине M2 в расписании S(π). 16

(b) Output S(π +k ). Как в подходе Гонзалеза и Сани, ключевой элемент в построении расписания — выбор диагональной работы. Однако в отличие от алгоритма AGS , в котором задаётся конкретное правило выбора этой работы, не зависящее от дополнительных построений, здесь диагональная работа сначала выбирается произвольно, а затем выбирается на основе построенного расписания. Структура результирующего расписания совпадает со структурой расписания, получающегося в результате работы алгоритма AS , но мы строим расписание иначе: здесь не требуется ни построение flow shop расписаний, ни циклический поиск по множеству расписаний. Теорема 1. Алгоритм A возвращает расписание длины C за линейное время O(n). Доказательство этой теоремы напрямую следует из доказательства теоремы 2, изложенного в следующей главе. 17

3. Задача Open Shop с маршрутизацией и нефиксированной базой 3.1. Алгоритм для задачи на цикле и его доказательство Напомним, что времена перемещений в задаче open shop с маршрутизацией называются однородными, если веса рёбер транспортной сети отличаются для разных машин домножением на скаляр. Пусть G — циклическая транспортная сеть для двухмашинной задачи open shop с маршрутизацией и однородными временами перемещения. За Ti обозначим оптимальный обход этой транспортной сети машиной Mi , i ∈ {1, 2}, а за Ti∗ — длину этого обхода. Для задачи open shop с маршрутизацией с нефиксированной базой определим нижнюю оценку R = max{`i + Ti∗ , dmax }. Разумеется, если времена перемещений двух машин совпадают, то T1∗ = T2∗ , и эту величину мы будем обозначать за T ∗ . Рассмотрим следующее обобщение Алгоритма A для задачи RO2|Rtt, G = cycle, variable − depot|Rmax . Алгоритм A0 : 1. Пусть π = (J1 , J2 , . . . Jn ) — список работ в порядке их появления при обходе цикла G. Полагаем, что работа J1 расположена в вершине v. Выбрать вершину v в качестве базы. 2. При необходимости перенумеровать машины таким образом, чтобы выполнялось `1 + T1∗ ≤ `2 + T2∗ . 3. Построить расписание S(π). 4. Если Rmax (S(π)) = R, то Output S(π). Иначе, 18

(a) Пусть работа Jk , расположенная в вершине u, выполняется после последнего построя на второй машине в расписании S(π). (b) Выбирая u в качестве базы, Output S(π +k ). Теорема 2. Алгоритм A0 возвращает расписание длины R за линейное время O(n). Доказательство. Заметим, что если Rmax (S(π)) > R, то машина M2 простаивает. Действительно, если не простаивает M2 , то должна простаивать M1 . По определению S(π), машина M1 может простаивать только до начала выполнения операции a1 , что возможно только если операция b1 выполняется во время простоя. Тогда Rmax (Sπ ) = max{d1 , `2 + T2∗ } ≤ R, противоречие. Пусть t — момент времени, в который заканчивается последний простой на машине M2 , который также является моментом начала выполнения операции bk для некоторого индекса k ∈ {1, . . . , n}. Рассмотрим расписание S 0 (π), полученное сдвигом операций b1 , . . . , bk−1 в расписании S(π) вправо так, что машина M2 простаивает только до выполнения операции a2 , как показано на рис. 3. Длина расписания остаётся той же. Определим блоки (упорядоченные множества операций и времён перемещений между соответствующими вершинами) A1 , A2 , B1 , и B2 следующим образом: A1 = → a2 → · · · → ak ; A2 = → ak+1 → · · · → an → a1 ; B1 = b1 → · · · → bk−1 → ; B2 = bk → · · · → bn → . Стрелки обозначают соответствующие времена перемещений. ∆ 0 A1 A2 → a2 → · · · → ak−1 → ak → ak+1 → · · · → an → a1 b1 → b2 → · · · → bk−1 → B1 bk → bk+1 → · · · → bn → t B2 Рис. 3. Схема расписания S 0 (π) 19 Rmax (S 0 (π))

Пусть ∆ — момент, в который начинается выполнение блока B1 , так что Rmax (S 0 (π)) = ∆ + `2 + T2∗ . Отметим, что выполнение блока A2 заканчивается в момент `1 + T1∗ , и `1 + T1∗ ≤ `2 + T2∗ влечёт ∆ ≤ Rmax (S 0 (π)) − (`1 + T1∗ ). Рассмотрим расписание, полученное перестановкой блоков A2 с A1 и B2 с B1 , как показано на рис. 4. A2 A1 → ak+1 → · · · → an → a1 0 → a2 → · · · → ak−1 → ak bk → bk+1 → · · · → bn → b1 → b2 → · · · → bk−1 → B2 B1 ∆ Rmax (S 0 (π)) Рис. 4. Результат перестановки блоков Допустимость этого расписания следует из указанного выше неравенства ∆ ≤ Rmax (S 0 (π)) − (`1 + T1∗ ), если только операции работы Jk не накладываются друг на друга, и на самом деле, это в точности расписание S(π +k ). Если всё же операция bk заканчивается позже, чем начинается операция ak , то мы получаем расписание S(π +k ) сдвигом операции ak вправо соответствующим образом. По построению расписания, машина M2 не простаивает, а M1 может простаивать только перед выполнением ak , так что Rmax (S(π +k )) равна либо длине работы Jk , либо Rmax (S(π +k )) = max{`1 + T1∗ , `2 + T2∗ } ≤ R. Отсюда следует Rmax (S(π +k )) = R, что и требовалось. Поскольку раннее расписание может быть построено за линейное время, алгоритм A0 также возвращает решение за линейное время. Отметим, что задача O2||Cmax является частным случаем задачи RO2|variable−depot|Rmax , если положить, что все времена перемещений равны нулю. Значит, алгоритм A, изложенный в предыдущей главе, напрямую следует из только что описанного алгоритма A0 . 20

3.2. Следствия теоремы Основной принцип работы алгоритма A0 состоит в построении раннего расписания такого, что порядки выполнения операций на двух машинах совпадают с точностью до циклической перестановки работ, и обе машины следуют одному и тому же оптимальному обходу транспортной сети. В связи с этим далее мы рассмотрим два подслучая задачи RO2|Rtt, variable − depot|Rmax , полиномиальную разрешимость которых легко доказать с использованием алгоритма A0 . Нетрудно заметить, что если времена перемещений однородны, то любой оптимальный обход первой машиной M1 также является оптимальным обходом и для второй машины M2 . Поэтому, если дана транспортная сеть G с условием easy − T SP , то простая модификация алгоритма A0 возвращает решение за полиномиальное время. Следствие 3.1. Задача RO2|Qtt, easy − T SP, variable − depot|Rmax разрешима за полиномиальное время O(n + tT SP ), где tT SP — время, необходимое для решения задачи коммивояжёра на траспортной сети G. В случае, если для задачи коммивояжёра имеется приближённое решение, мы можем использовать алгоритм A0 , чтобы получить приближённое решение такой же степени для задачи RO2|Qtt, variable−depot|Rmax . В частности, применяя алгоритм Кристофидеса-Сердюкова [13, 14], мы получаем следующее Следствие 3.2. Для задачи RO2|Qtt, variable − depot|Rmax существует 32 приближённый алгоритм. Алгоритм A0 можно применить только если оптимальные обходы для машин M1 и M2 совпадают. Однако в общем случае это неверно: именно, когда 21

времена перемещений независимы и структура графа G не уточняется. В этом следствии, структура графа G обеспечивает совпадение тех самых оптимальных обходов. Кактусом назовём граф, у которого все блоки — циклы либо рёбра. Следствие 3.3. Задача RO2|Rtt, G = cactus, variable − depot|Rmax разрешима за линейное время O(n). Наконец, если времена перемещений независимы, имеет место следующий результат. Теорема 3. Для задачи RO2|Rtt, variable − depot|Rmax , пусть τ — обход транспортной сети G, найденный за полиномиальное время, такой что длина этого обхода τ ∗ = ρi · Ti∗ для некоторого ρi , i ∈ {‘1, 2}. Тогда для задачи существует алгоритм A такой, что ∗ Rmax (SA ) ≤ max{`i + ρi · Ti∗ , dmax } ≤ max(ρ1 , ρ2 ) · Rmax . i=1,2 22

ЗАКЛЮЧЕНИЕ Задачи теории расписаний с маршрутизацией часто возникают в приложениях, поскольку, в отличие от классических моделей, учитывают задержки при выполнении операций различными машинами. Однако описанная в работе постановка — это лишь один из способов учитывать такие задержки. Например, в [15] предлагается перемещать не машины, а работы между неподвижными машинами, что на самом деле очень похоже на рассматриваемую нами постановку, поскольку в open shop всегда можно менять местами работы и машины. Другой известный подход [16] предполагает объединение работ в группы и задания машинам времени, которое они тратят на переключение между этими группами. В терминах нашей постановки это соответствует расположению группы работ в одной вершине транспортной сети, а вес любого ребра соответствует времени переключения между группами. Однако важным отличием этих подходов от рассматриваемой постановки является отсутствие базы. В представленной работе был предложен линейный алгоритм для задачи RO2|Rtt, G = cycle, variable − depot|Rmax и показана полиномиальная разрешимость для задач RO2|Rtt, G = cactus, variable−depot|Rmax и RO2|Qtt, easy− T SP, variable−depot|Rmax . Последний результат интересен в связи с тем, что, согласно нему, задача open shop с маршрутизацией и нефиксированной базой сложна лишь постольку, поскольку сложна задача коммивояжёра на соответствующей транспортной сети. Это отличает задачу от её вариации с фиксированной базой, где NP-трудность доказана даже для траспортной сети G = K2 , на которой задача коммивояжёра решается, конечно же, полиномиально. То же справедливо и для описанного выше подхода [16], в котором база отсутствует вовсе, но для простейшего случая из двух машин и двух групп работ 23

задача также NP-трудна. Таким образом, результат демонстрирует важность базы и её свойств в постановке задачи. Как было упомянуто во введении, для простейшего случая задачи open shop с маршрутизацией RO2|G = K2 |Rmax существует FPTAS, который частично основан на структурных свойствах оптимального расписания для классической задачи open shop, получаемого по алгоритму Гонзалеза-Сани. Было бы интересно посмотреть, могут ли структурные свойства расписания, полученного алгоритмом A, быть использованы в рамках этого исследования. Одним из ключевых свойств алгоритма A является то, что диагональная работа не определяется заранее, но выбирается в процессе построения расписания. В то же время, несложно понять, что в оптимальном расписании S(π) для некоторого списка работ π не всякая работа может выполнять роль диагональной. Это поднимает естественный вопрос о том, какими свойствами может определяться работа, которая может быть диагональной, и как можно было бы её найти независимо от соответствующего ей расписания, или возможно ли даже построить оптимальное расписание вокруг работы, которая заранее была определена как потенциально диагональная. 24

ЛИТЕРАТУРА [1] Gonzalez T. F., Sahni S. Open shop scheduling to minimize finish time // J. ACM. –– 1976. –– Vol. 23, no. 4. –– P. 665–679. [2] Chapter 9. Sequencing and scheduling: Algorithms and complexity / Eu- gene L. Lawler, Jan Karel Lenstra, Alexander H.G Rinnooy Kan, David B. Shmoys // Logistics of Production and Inventory. –– Elsevier, 1993. –– Vol. 4 of Handbooks in Operations Research and Management Science. –– P. 445–522. [3] Pinedo M., Schrage L. Stochastic shop scheduling: a survey // Deterministic and stochastic scheduling / Ed. by M. A.H Dempster, Jan Karl Lenstra, Alexander H.G Rinnooy Kan. –– Springer, Dordrecht, 1982. –– Vol. 84 of NATO Advanced Study Institute Series. –– P. 181–196. [4] de Werra D. Graph-theoretical models for preemptive scheduling // Advances in Project Scheduling. –– 1989. –– P. 171–185. –– Access mode: http://infoscience.epfl.ch/record/88562. [5] Soper A. J. A cyclical search for the two machine flow shop and open shop to minimise finishing time // Journal of Scheduling. –– 2013. –– nov. –– Vol. 18, no. 3. –– P. 311–314. [6] Averbakh I., Berman O., Chernykh I. A 6/5-approximation algorithm for the two-machine routing open-shop problem on a two-node network // European Journal of Operational Research. –– 2005. –– Vol. 166, no. 1. –– P. 3–24. [7] Averbakh I., Berman O., Chernykh I. The routing open-shop problem on a network: complexity and approximation // European Journal of Operational Research. –– 2006. –– Vol. 173, no. 2. –– P. 531–539. 25

[8] Кононов A. B. О цеховой задаче открытого типа на двух машинах с маршрутизацией в двухвершинной сети // Дискретный анализ и исследование операций. — 2012. — Т. 19, № 2. — С. 54–74. [9] Chernykh I. Routing open shop with unrelated travel times // Discrete Optimization and Operations Research — 9th International Conference, DOOR 2016, Vladivostok, Russia, September 19-23, 2016, Proceedings. –– 2016. –– P. 272–283. [10] Chernykh I., Kononov A. V., Sevastyanov S. Efficient approximation algorithms for the routing open shop problem // Computers & OR. –– 2013. –– Vol. 40, no. 3. –– P. 841–847. [11] Brucker P. Scheduling algorithms. –– Springer-Verlag Berlin Heidelberg, 2007. –– ISBN: 978-3-540-69515-8. [12] Esswein C., Billaut J.-C., Strusevich V. A. Two-machine shop scheduling: compromise between flexibility and makespan value // European Journal of Operational Research. –– 2005. –– dec. –– Vol. 167, no. 3. –– P. 796–809. [13] Christofides N. Worst-case analysis of a new heuristic for the travelling salesman problem. –– Report 388, Graduate School of Industrial Administration, Carnegie-Mellon University, Pittsburg, PA, 1976. [14] Сердюков A. О некоторых экстремальных обходах в графах // Управляемые системы. Сб. науч. тр. — 1978. — Т. 17. — С. 76–79. [15] Complexity results for flow-shop and open-shop scheduling problems with transportation delays / Peter Brucker, Sigrid Knust, T. C. Edwin Cheng, Natalia Shakhlevich // Annals of Operations Research. –– 2004. –– no. 129. –– P. 81–106. 26

[16] Kleinau U. Two-machine shop scheduling problems with batch processing // Mathematical and Computer Modelling. –– 1993. –– mar. –– Vol. 17, no. 6. –– P. 55–66. 27

Рецензии:

Авторизуйтесь, чтобы добавить рецензию

Рецензия от Антонина Храмова

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

около 3 лет назад

Рецензия от Антонина Храмова

Рассматриваемая в работе двухмашинная задача орел shop была сформулирована и решена в статье Гонзалеза и Сани в 1976. В этой задаче требуется составить кратчайшее расписание выполнения операций множества работ двумя машинами: каждая машина выполняет по одной операции для каждой работы, время выполнения известно для каждой операции, при этом порядок операций не задан, но операции одной машины ил...

около 3 лет назад

Отзывы:

Авторизуйтесь, чтобы оставить отзыв