Задачи теории расписаний для системы с нефиксированными маршрутами и ресурсными ограничениями тема автореферата и диссертации по математике, 01.01.09 ВАК РФ

о

. I

АКАДЕМИЯ НАУК БЕЛАРУСИ ИНСТИТУТ МАТЕМАТИКИ

На правах рукописи

ЛУЖКОВА Ирина Николаевна

ЗАДАЧИ ТЕОРИЙ РАСПИСАНИЙ ДЛЯ СИСТЕМ С НЕФИКСИРОВАННЫМИ МАРШРУТАМИ И РЕСУРСНЫМИ ОГРАНИЧЕНИЯМ

01.01.09 - математическая кибернетика

Автореферат

диссертации аа соискание ученой степени кандидата физико-математических наук

минск - 1992

Работа выполнена в Белорусском государственной университете

Научный руководитель - кандидат физико-катематических наук,

профессор Леиешинский Николай Андреевич

Официальные оппоненты - доктор физико-математических наук,

профессор Такаев Вячеслав Сергеевич

- кандидат фиаико-матеиатических наук, доцент Бородич Сергей Аркадьевич

Ведущая организация - Институт кибернетики ш.В.Ы.Глушкова АН Украины

Защита состоится "27- " и о.я &рх- 1992 года в

часов на заседании специалазяровзкиого совета Е 006.19.01 в Институте «агеиагини АН Беларуси по адресу: 220072, г.Мииск, ул.Сургановэ, И, Институт математики АН Беларуси.

С диссертацией можно ознакомиться в библиотеке Института математики АН Беларуси.

Автореферат разослан " Схз " СгШс^-^^Л. -с^ 1992 года

Ученый секретарь специализированного совета кандидат физ.~иат. наук

Дйс-Ц^?- А.И.Астровский

„•^ч, iv. ннчл ? ---

У-олгС • »

ОЩАЯ харшерДГША РАБОТЫ

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

Многостадийные обслуживающие системы с нефиксированными маршрутами привлекли внимание специалистов в семидесятые годы. Не толь-<о чисто научный интерес, но и необходимость решать новые практи-1еские ¡задачи (например, задачи, возникавшие при организации спут-мковой связи) привели к появлению целого ряда публикаций, посвя-¡енных этим системам. С конца семидесятых годов в теории расписа-;ий сформировалось, также направление, в котором изучаются различие одностадийные и многостадийные системы с ограниченными восста-1авлиэаемыми ресурсами.

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

Целью работы - является исследование различных классе задач для многостадийных обслуживающих систем с нефиксирован-ыми маршрутами и ограниченными восстанавливаемыми ресурсами, а менно: доказательство А/Р -трудности некоторых задач; выявление олиномияльно разрешимых задач и построение для них.точных эффек-ивных алгоритмов решения.

Научная новизна. Доказана N9 -трудность в силь-эм смысле задачи построения оптимального по быстродействию .распития для двухстадийной системы при условии,, что в процессе обслу-пзания требований испольоУются восстанавливаемые ресурсы, запас 1хдого из которых равен единице. Показано, что задача является ]Р -трудной, если имеется точно два ресурса.

Доказана А/Р -трудность в сильном смысле задачи построения ггимального по быстродействию расписания для трехстадийной системы >и условиях, что длительности обслуживания требований одинаковы и

в процессе обслуживания требований используется ресурс произвольного запаса.

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

Шервые рассмотрена задача выбора оптимальных скоростей приборов в двухстадийкой системе с нефиксированными маршрутами при условии, что в процессе обслуживания некоторых требований некоторыми приборами используется более половины запаса восстанавливав- • мого ресурса. Эта задача сведена к известной в литературе полиномиально разрешимой задаче.

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

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

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

