Методы оптимизации в задачах планирования тема автореферата и диссертации по математике, 01.01.09 ВАК РФ

:■) :Л ЪЪ

" САНКТ-ПЕТЕРБУРГСКИЙ

Т0С7ДЛРСТВЕ!ШЫЙ УНИВЕРСИТЕТ

На правах рукописи ТЕМЩШЛ Лариса Александровна

И В Т О Д H, ОПТИМИЗАЦИИ В ЗАДАЧАХ. ПЛАНИРОВАНИЯ

01.01.09 - Матекатаческая квбзрпвтйка

АВТОРЕФЕРАТ диссертации па соискание ученой степени кандидата физико-математических наук

САНЯГ-ПЕГКРПТРГ 19 9 2

/

Тйботл выполнена на кафедре математической статистики и теорги надпжиосги массового обслуживания факультета 1Ш-П7 С'!ГГУ.

Научный руководитель - кандидат йизико-штематических наук В.Ф.Горысовш.

(Мпгоийлькне оппоненты: доктор технических наук.профессор

Р.А.Нелегаш;

кандидат фпзщю-матеыатических наук, доцент К.М.Малов.

Велувпя организация - Вк целительный центр Академии наук Армении.

Зашита состоится 1992 г. в •

4-1 с.. _ мул. на заседании специализированного совета К-ОПЗ.57,16 по присуждению ученой степени кандидата физи-ко-?!птеиат1:чэсглх наук в Санкт-Петербургском государственном университете. А;фэс: Санкт-Петербург, В.О., 10-я ли-нгя, д. 33.

Г- цчссертацяей ммше ознакомиться в читапьном зале Це;гтр'1пыю11 библиотеки СИТ, Университетская наб., ?/9.

Лвг1т;>9гТ».рат разослан

" ( 6 " О-1932 г.

Ученьй секретарь оБтдалпз^рованного с о? о га, г гдадат фиэ.-шг. .наук А В.Ф.Горьково!

! - 1 -

. ' !1 1. ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЦ.

' ! - " 1 ■ ' " " ; Актуальность теми .

, Диссертация посвящена разработка ттекахачвсккх дпя

задач планирования.

. . Замет лов в последнее время возрастание интереса к вопросам оптимального планировании для различных обслуживаю щи сксгьи обуслоачвно существенным цслщкниаи уровня автоматизации ьсах видов человеческой деятельности, в том числе й'улрялч^ик , этой деятельностью. Качество рункцаонироьянип соирвм-аного проазводства во мнйгам опрадаллвтся рвшвнвякп, прцня;..а»т<>:н • на этапах календарного планирования а операторного упр:шиньи. Наряду с улучшением качества планов« релений вое <1олеа злот-кймд становятся требована л к сокращению срокоп, поштопай оперативности я гийкоста управления. ■ ■ ' '

Сущастпуют различные подходи к решению задач .лланаронаняя» ••такие, наирикчр, как пракеншше методов линейного а динамв-чвского программирования, теории игр, ^ор^улирсгок« задач я терминах сетей, В диссертационной работа прндтагаптоя математические модели, основании« на методах теории гра£оя. В частности, разнообразные задачи, возникающие пря аланярогшнда :• производства, составлении графиков осмотра, хранении п транспортировке товаров часто ьогут бить представлены как задача теории графп, тесно срязаннна п гак наянпаямоР "задачей раскраски". Это дает возиочсноеть наглядно иредстпрягь структуру задачи й вид искомого рспания, а так-»« позппляот пойти точное решение задачи янтлятнчеекяг.'И методами.

Применение в диссертации последних разработок ц области

гйяйН'ялт.иэЯ раскраски графов, в частности, точного критерия ь-янимальяости раскраски, дало возможность построить математические уодвли, позволяющие получать точные рвшания поставлен-: в их задач планирования аналитйческяуя методами.

Кроме того, наличие критерия минимальности сделало тарспек-тявным сведение к задаче о минимальной раскраске других теоре-тяччских задач теории гра^лв, таких, капрмер, как изучение структуры связннх, а также критических и минимальных относи-гелг-во связности градов. ;

Актуальность згоЭ теш связана, с ее ва*ядаи прикладными применениями, тйкпул, как решение задач планирования оптималь ч«г по схойчости и надежности сетей. Например, минимальные ►V -сяяэчне гра}а обеспечивают оптимальное решение в задачах планирования сетей, которые трейугт максчмалъной связности с использование» ииняма.т--.ного числа ребер.

