Беллман Р. Прикладные задачи динамического программирования (2013) (1246769), страница 30
Текст из файла (страница 30)
Рассмотрим 1ч' различных детзлей, которые должны пройти последовательную обработку на двух мзшинзх. Нз каждой стадии процесса каждая машина может обрабатывать лишь одну деталь. Лопустии, что порядок прохождения деталями обработки не может быть изменен после начала процесса. Лля каждой де~али задано время обработки на каждой машине. В каком порядке следует подавать детали на первую машину, чтобы минимизировать суммарное время, необходимое для обработки всех деталей? 43.
МАТЕМАТИЧЕСКАЯ ПОСТАНОВКА ЗАДАЧИ Пусть а; — время обработки г-й детзли нз первой машине, Ь; — время обработки Рй детали на второй машине. Процесс протекае~ следующим образолк Летали располагаются в некотором порядке, например 1, 2, , АГ, что схематически изображено на рнс. 52. После того как первая деталь гтааала г Рис.
52. прошла через машину 1, она подзется на машину 2. Как только машина 1 кончает обработку первой детали, машина 2 начинает ее обработку. Машина 2 не может приступить к обработке второй детали, пока она полностью не закончит обработку первой. Задача состоит в том, чтобы установить порядок запуска деталей в обработку, минимизирующий суммарное время простоя второй машины в ожидании деталей от первой машины. Сложность этой задачи являегся следствием того факта, что различные детали требуют разного времени обработки на машинах.
192 сглажиВАиие и состАиление Расписаний (гл. 1и Пусть х! — период простоя второй машины перед тем, как на нее поступает 1-я деталь. (3.108) Имеют место следующие рекуррентные соотношения х,=ан ! ха=шах(а,+а,— Ь, — хь О), х,+хя —— шах(а,+а, — Ьн а ), з 2 2 х,=шах(~~ а; — ~ Ь; — ~~ хп О), 1=1 1=1 1=! т з я х, + х, + ха = птах ! 'У', а; — ~ Ьо ~ ', а! †а,) ! =1 1=1 (3.109) и по индукции х ~ч~ х;= тпах К„, 1 л !т (3.110) я л — 1 К„= ~ аа — ~ ЬР (3.1 1 1) 1=1 44.
ПОДХОД С ТОЧКИ ЗРЕНИЯ ДИНАМИЧЕСКОГО ПРОГРАММИРОВАНИЯ Введем следующую функцию: у(ан Ь„аи Ьи ..., ал,, Ь, 1) — время, необходимое для обработки АГ деталей при условии, что вторая л1ашина начинает работать на 1 единиц времени позже первой, (3 112) аь Ь; — время, необходимое для обработки !-й детали соответственно на первой и второй машинах, и при этом используется оптимальная перестановка деталей. Мы хотим найти перестановку деталей, которая минимизировала бы выражение (3.110).
Хотя этого можно достичь и прямыми методами с помощью приведенных выше рассуждений, будет поучительно использовать метод функциональных уравнений, что мы и сделаем. 451 ОпРгделе1ше Оптик!тльной пеРест \поз!и 1йч где +птах(1 — ан 0) — а,, О] = + !пах [!пах(1 — ан 0), а — Ь;]= +шах [1 — ан а, — Ь;, О]= — а;-1-шах [1, а;+аг — Ьн а!]= — а, -1- вах [1, гпах [а!+ а, — Ьн а;Ц. (3.116) 1; =Ь -1- !! l =ь,+ = Ьу -т=Ьг+ вах [Ь! Ь; — а Ь вЂ” а. ! / Ь вЂ” а ! !' Ь,— а; Теперь мы видим, что если вах [а;+ аг — Ьп а;](шах [а!+ а! — Ьр аг], (3116) то 1-ю и /-ю деталь имеет смысл поменять местами.
Этот критерий может быть переписан в виде а! + а, — ' гпах [ — Ьн — ау] ( а! + от+ + птах [ — Ьр — а;]. Таким образом, мы сравниваем о) шах [ — Ьн — аг] и шах[ — Ьь — а;]. (3Л17) (3.118) 45. ОПРЕДЕЛЕНИЕ ОПТИМАЛЬНОЙ ПЕРЕСТАНОВНИ Чтобы в соответствии с предыдушим результзтом определить оптимальную перестановку, нужно действовать следующим образом. ") Перестановка необходима, если пни [Ьн от[~поп [Ь, а!], отктда непосредственно следует данное в ф 45 простое правиао.
(Прил!. ред.) 7 Р, Беллмен. С. Дгеартс Если машины начинаюг обрабонсу с 1-й дегали, то мы получаем функшгональное уравнение 1(а„Ь1, а„, Ь„..., а „Ь ., 1) = =пни[а,+У(а„Ь„ат, Ьи .. О, О, ..., а, Ь; Ьг+ вах (1 — ан 0))], (3.113) где на месте пары (ан Ь;) стоит пара (О, 0). Чтобы из это!о соотношения получить оптимальную перес!ановку, поменяем местами две детали. Тогда, обрабатывая сначала г-ю, а затем /-ю деталь, получим: Г"(аг, Ьн а,, Ьи .. а ., Ь б 1)= =а! — , 'а,-'-У'(а„Ь„..., О, О, ..., аел Ь; 10), (3.114) 194 Ггллживлнии и состлвлвиив РлсписАний 1Гл.
и! 1. Записагь знзченпя и! и Ь,. в двух вертикальных колонках !таблица 3.6). Таблица 36 а. Л. ! а, а. М~ Ьм 46. ПРИМЕР Рассмотрим следующий пример: ! 1 3 4 ЗО 6 2 2. Отыскать среди значений а; и Ь; наименьшее. 3. Если таковым окажетса одно пз ап поставить соответствующую деталь первой. 4. Если эло Ь; — поставить сооаветствующую деталь последней. 5.
Вычеркнуть оба значения а; и Ьг из списка. 6. Повторять этот процесс с йл — 2 ос!авшичися величинами. 7. В случае нескольких минимальных элементов для определепносги выбрать деталь с меньшим номером. Когда а! = Ьп упорядочивать дегали по значению ап 196 471 зхкл!Очвннн На первом шаге мы имееж ю 4 зо ! 4 ЗО 6 2 На следующем шаге к ! а,, ! ь,. 3 4 зо ! 2 4 30 6 4 Теперь мы видим, что о~пимальной перестановкой будет (б, 1, 4, 3, 2). 47. ЗАКЛЮЧЕНИЕ В этой главе мы ставили перед собой цель показать, что ряд задач составления расписаний, одни из коз орых дейсгвительно называются задачами составления расписаний, а другие маскируются под названием задач сглаживания, замены оборудования и управления запасами, могу~ быль реп ены методами динамического програиьшрования.
Еольшинство из этих задач сводится к несложному машинному счету, в других же задачах этого класса метод функциональных уравнений позволяет найти явные вырви<ения для оптимальной политики и функции дохода. Мы уже подчеркивали ранее, что одна нз важнейших причин, по которой мы обратились к этим простым моделям экономических процессов, состоит в точ, что полученные решения помогают получиаь приближенные политики в более сложных моделях. Кроме гого, анализ чувствигельности этих реп,ений приведет нас к построению более общих моделей.
7' 196 СГЛАЖИВАНИЕ И СОСТАВЛЕНИЕ РАСПИСАНИЙ [ГЛ. !Н КОММЕНТАРИИ И БИБЛИОГРАФИЯ 9 1. Рассматриваемому вопросу посвящено большое число работ. Заинтересованному читателю лгы рекомендуем следующие работы: К. В е11гп а п, Оупаппс Ргойгапгш!ИЕ, РПпсе!оп Опщегя!у Ргеьь, Рппсе1оп, Меж 7егьеу, 1957 !русский перевод: Р. Б ел лман, Линамическое программирование, ИЛ, 1960!. К. В с!1гп а п, Майспга!ка! аьресы о1 ьсйебойпй йеогу, 1. Бос. 1пбаьг.
Арр1. Май., чо1. 4, !956, рр. 168 — 205. К. Л Аг гож, 5. К а г11п апб Н. 5 с а г 1, 51обгеь !п йе Майсшайса1 ТЬеогу о1!Итеп!огу апб Ргобнсггйп, 51ап1огб, Са1г!огп!а, 1958. Кроме того, ряд работ по этим вопросам, касающихся математической стороны задач, можно найти в выпусках журналов: уоогпа1 о1 йе Орега!1опь Кеьеагси 5ос1е!у о1 Агпег1са, Мапайспгеп! Бе!сисе, Хача! Кеьеагсй Бойгыкь Ооаг!ег1у, Есопогпеггка н эонгпа1 о1 йе 5ос!егу 1ог 1пбньгпа! апб Арр1!еб Майспга11сь. 9 4. Лля изучения некоторых непрерывных вариантов задачи сглаживания см.
главы 4, 5 книги Эрроу, Карлнна и Скарфа, упо- мянутой выше. Перечислиьг некоторые другие статьи: К. В е11пг а и, 1. О11сй ьЬе г 8 апб О. Огоьь, 5оше ргоЫешь !п йе йеогу о1 г1упапнс ргойгашш1пй — а ьшоотйпй ргоЫеш, А 5ос, 1пбаы. Арр!. Май., чо1. 2, 1954, рр. 82 — 89. Е. Н.
В о тч ш а и, Ргобнсйоп ьсйедн1!ИЕ Ьу йс !гапьрог!агщп шсйоб !ог 1гпеаг ргоегашшгпй, Орегаиопь Кеьеагси, чо1. 4, 1956, рр. 100 — 103, А. С1тагпеь, %. %. Соорег апб В. Ме!1оп, Мобе! 1ог ор11ш1г1п8 ргобнс!1оп Ьу ге1егепсеь !о сои ьоггоеа!еь, Есопоше!гка, чо1. 23, 1955, рр. 307 — 323. О. В.
О а и ! э18 апб 5. у о 5 па оп, А Ргобнсйоп БшоогЫпй РгоЫеш, ТЬе КАМО СогрогаНоп, Кеьеак1т Мепгогапбнш КМ-1432, 19о5. А. Н о11гп а п апд %. 1 а с о Ь ь, Бптоой раисгпь о! ргобнсйоп, Мапаеепгеп! Бе!енсе, то!. 1, 1954, рр, 86 — 91. 5. М.
3ойпьоп, 5ецоепйа! Ргобнсйоп р1аппгпй очег йгпе аг пипнпнш сов!, Мапайешсп! 5с1епсе, чо). 3, 1957, рр. 435 — 437, %. К а г н ь Ь апд А. ч' автои у1, Майеша!!са1ргййгашш~пй апб ьегщсе ьсиедв1!пй, Мапайешейг Бе|енсе, чо!. 3, 1957, рр. 140 — 148. Р. Мой!81!а пг апб Р. Нойп, Ргобвсйоп р1апп!пй очег йше апб йе лайте о1 йе ехреста!1оп апб р1апп1пе ЬоПтоп, Есопопге1гка, чо1.
23, !955, рр. 46 — 66. Г. Мог!и, Хо!е оп ап !пчел!огу ргоЫепг, Есопошегпса, то1. 23, 1955, рр. 44? — 450. иоммвнтлРии и БивлиОГРлвия 197 6 11. Задачи аналогичного характера возникают в статистиче- ской механике. Освещение как теоретической, так и вычислительной сторон этих задач можно найти в работе: А %. С а Ь п апг( К. К! И и с Ь 1, ТИеогт о1 Оогпвп %айя !п Огйе. гей 51гистигея — И.
Рагг Арргохггпаиоп (ог Хоптего Тсгпрега1игек, Ниаиея Кекеагс1т ЕаЬогатог!ея, Кекеагсй Керогт, Хо. 177, 1961. ф 12. Задаче о замене оборудования посвищено большое число работ. Традиционные подходы к решению и прикладная сторона вопроса изложены в книге: Т. % Ь г !!и, ТЬе ТИеогу о1)пчептогу Мапаиептепт, Рппсетоп ()гт(- чегяйу Ргеяк, Рппсе1ап, Хечг Юегкеу, 1953. Вариационные методы, использующие непрерывную модель, чи- татель найдет в статье: А. А1с Ь ! а п, Есопов1с Кер1асешепт Ройсу, ТЬе КАХО СогрогаИоп, Керогт К-224, АРМ! 12, 1952. Изложенный в настоящей главе метод описан в статьях: К. В е(1в а п, Ейврпгеп1 гер1асешеп! ройсу, А 5ос.(пйики Арр1. Мат!т., то! 3, 1955, рр.
133 — 136. 5. О г е у 1 и я, А йепега1гхей ейи)увеп! к!ийу, ). Зос. (пйия!, Арр1. Ма!И., чо1. 8, 1960, рр. 42о — 435. Этой задаче посващены также работы: В. 3. Маг 1г я, А Оупаппс Арргоасй !о !Ье РгегИс1юп о1 ))ешапй 1ог Кер1асешеп1 Раг1я. !960 (не опубликовано). Р.
%. 3 от Иге п кои, Ориша! ЗсйейийпК о1 Кер!асептепт апй С!тесйои1 — 1)(; Соврита!гоп Ьу Зиссеякще Арргохгптаиапя, !960 (не опубликовано). О. %. ) о г К е п к о п апй К. К а й п е г, Орипта1 Кер!асетпеп! апй (пяресиоп о( Зтосиакг!саИу Рай)пп Ейщрптепт, 51исИек гп АрРИей РгоЬаЬ)рйу апт) Мапапегпепт Яс!епсе, 51ап(огй, Бтап1огй Сп(ч. Ргев, 1962.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