Публикации и апробация работы. Основные результаты диссертации опубликованы в работах А-8/ и докладывались на ill Всесоюзной школе-семинаре "Дискретная оптимизация и компьютеры" (г.Таштагол, 1987), на XI Всесоюзной школе-семи-нарз "Системы программного обеспечения решения задач оптимального планирования" (г.Кострома, 1990), на республиканской конференции молодых ученых и специалистов "Применение информатики и вычислительной техники при решении народнохозяйственных задач" (г.Минск, 1989), на межреспубликанской научно-практической конференции творческой молодежи "Актуальные проблемы информатики: математическое, программное и информационное обеспечение" (г.Иинск, 1990), на научном семинаре по теории расписаний под руководством В.С.Танаева

В ИТК АН БССР (г.Минск, 1386, 1991).

Структура и объем работы. Диссертация состоит из введения, трех глав, списка литературы (96 наименований) , содержит ПО страниц шелшописного текста.

СОДЕРЖАНИЕ РАБОТЫ

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

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

В § I вводятся основные понятия и определения.

Пусть имеется множество /Ч- » { 4, 2., ..^-/Л} последовательных приборов (АЛ ^2). Множество N-{I, 2, требований необходимо обслужить этими приборами. Требование ¿€/1/ поступает в систему и момент времени ^О . Для всех требований множества- д/ маршрут обслуживания (порядок прохождения приборов) заранее не задан и монет быть различным дая разных требований. Известны длительности Ь ¿ ¡_ О обслуживания каждого требования I £ Л/ каэдым прибором 5 / « А\ . Запись

означает, что требование I прибором ¿. не обслувд-ваетоя. В любой момент времени каждое требование обслуживается ке более чем одним прибором и каждый прибор обслуживает не более одного требования. Такие обслуживающие системы называются системами с нефиксированными маршрута -ми , v.

В дальнейшем предполагается, что все требования поступают в очередь на обслуживание в момент времени Л - О I и прерывания процесса обслуживания каждого требования каждым прибором запрещена.

Процесс обслуживания требования отдельным прибором навивается операцией. Кавдю операцию будем обозначать упорядоченной парой { I, I) } I £ Л/, I £ АС.