Задачи тчтслвпия связности получили наибольшее распрострг ц»»?и* при исследовании свтбй связи в трапспортянх сетей. Мод< •'прсваяие па графах позволяет строить сети, оптиматьяне по т<

яиспокическиу критериям, ».ак живучесть и о^ктивк-сгь. II",п живучестью /явдетаостьп/ сети понимается устойчивость ев Ттчктшонирошпия относительно выхода из строя эле>,'>нтов сети Огспяя вотеиавт интерес к критическим состояниям сети, кото-р>?* исс^адуггсл с поиощъг ".оделнр'»ваяия ня критических я Уй>1 »'пчьрн* отяоситм^о связности графах я изучение их хягчкте-

ПЧ'ПИН,

Ц»>Л*1!> ДЯНПОЙ рЯ^ПТМ б НПО ПТТР^вЯПЯ '.',«Гс."/'!Тй-1

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

Кроме того, в работа проводится конструктивное исследование Д связных, а также критических и ммшдаяьных относительно связности градов, основанное на р«ул штатах Менгера а Ушта a vil но малы ¡0,1 раскраске специально построению градов.

1.?. Основные результаты

Основные результаты диссертации состоят в следу щам.

1, 1}а основе изучения реального производственного процесса поставлена задача об оитшашюй загрузка оборудования; по ней построена ултематаческая модель, объединяющая широкай класс задач планирования в использующая иоваШиие разработки

в области минимальноЛ раскраска градов, ✓

2,'Получено аналитическое ранение .задачи в вида 'оптимального плана загрузки оборудования,

3, Проведено конструктивное исследование 1\ - связных, а такае критических и минимальных относительно связности графов на основании минимальной раскраски специальных графов цепей; подучзнн необходимые н достаточнее усчовин мчнякагь-пости н критичности гра]а относительно связности; доказано, что хро«атичаоков число графов цепей равно их тотности.

i. Созданы алгоритм и программа, осуцестштцип 'яштлалъ-пуп раскраску графа, основанные на необходи\г>м условии крц-трчног-ти.

- 4 - >

5. Созданы алгоритм и программа построения оптдаачьного гитана загрузки оборудования, использующие вышеупомянутаI а горятм (.'пняуальксй раскрасга. 1.4. Научная новизна работы

Отсутствие достаточно точных критериев минимашюсти ра крчски графов привело к тому, что она испольглвалась прайм щастиашг в тех случаях, где валяв» било видеть структуру лачи и решения, а не достигать точности решения, либи на с рачпеичнх массах графов, для которых существовали Крите! мьлимальиости. .' ') ■

Использование последних разработок в это! области, а и* 41 опясп.тв необходимого вида Н, - критического гра|а и 1 ит-ллъной раскраски в тер™.ах взаимосвязанном« классов, по розмокяость эф^гтивно решать производственные задачи 1 построить математическую модель, позволяющую получать опт ».■«1тигой решение аналитическим методом.

Применение минимально£ раскраски графов позволяло так» промети исследование в области связности градов. Посколь р провой лятзратуре основное пяиуяния здесь удалялось ог яям различных характеристик П» - свяэннх, а так*« жрити* тх и гинпу&тьшх относительно связности графов, а иечррг тгктв конструктивную описания сутесгруот топко ляп ма< я 3- связянх градов я 3- нпткгшпих .градов, то /рс^о; о "нал "работа представляет конструктивяне иослсмгрякия г.'ч:

>>*>.Ш"Ю: П КрИТИ7вСКЛХ Д. - СВЯЭПНХ ГрЯ^ОВ ДЛЯ НрОЯЗГОДГ-

П- . Все получекяне рчяультаги здесь .чтитнгп^я иор.т-г и рядагс* яа доказанное теоремы.

1.5. Практическая значимость

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

Задача об оптимальной загрузке оборудования может применяться для оптимального планиропания как в производства так а в других отраслях, где возникают задачи планирорания и рас-; прэделения. , . •.-. ■

Результаты в области связности могут использоваться при разработка оптимальных коммуникационных сетей. / , ' , 1.6Г Методы исследования • • • ''•'-■,■■

- В рлботе использовались методы теории графов, в частности, конструктивные описания различных классов графов в терминах взаимоовязности ах частей, необходимый вид критического гря-|а а минимальная раскраска. '

• 1.7. Алробадия работы -.лг- ,

Результаты работы докладывались на научных семинарах кафедр факультета 1Ш-П7 СП6Г7 и на научных конференциях СШГУ

и НУ. - , - "' • V• .• "'

■ Основные результаты диссартавди опубликованы в 4 работах

. '