Выполнение некоторых операций может быть сопряжено с потреблением восстававливаешх ресурсов. В этом случае предаолагается заданным множество 5?. - { т-*, , 7. £ § восстанавливаем«: ресурсов. В лжбой момонт времени запас ресурса "г ; равен

- о -

, а его потребление при выполнении операции (I , I) составляет ^ ( I < п-г-у единиц, 1 < й ¿.

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

Пусть Б - произвольное расписание.

Расписание 5 будет допустимым по ресурсам, если а любой момент времени суммарное потребление каждого ресурса не превосходит его запаса. В дальнейшем будут рассматриваться только допустимые расписания. •_

Через С £) и Ь ¿ ( £) обозначил соответственно

момент начала и момент завершения обслуживания требования ¿ прибором при. расписании 5 . Через ± £ (ъ ) а ггис^х.' обозначим момент завершения обслужнва-

ния требования I при расписании 5 , а через Ь ^^ -= { ("£) j - момент завершения обслуживания всех

требований (общее время обслуживания) при расписании .? . Расписание X* , при котором достигается минимум "¿тсчх • называется оптимальным по быстродействию.

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

Б § 2 рассматривается задача 25 , которая состоит в построении оптимального по быстродействию расписания для многостадийной системы с нефиксированными маршрутами и ограниченными восстанавливаемыми ресурсами.

Теорема 2.1. Задача является МР -трудной в сильном смысле, если /Л 2 . t 2. и л*.у = i) ^ » ¿, £,

К соответствующей, задача распознавания при ЛЛ = 2 сводится известная л//5 -полная в сильном смысле задача о 3-разбиении.

Теорема 2.2. Задача 25 является Л/Р -трудной, волк М = 2 , £ = 2. и гл; » 1 , у - I.

К соответствующей задаче распознавания можно свести известную д/Р -полную задачу о разбиении.

Теорема 2.3. Задача 2 является Л/Р -трудной в сильном смысле, если ЛЛ ^3 , ¿ = I и ¿¿^ » ^ , I е /V , '¿- = /л. .

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

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

В- этой главе приборы обслуживающей системы обозначаются А и 8., а длительности обслуживания требования I е /V этими приборами сц, и ¿1 соответственно.

В § 3 предлагается алгоритм построения оптимального по быстродействию расписания обслуживания множества /V требований в двухстадийной системе с нефиксированными маршрутами прохождения приборов. Множество /V содержит требования, для которых необходимо использовать единицу ресурса в любой момент обслуживания тем или иным прибором. Запас ресурса в любой момент времени равен единице. .

Множеству /V сопоставим три подмножества А/0 , и Л/в требований. Ко множеству А/0 отнесем требования, не использующие ресурс. Требования, использующие ресурс только при обслуживании прибором А (ига В ), отнесем ко множеству /1/д (соответственно, Л/0 ), Каждое требование I , использующее ресурс при обслуживании как одним, так и другим прибором, заменим на пару требований 1* и ■£." , полагая ее - г = , вс - о , в¿„ = ё>1 , сх. ^ - о , а отнесем требование I' ко множеству Л^ , а требование I" - ко множеству Л/а .

Для непустого множества р. требований положим о.(й) =

- ее; , ёС&) - 21 ё; . Если £ =(6 , то положим ¿еА и*

. Через обозначим произвольную

перестановку требований множества /?

Для величины ¿та_х ) общего времени обслуживания требований множества л^ и А/А и Л/в при произвольном расписании 5 справедливо

Утверждение 3.1. Имеет шио следующая оценка:

Ь^х с ^ т= { ГО, £ (АГ) >

г^-о^х {(\i-hii I ¿ел/о}, +

т^х { с», с + \ I € + £

{ Я. с ¿1 | г! £ Л/й ] + а- СЛ/а)У .

Описывается процесс построения расписания такого,' что

при $ - имеет место равенство ¡Гз) = 7~ . Такое'

расписание, очевидно, является искомым оптимальным расписанием.

Оптимальное раскисание ищется в классе расписаний, которые однозначно определяются заданием пары наборов вида ( ;

... , \-tpj_ ), ъ ± . Здесь ¿- £ ( А, В ] _ наименование лрггбора, элемент И^ набора имеет вид £ •

, где (¿) -момент времени, начиная о которого прибор и . функционируя без простоев, обслуживает требования множества л^ с л/ в последовательности ^ СЛ^) •

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

Алгоритм построения расписания X * заключается в проверке ряда неравенств и в выбора соответствующей пары наборов, определяющей оптимальное расписание.

Представлены схемы, ¡указывающие порядок проверки неравенств, а также специальный алгоритм С , позволяющей построить расписание 5* (.соответствующие пары наборов) в важном частном случае.

Утверждение 3.2. Алгоритм С строит оптимальное расписание 5* .

Введено А 6 -преобразование, ограничивающее с учетом симметрии число изучаемых ситуаций. Оно заключается в том, что сначала меняются местами наименования приборов, затем одним из способов строится расписание , после чего восстанавливаются исходные наименования приборов.

Совокупность рассмотренных а § 3 неравенств полностью охватывает всевозможные соотношения между исходными данными задачи.

Построение любой пары наборов, определяющей оптимальное расписание, требует выполнения нэ более ОС к-) операций.

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

1) когда в процессе выполнения операций допускаются прерывания, поскольку утверждение 3.1 остается справедливым;

2) когда запас ресурса в любой момент времени равен т, , а каждое требование множества л/д (или Л/а ) в любой момент времени его обслуживания прибором (соответственно, В ) должно использовать более т. /г. единиц ресурса.

В § 4 рассматривается двухстадийная обслуживающая система при предположении, что скорости приборов заранее не заданы. -Воли скорость прибора А (прибора 8 ) равна VA о (соответственно, хГвУО), то длительность обслумшания требования I е Л/ этим прибором раина <7L¿ /ггл- (соответственно, S i / г/j ) единиц времени. Здесь il; и - заранее заданные неотрицательные числа (длительности обслуживания требования t с- Л/ при скоростях приборов ХГА - - d ). Пусть "fc ( ^а , ^ 3 означает наименьшее значение общего времени обслуживания в классе всех допустимых расписаний при фиксированиях скоростях приборов TJ~fy и V0 .