2. КРАТКОЕ СОДЕРЖАНИЙ РАБОТЫ. -

Диссертация состоит из введения и 3-х глав. Работа изложена на 96 отраницах, включая 13 рисунков, В конце приведен список литературы - 7 стр. а приложения, содержащие тексты двух программ на языка Паскаль - 28 стр.

Введение содержит материалы, отряжающие состояние каздого.

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

Петя тлрва посвящена физической постановке задачи об оп ги№ч>.нп5 загрузке оборудования, оснораяно!' на изучения реального произюдстгенпого процесса.

Рассматриваемая задача возникает в рамках •»вто-^тизярогаг ной слетг и управления пехом /АСУЦ/ для реализации опэратпп-яо-каландарного планирования.

В цех поступает план, содержащий следующую информацию:

1. Перечень наименований издели". '

2, По каждому ■наикенояанио - об т. ем вотускэ.

Дтл я-готоалеяля изделия одного наименования требуется '»матчить некоторое количество даталеопераппй.

Цех втипочавт я себя определенное число станков различны; чгцrw.il. Кяаднй станок яо'гвт выполнить одну пли пепколтко и">ттИ по обработке деталей. Считаем, что известно время, ^атртивяемол на одну деталеоперацию в зависимости от номера ятоЯ яе тала оперши я, детали в станка, на котором ока вн-чоччячтея. Требуется составите план работы цеха, осуадствж ■ »"гяР. оптмяльную загрузку оборудования, т.е. крою так рао-претить отдельме »тапы обработки деталей мляду отянквмя •!т1б.ч иромл обработки всрго объ«ыа продукции 4цло кичяг/вль-

Задача гтродусгдтпппаот 4 гарнянта постановки, которые оагптлагаяугсп в порядке усложнения.

Н первом мргяпте предпотагачтсч, что проязводогмкпнй лягстпппвпт тхдо?. детали состоит из йдияотр«нч9£ оп

рации, и вреуя, необходимое для её выполнения, одинаково дзш всех деталей. Во втором варианта постановки задачи над кгжД<1Й. С- -й деталью требуется выполнить К I операций по обработке. В третьем варианте время выполнения каждой дат ало люршдкй Ь. у- зависит от несера даталеонерацш я номера станка, на котором ого выполняется. И, наконец, в четвертом вариант" добавляется следующее условно: часть деталей поступая? в обработку через некоторое время от начала производственного процесса.

При рапеняи задачи попользуются методы теопп трэдов, в частности, мити/:льняя рчекраска графов, поэтому в п.З дается описание процесса ггрял^дзкяя раскраска я критерия ее мяня-ыялъпостя. Созданная на основа этого программа, осуществляв-чая мйнт/яльнуч раскраску графов, приведена в Прилотаяйл 1.

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

Пусть X - миоявсио дегалеонвраия.",- У - киожаство ссанков. Так как для кавдой д&тапеопврапип определен перечень станков, на которых опа мо.^ат выполняться, то считаем, что задан даулальяий граф ^ ■=*( XV ) , где отображение ^ У У гаалйоуйт альтернативные варианты обработки дета-

»п. 1Х1*Г,1У1*К.

Обозначим (: ¡1 время рыполнанпя С -й детани на ^ -м стаятся, I ... 7 Г; | ..} К .

Задача 1, Пусть мномстро деталей совпадает с тпокеством дптчле его г-> тай X , я время Ь С! 'СОЛ^Ь датя любых Ь , } , где £ - и'»'ер датата, - номер станка.

_ е -

■ Построй« двудольный грар £ ~(Х О У, Р) . Будем счи-гн?ь',' чт Лйрчшна Х'^ £ X смежна с вершиной у^ £ V , «олр. дз гачвоперацяа можно выполнить на ^ -м станке

По графу Ц' лэстроим реберный граф КС : гсаждому ребру ставим в соответствие вершину 2. ^ £ •#"£ $ ^ераюян/ ¿д-'й...?- кй-/'- 'смежны тогда и только тогдч, когда рк*8хнц сооиветствуюцие им рабра в С, .

. Но графу же построим дополнительный к нему граф и раояраещ>РО>ьздяащльньт образом. / , ,,.; ^сорома Число клааоов

в минимальной раскраске р^афа ЖС* удовлетворяет следующему неравенству;

где .число, равное голачеству наборов вершин '£ X) таких, , и'дагя любого

Щ ¿л \ ^ - несмежна с , , а Г\-чяс