Рассматривается задача выбора оптимальных скоростей

приборов VA и V~0 , при которых ($ункционал стоимости обслуживания требований в системе

f

принимает наименьшее значение. Здесь Са, С-х t С- положительные константы, и - натуральные константы.

Известно, что эту задачу можно решить за

0(ъ г)

операций, если t ( Ы Ы0 ) - ( /V~A +

+ I j -zftfr.

Показано, как в результате надаежащего выбора z и значений и /3 j задача i С может быть решена для двухста-дийной системы с нефиксированными маршрутами при предположении,

- g _

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

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

В § 5 представлен подробный анализ данной задачи и намечен возможный подход к её решению.

Множество Л/ разобьем на 2 ^ непересекаюшихея подмножеств М* ; Д/2 , ..., ; Л/„ ,.Л/уд,, . Ко мно-

жеству Ыр отнесем все требования, не использующие ресурс. Если требование использует ресурс только при обслуживании одним прибором 1 й 4 ЛЛ , то отнесем его ко множеству . Если требование использует ресурс только при обслуживании Ц приборами , то отнесем его ко множеству ^ С, 1-х — § ' ^Роме гого, обозначим H¿ множество всех требований, использующих ресурс при обслуживании прибором ¡-гИ ¿.&1Л. Полежим ■к1 я | И11.

Для произвольного множества /2 С Д/ требований положим

= I , если 0 , и Г(И) = О в противном случае.

Для величины £ ^^ общего времени обслуживания тре-

бований множества N при,произвольном расписании J справедливо Утверждение 5.1; №еет место следУшяя оценка:

£ (Ь) > Т - + +

Любое расписание о однозначно определяется заданием матрицы н ^il(S)Ч моментов завершения обслуживания каждого требования I р А/ квщыи прибором I .

Обсуждается возможный способ построения расписания 5* такого, что при 5=5* имеет место равенство ($) = Т> - которое обеспечивает оптимальность

Вводится матрица А = II II , где "Х^ - I,

если прибор 1_ обслуживает -ыы по порядку требование I £ Л/. Рассматривается также матрица Ц, = ц ц , где и-ц если требование с (. N при обслуживании прибором 1_ использует ресурс, и и^ =0 в противном случае. Матрица 1С строится с точностью до расположения столбцов.

Назовем матрицу допустимой в соответствии с матрицей и., если ^ля любого столбца матрицы Д будет выполнено неравенство ~> (Л. / % £ -У

Исходная оадеча сводится к построении матрицы /I , допустимой в соответствии с заданной матрицей Ы. . Если такая матрица А найдена, то полагая

т /Л, п,

.получаем матрицу ц £ ^ С 2") II . определяющую оптимальное расписание .5* .

Матрица А предстааляет собой латинский прямоугольник (кяад-раг), построенный на множестве { i, 2, — , ~Т ] , причем на воз-ножное расположение элементов в столбцах накладываются определенные запреты, характеризующие ресурсные ограничения. Достаточно общий характер запретов при произвольном !Л на расположение элементов в столбцах является существенным препятствием для разработки компактного алгоритма построения латинского прямоугольника (квадрата). Предлагаемый подход к решению задачи заключается а том, чтобы классифицировать эти запреты и для каждого конкретного случая унагэать допустимнй латинский прямоугольник. Построение матрицы А размерности МхТ и матрицы Il7¿¿ в каждом конкрет-

ном случае будет требовать выполнения не более чем 0 (Л1г п.) операций.

В § 6 реализация предложенного подхода продемонстрирована для случая ЛЛ = 3.

Аналогично тому, как для множества /V требований были введены матрицы Д » || Л ¿о. II и Ц = ц иц II , для произвольного подмножества Я С Л/ вводятся модельные матрицы X = // х^ ц и У ■= Я || «а также понятие допустимости матрицы X в соответствии с матрицей У.

Представлен анализ структуры множества Л/ и указан способ построения матрицы А . Алгоритмы построения фрагментов матрицы А

описаны с помощью языка высокого уровня Упрошенный Алгол;

В каждом Алгоритме построения фрагмента матрицы А. для определенного подмнокестча требований К ? А/ рассматривается его ¡.'.сдельная матрица У . Предполагается, что порядок расположения столбцов матрицы У совпадает с указанной в алгоритме последовательностью у / Я) расположения столбцов некоторой модельной матрицы У . Л

„ Предварительно строятся матрицы У и^Х такие, что матрица X допустима в соответствии с матрицей У , которая может быть приведена к матрице У с помощью перестановки строк. Матрица X Представляет собой латинский прямоугольник (квадрат), построенный на множестве 12. с .учетом последовательности кр {й) ^ . Далее проводится необходимая замена нумерации строк матрицы X с тем, чтобы получить матрицу X , допустимую в соответствии с У.

Построенная матрица А имеет размерность 3 х Т . Матрица ¡1 tiL (£*) II , определяющая оптимальное расписание,

получается с помотыо формул из § 5, приведенных выше.

Автор выратает благодарность за помощь в работе, и неизменное внкчалие своему научному руководителю кандидату физико-математи-чески:: наук профессору Н.А.Лепешинскому и кандидату физико- математических наук доценту З.Л.Струсеаичу.

ПУБШЛЦИИ

1. Луиакова И.Н., Струсевич З.А. К задачам теории расписаний с нефиксированными маршрутами и ограничениями на ресурсы // Тез. докладов Ш Всесоюзной школы "Дискретная оптимизация и компьютеры". - М.: ЦЗМИАН СССР, 1987, - С. 41-42.

2. Струсэвич В.Л., Луиакова И.Н. Оптимальные по быстродействия расписания для двухстадийных систем с нефиксированными маршрутами при наличии ресурса единичного запаса /Ред ж. "весц!

№ БССР. Сер. ф1з.-ыат.н." - Минск, 1988. - 65 с, - Деп. в ¿ШИГИ 24.06.88, № 5074-В88.

3. Луиакова И.Н., Ст русевич В.А. Сложность построения оптимальных расписаний для систем с нефиксированными маршрутами при ограничениях на ресурсы // Методы репекич экстремальных задач. -Минск, 1989. - С. 57-65.

4. Лущакова И.Н., Струсевич В.А. Двухстадийнце системы с нефиксированными маршрутами и ресурсными ограничениями //ЙВМ и МФ.

* 1989. - Т.29, №9. - C.I393-I407. ''

5. Лущакова И.Н. Об одной задаче теории расписаний с нефиксированными маршрутами и ресурсными ограничениями // Применение информатики и вычислительной техники при решении народно-хозяйственных задач: Тез. докл. респ. конф. - Минск: БГУ, 1989, - С.191.

6. Струсевич В.А., Лущакова H.H. Выбор скоростей приборов для двух задач теории расписаний //Системы программного обеспечения решения задач оптимального лланирования:Тез.докл. XI Всесоюзной школы. - М.: ЦЭШ АН СССР, 1990. - СЛ26-127.

7. Лущакова И.Н. Оптимальные по быстродействию расписания для трехстадийных систем с нефиксированными маршрутами и ресуреши и ограничениями //Актуальные проблемы информатики: математическое, программное и информационное обеспечение: Материалы меж' респ.научн.-практ.конф. - Минск: ИМ АН БССР, 1990. - С.304-306.. -

8. Лущакова И.Н. Оптимальные по быстродействии расписания для трехстадийных систем с нефиксированными маршрутами и ресурсными ограничениями /Ред. ж. "Весц1 АН ВССР. Сер. ф1э.-мат.н.".

- Минск, 1991. - 38 с. - Деп. в ВИНИТИ 29.04.91, »I800-B9I.