4р, равное количеству наборов вершин ^(/¿х- £ У',?)

'1 , ' Л ' * ч «мм» ** .

таких, что ^X €х , б?/, . а для.любого К^Сг-' нееч^а V I - ^ ,

ВРберем иэ каждого класса минимальной раскраска графа Ч ¿г * -по одной вершине так, чтобы в совокупности эта вершчна образовывали полный подграф ¡~к /К максималь но/. Он будет соответствовать множеству ребер гра'а , тоусрнв'попарно несмежны, т.е. партии одновременно обрабаты вавмых деталей,

Среди множества всех полных подграфов существует мини- _ мальный набор, покрквавдий /V . Обозначим его Г рде /V - число полных подграфов, входящих в этот набор. План загрузки оборудования получаем следующим образом.

- 9 -

Пусть С Fk , 5 ~ , имеет вид >'

fxu' ÍO-liji ' ¿k-»/* i -••/ Л^

Тогда в первую обрабатываемую партии нужно включи. - детали с номерами L i.,..., L и направить их на станки J 1,- , J <t соответственно. Во второй партии обрабатываем детали на станках ftf, соответственно и т.д.

Задача 2. Пусть KT¿ - количество операций, составляющих прочзводствояяый щнсл изготовления t -й детали, t Cj для лябых l4j .

Данную задачу,сводим к предыдущей стапл в соотвэтствие i -§ дататя fC¿ вер тан из множества X . Птан загрузки оборудования составляем с учетом того, что у вершин, входящих я t Fv i í s г fj¡f i первые индексы указывают не на покера деталей, а на номера детатеопераций, которые должны выполняться одновременно.

Задача 3. К условиям задачи 2 Добавим, что время k¿j выполнения i -6 деталеопераояи на J -м станке может быть различит'.

Найдем вреуя "t такое, что с допустимой в каждом конкретном случае тччяостью судестэует представление £ .

•У

гдч LCj О - пелое число.

ГЬстрсягя двудольны!! гра£ С и по налу - мультигра^ в котороу чпкд^ку ребру (Xc^j) £ & соответствует T¿j рр^ер. Далее задачу ряпаем тем хе методом, что и задачу 2. Тллрдуа 2, Число классов мшима.тьноК раскраски гра|а

же;

построенного по мультигра^г , равно числу классов мини-

■ - 10 -

галькой раскраски графа JÏ-СУ , построенного по графу С.

При ve't'OHHH 06340й. задачи необходимо учитывать следующую

!<3ео<5£яносгь Birfopa минимального набора полных подграфов, по-

крываадага • X ; если в некоторый полный подграф

иходпт вершина' V' (X C i « то в сладувдий выбранный подграф г-114 - ' ■ ' ■ ' - пг .

Гvc должна входить вершина H-Cj , и т.д.. пока не

исчерпаем все t.¿у вершин выполнения каздой деталйопярации.

Это условно необходимо 'для того, чтобы обеспечить непрер]

яосгь/вдаоляен'вя кавдой деталаоперация.

Суммарноо ярвмя обработки всего объема продукции вичисля

ercjf по формуле \

Т- M t , где N - число полных подгра фов -в гзщймаяьнш наборе.

Задача 4. Пусть часть деталей поступает на обработку не начале производственного'процесса, а в некоторый момент вра МВ.9В ti. .. " ' . ' '.,'-;•

.Б этом случав мы разбиваем задачу по времени на 2 подзад ча ;г одна - составить плац загрузки оборудования на вреш Ct; другая - на время С i, ¿д 3 . В первой подзада1 mi р-чссыатршзем только те детали, которые поступада к начг '-гой'нюдсгвошюго процесса, во второй - детали, поступивши! пар; i время 'tj , а такав,те двтаавопврацил яз первой под дзчг., которые согласно построенному в ней плану доджнн быт: выц ляенн досле момента вреиени k j .

Коли выбранная едашщя врешнц "h , аа которое яиполнп ея один этап обработка деталей, m укладывается в npo.ve«>T COjiil целое число раз, ïo5 чтобы обеспечить непрерывно выполнения каждой двталвоперацки, иукно выбрать меньшую ед!

1 временя, тан чтобы ^i/t было:цвлнм числом. -

ÍT.2 посвящен описанию програьтиноР реализаций построения :тикального плана загрузки оборудования.

Третья глава посвящена исследованию критических я гчтигАхта пс YÍ. - связных графов. : В п.2 рассматоиваются П. - связанв графн. Пусть вмавтся граф d , вертлявая связность которого ? [G.)~fL . По теореме Менгера любые две вершины такого трй-1 можно соединить йа менее чем tV простым«,ввршаянонепэр^св-яяцииися цепями.

По гря^у и достроим граф КС Cj сладушям образом: аа-•ксируем две вертдни X¿ t3Cj G $ я сопоставим каждой просей цепи, соединяющей и , верпшну графа зз вершин графа ЖAj смвжнп, ясли соответствующие ям пв-! в Q на перасекаются. '

Раскрасим граф JTCij мянимтяым образом. Пусть JD(DC) -•«пень вертошы X . тогда, опираясь на теорему Менгера, допиваем следугс^то теорему. Теорба 2.1. Число классов

в млнямальйоК рас-таскв графа УГСсj удовлетворяет слвдуядэму соотношению:

juiJÍCij) ~к шп (pí^ú, j)

18 КЪП - «эчсииальпоп число непересекакдахся цепей, соеди-1ЩЯХ X ¿ и X j .

for^va VTNy.iipyeT вахяоа свойство гра1юв цепей.

2.Д', Гра{ti ч"иаП образуют ктаес графой, для кото--т xnv-яrti i"-«"ifl -поло р-ярно штотяостя, т.е. LkIJICí

jb

- 12 -

Замвтик,: что рля Произвольного гра|а ^ [ причем разница Мояет быть сколь угодно большой,

Пусгь галер*. для каждой пары впрсшн где Д/ - <дасло варшн графа £ч , построен граф произведена его; »ащямяльная раскраска. Получим набор чис/

Теорема Й.2. Вершинная связность графа С удовлетво;

т1пкаур..

/Я^'осязании зтях теорем предлагается способ опредале варашшой связнозтя трафз и конкретного максимального, на яёпе^асвкгошщхся цепей, соединяющих две вершины графа С Подученные результаты верны и для реберной свяэно'сти ^рв, есл-1 под непереоекаодимйся цепями поникать реберно ■ресокашдаеея цепи;

-. П.3 посвящен изучению критических и минимальных относ ие; связности графой, . ■ Будем рассматривать набор } дибюс № (ЖСу ) - £(<-¡1) ,, причем да

соге гр&фа 1ГСК€ 0А .

В графа этот? набор соответствует множеству пар а . шадняявдихея ровно ¡Ъ непорасекапцймися цепями. -

■ Теорема 3,1. П» - связный граф (* является крятнч относительно связности тогда и только тогда, когда для . яор'ликк X С" и найдется гра

Л С

С! С" о , в кото

с г

нельзя выбрать подграф г ^ , не содержащий вврпшну, с

- 13 -

ю в (л пени, проходящей через ЗС .

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

связностя графов.

юновачия этих теорем получаем способ определения, ямя-1 граф критическим /минимальным/ относительно связности. !м набор А так, как указано вшю и произведем опера-1ДНН0НЯЯ всех градов Щ 6 А . Получим граф £ - число графов ЛС^ , входящих .в А . тма З.З.' - связный граф С является минимальным ■вльно связности тогда и только тогда, когда дтя дгобо-)а Iгб С граф С* = (л порождает набор ' , что построенный чо нему граф Л А1 имеет хроматячес-!Л0 /¿(ЛА (КА) С-71

Аналогичная

» доказпЕЭзтся п для КЬ - критических градов.

ил образом, задача определения критичности /мипимаяыюс-

**

\фа сводится к ».пшнк-аи-ной раскраске специально постро-графа. ''

га того, яга основания вида минимальной раскраски графов гожнэ .найти все вертите графа (х , удалений какдой из [ в.течет уг/еншетяе связности в графе. Обозначим это

:во V . '

1ст?я9. Если множество V совпадает со множеством X ?ршян графа С , то граф С является крятячветсям 11 -

означает, что этот способ такие годится для того, что-иилятт. тфитлчнооть графа отиооятачьно связности, Анало-исследования птювпдены к для вдшима'шшх графов.

- 14 -

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

Публикации по тема диссертации:

1, Тюлотщина 1.А, Методы оптимизации в задачах плат ния. - Вопроси механики и процессов управления, вып. 1* 1991, с, 91-98,

. 2. Тшяндина Л.А. Минимальная раскраска и 4--критиче< ■ гра$н. - Л., 1988. Двп, в ВИНИТИ 11.01.88, 5 84 - В 88

3. Тшяндина Л.&. 0 критических и минимальных П-.кт графах /в печ./ 1

4. Тшяндина Л.Л. О связности гра$ов, - Л., 1990. $ ВИНИТИ 17.10.90, & 5586 - Е 50, ' <

?6.03,92 г.Зак .125-100. РП1 ЛТИ, Московский пр.,26