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

Академия наук Беларуси Институт математики

УДК 519.854.2

КРАВЧЕНКО Светлана Алексеевна

ПОСТРОЕНИЕ ОПТИМАЛЬНЫХ РАСПИСАНИЙ ДЛЯ МНОГОСТАДИЙНЫХ СИСТЕМ С ФИКСИРОВАННЫМИ МАРШРУТАМИ ОБСЛУЖИВАНИЯ ТРЕБОВАНИЙ

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

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

Минск - 1996

Работа выполнена в Институте технической кибернетики АН Беларуси

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

профессор Сотсков Юрий Назарович

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

профессор Метельский Николай Николаевич; кандидат физико-математических наук доцент Мельников Олег Исидорович

Оппонирующая организация:. Вычислительный центр РАН

II. г! II

Защита состоится " 28 " июня 1996 г. в 1г часов на заседании совета по защите диссертаций Д 01.02.02, в Институте математики АН Беларуси (220072,г.Минск,ул.Сурганова, 11).

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

II и

Автореферат разослан_1996 г.

Ученый секретарь совета да , р А.И.Астровский

по защите диссертаций

ОБЩАЯ ХАРАКТЕРИСТИКА, РАБОТЫ

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

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

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

Связь работы с крупными научными программами, темами. Диссертационная работа выполнялась с 1991 года по 1995 год в лаборатории математической , кибернетики Института технической кибернетики АНБ в соответствии с плановыми научными исследованиями по теме "Машиностроение 2.25".

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

Научная новизна полученных результатов. Впервые доказана

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

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

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

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

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

Экономическая значимость полученных результатов.

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

Основные положения диссертации., выносимые на задоту.

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

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

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

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

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

Апробация результатов диссертации. Основные результаты диссертации опубликованы в работах [1-11] и докладывались на Международном семинаре по дискретной оптимизации (г. Минск, 1993 г.), на VIII Европейской конференции по комбинаторной оптимизации (г. Познань, 1995 г.), на Международной конференции "Алгебра и математическая кибернетика" (г.Минск, 1995 г.), на научных семинарах по методам оптимизации в проектировании и управлении Института технической кибернетики АН Беларуси (г.Минск,1992-1995 гг.).

Опубликованность результатов. Основные результаты диссертации опубликованы в 11 научных работах.

Структура и объем диссертации. Диссертация состоит из введения, четырех глав, списка использованных источников из 97 наименований. Диссертация содержит 94 страницы машинописного текста, в том числе 25 иллюстраций и 2 таблицы.

В первой главе диссертации приводится обзор научной

литературы по теме исследований.

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

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

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

максимального временного смещения.

В конце глав 2, 3 и 4 помещен раздел с краткими выводами.

Автор выражает искреннюю признательность своему научному руководителю доктору физико-математических наук профессору Юрию Назаровичу Сотскову за постановку ряда задач, внимание к работе и плодотворные обсуждения.

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

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

В главе 2 рассматривается следующая задача.

Два прибора И¿ и М^, обслуживают к требований J = {Jj,...,J^}. Каждое требование обслуживается без прерываний и невозможно одновременное обслуживание его двумя приборами. Любой из двух приборов, в свою очередь, не может одновременно обслуживать более одного требования. Для любого требования J^ заранее задан порядок его обслуживания ( fi^ j, )lj ^..... рt г ^

приборами fijjS { Mj ,¡¡2 } и вес tu^e R, количественно определяющий значимость момента завершения обслуживания требования JjÇ J , I е {?,...,&}. В задаче требуется построить расписание, минимизирующее некоторую заданную неубывающую функцию.

В разделе 2.1 решается задача минимизации £ w. С, .

1=1 1 1

Введем в рассмотрение орграф G=\V,E). V=U={j(1),.. ,j(k))'. О s J(t)s г{ , t e { } }, - множество вершин орграфа G.

Каждая компонента J(i)*0 вершины JeV служит для обозначения операции j^y Вершина р е V, у которой все компоненты нулевые, называется начальной вершиной, а вершина q e V, у которой g(í) = rt для всех í с { 1,¿..,k }, называется конечной вершиной.

Пусть и e У , V <= V и кроме того u(i) s u(í) для всех te{ }, тогда можно определить следующие три множества :

D (u,v) = { 0t>j(i) : í e О.....k), "(О < Л O s u(£)Jï

DA(u,v) = i 0j : 0ifj e D(tí,u) , UtJ = ^ }; DB(u,v) = { 0t'j : 0¿ e D(u,u) , = >.

-а-

Будем говорить, что D(u,v) образует блок и - и, если можно построить допустимое расписание со следующими свойствами: 1) операции множества DA(u,v) выполняются в промежутке [г , Т + T(A,u,v)~} , здесь Z - некоторый момент времени, а !Г(.4,и,и) -

Е гц '

0{ jsDA(u.v) lJ

2.) операции множества DB(u,v) выполняются в промежутке [г , т +

Т(В,и,и)] , где Т(В,и,и) = £ t, . ,

DitJGDB{u,v) lJ

3) в промежутке времени [г + min[T(A,u,v) ,T{B,u,v)), t +

mar{2'(ji,u,v),r(S,tz,!;)}] один из приборов простаивает, а • другой

прибор занят выполнением операции.

• Дуги Е орграфа G определяются следующим образом: (u,u)e Е тогда и только тогда, когда D(u,v) образует блок.

Поскольку любое компактное расписание состоит из блоков, то очевидно, что любой путь из р в q в орграфе G соответствует некоторому (допустимому) расписанию, однако, не каждое расписание соответствует какому-нибудь пути из р в q в орграфе G. Тем не менее, оптимальное (относительно регулярного критерия) расписание можно искать среда расписаний, соответствующих путям из р в q в орграфе G.

В орграфе G каздой дуге (и,и) припишем длину L{u,v) и два веса C(u,v) и W(u,v): L(u,v) = яаз? { 244,и,и), Т(В,и,и) } и

№(и,и) = £ «?. . Очевидно, величины W(u,u) и I(u,i>)

{«: г{>и(Ш 1

одинаковы' для всех допустимых размещений операций из множества D(и,и) в блоке и - и. Наличие дуги (и,и) и вес G{u,v) будут определяться из орграфа G(u)=(7(u),E(u)), который будет построен для каждой вершины и е V. В орграфе G(u) любой путь из вершины и в V определяет некоторое допустимое размещение операций D(u,v) в блоке u—v, причем, каждому допустимому размещению операций из D(u,v) в виде блока в орграфе G(u) взаимнооднозначно соответствует некоторый путь из и в и.

Опишем построение орграфа G(u). Множество вершин 7(и) орграфа G(u) определяется следующим образом: V(u)~ V'(u) U tu}, где V>(u) = { (J,/) : J с 7, f e О,J(t) * "(О Для всех i е {1.....к} }, т.е. вершина (J,f) в V(u) является верши-

ной / из V о одной выделенной компонентой /.

Дуги Щи) орграфа й(и) определим таким образом, чтобы для любого пути (и.и^,...,и2) в б(и) с и2 = (J,f) существовал блок и - J, в котором самой последней завершалась бы операция °/»Д/)' Г*е" */»Д/)~ г" ЯРУ1™0 словами, если дуга

выходит из вершины и, то (и,(/,/)) е Е(и) тогда и только тогда, когда J(g)=u{g)■^-1, если и J(g)=u(.g), если если у * и, то дуга ((у,7г),(/,/)) принадлежит Е(и) тогда и только тогда, когда :

1) существует единственный номер £ € { 1, ..., к } такой, что ДО = у(0 + 1, причем ДО^уф) * М( а Аля остальных индексов gG[1 ,...,1-1,1±1 ,...,)г} выполняется равенство y(g)=J(g);

2) если 7г=/, то Л/)-у{/) и для индекса £ такого, что Д 0=1/(0 + 7, выполняется соотношение J(t)•u•J) *

если же 1г*/, то Д/)=у(/)+7 и ^(Мд^).«»/) > т^п,у(П) •

Таким образом, наличие дуги ((у,к),(/,/)) в С?(и) означает возможность увеличения блока и - у на одну операцию 0{ j(^)^ гДе ДО = У(0 + 1.

Каждой дуге в С (и) припишем вес следующим образом. Пусть в <?(ц) дуга ((у,П), (/,/)) принадлежит £(и), а номер £ такой, что ДО= 1/(0+1, тогда дуге ({y,h),(J,f)) припишем вес Р(у,Л:

если ДО=ге; и Р(.у,Л-0, если ДО Аналогично, дуге (u,(j,f)) е Е(и) припишем вес Р{и,Л=

J(J.yU,S), если Д/)=гу; И Р(и„/)=0, если Д/)*гу.

Рассмотрим орграф С (и). Любой путь (и, (uJ¡,g1)..........И3

иБигв орграфе <3(и) определяет некоторый блок и - и2 , т.е. ребро (ы, и ) принадлежит 7.

Таким образом, любое расписание, содержащее блок и - их, соответствует некоторому пути из и в и в орграфе б(и).

Поскольку длительности выполнения кавдой операции из множества Л(и,и2) заранее известны, то можно определить веса всех дуг в в(и). В диссертации доказаны следующие утверждения. Утверждение 2.1 Если в орграфе в некоторый путь из р в д, содержащий дугу (и,и2), соответствует оптимальному расписанию, то блок и - и2, входящий в данное расписание, должен соответ-

ствовать кратчайшему из и в uz пути ¡1 = ( и, (u^.g^), ..., (u^.g^)) в орграфе G(u).

Утверждение 2.2 каждому пути Ji=((u0,u?).....(us_1tuz)) из р в q

в орграфе с соответствует некоторое расписание s со значением

k

целевой функции, равным £ ^Сг=У(и0,и?)+У(и^,ир)+...+ У(и2_^,п2).

Таким образом, задачу J2|n=fc|5>{C{ можно решить за время 0(гЖ), путем сведения ее к задаче нахождения кратчайшего пути в орграфе G.

Для задачи J2|п=3|£ ti>{C{ трудоемкость описанного алгоритма может быть уменьшена до 0(г4).

.Все описанное до сих пор относилось к суммарному взвешенному критерию, однако, если в качестве Y(u,v) взять значение L{u,v), то получим решение задачи J2\n=k\Cmx, причем, трудоемкость не изменится. Таким образом, задачу J2|п=к|С и задачу

<-чг_ JTILlá,

J2\n=k\Y. можно решить за 0(г) элементарных действий путем их сведения к задаче поиска кратчайшего пути в бесконтурном орграфе.

В разделе 2.2 рассматривается та же задача с более общим критерием, а именно, I/^Cj), где /{(С{) - неубывающая функция, зависящая от времен завершения обслуживания требований. Для ее решения предлагается алгоритм, общая трудоемкость которого составляет

В разделе 2.3 рассматривается обобщение задач, описанных в разделах 2.1 и 2.2 на произвольный регулярный критерий, т.е. в рассматриваемой задаче требуется построить расписание, минимизирующее произвольную неубывающую функцию F.

Введем следующие обозначения. Операцию назовем

trí

КОНеЧНОЙ операцией работы Блоки будем обозначать буквой В с индексом внизу. Множество операций, выполняющихся в блоке обозначим . Блок Бу назовем существенным блоком, если он содержит по крайней мере одну конечную операцию. Последовательность' существенных блоков В, , б, В, (1szsk), назовем

11 12 • z

каркасом расписания. Пусть обозначает множество работ,

которые завершаются в блоке Впринадлежащем каркасу.

Рассмотрим представление оптимального расписания з в виде

блоков в1, В0.....В„ и пусть В, ,В. .....В, - соответствующий

д 17 12

каркас. Тогда оптимальное расписание з обладает следующим свойством: операции в каждом множестве Л0= В]) , +

1

..., иу={ , упорядочены таким образом, что каждое

частичное расписание, состоящее из операций А(, имеет минимальную длину. Отметим, что множества А( однозначно определяются каркасом.

Предположим, что дан каркас В, ____,В. и последова-

1 г

тельность & состояний ,...где каждое состояние

(7)•...(&)) определяет положение операции , т.е,

I

8^(J) обозначает хшдекс последней операции О^ ^ требования

3, начало обслуживания которого не больше чем начало выполнения операции 0{г . Очевидно, что , и кроме того, если

заданы В{ и б^.-.-.б^. то значение С{ определено

однозначно для кавдой операции 0. , поскольку несложно найти

1Г{

существенный блок В, , в котором выполняется операция 0,_ ,

V 1Г{

т.е. длину расписания до данного существенного блока можно

подсчитать, а состояние позволяет вычислить длину блока до

момента С{.

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

АЛГОРИТМ

Шаг 1. Генерируем все возможные последовательности, состоящие из произвольного каркаса В, ,...,В, и произвольного множества

СОСТОЯИЙ

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

1 Ob

Итак, задачу J2\n=k\F можно решить за 0(г ) элементарных действий.

В главе 3 рассматривается следующая задача. Имеется

множество требований J = (J^.....J^}, которые необходимо

обслужить двумя приборами lí? и if р. Обслуживание каждого

требования«/^, i е {7,___,п}, заключается в последовательном

выполнении некоторого множества операций ___} >

причем, операции должны выполняться в указанном порядке. Для кавдой операции известен прибор j <е Üfj.íí^},

/ € {7.....г(}, выполняющий данную операцию. Предполагается,

что в любой момент времени кавдый прибор может обслуживать не более одного требования, время выполнения каждой операции равно единице и любые две соседние операции O^j и °íj+-¡ Должны выполняться на разных приборах, т.е. (l^j * • Прерывания в

процессе выполнения каждой операции запрещены, т.е. если - момент начала выполнения операции в расписании s,. то

t{j(s) = t°j(s) + 7 - момент окончания выполнения операции 0{^

в расписании s.

_ *

В разделе 3.1 решается задача нахождения расписание s ,

л

для которого значение целевой функции £ С, было бы минимальным.

t=1 1

Условимся представлять каждое расписание в виде таблицы

п

S, состоящей из двух строк и не более чем £ г, столбцов. Каждая

1=7 1

строка соответствует одному прибору и значение каждой позиции

п

S(h,g), Ы{1,2}, ge{7,..., £ г,}, определяется следующим

1=7 1

образом: S(h,g)=0¿^, если машина Uh в промежутке времени (g~1*8] выполняет операцию S[h,g)=0, если машина М в

промежутке времени (g-1,g] простаивает. В дальнейшем будем отождествлять расписание з и таблицу S. Предварительно подсчитаем для каждой операции 0ij коэффициент y^j по формуле yij = г{- J + 1. В процессе работы алгоритма столбцы таблицы S* заполняются последовательно, причем, каждую позицию очередного столбца займет операция, имеющая минимальное значение коэффициента среди всех операций, претендующих на данную

позицию в момент заполнения. Доказывается, что такой, алгоритм

строит оптимальное расписание для задачи J2\t¿j-llZ С{. Далее в

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

п

что оптимальное расписание строится за 0( £ г,) элементарных

i=1 1

действий. С помощью более компактного представления оптимального расписания, а именно, для того чтобы задать оптимальное расписание достаточно знать моменты начала выполнения первых двух операций каждого требования. Задачу можно решить за 0(n log п ) элементарных действий.

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

СРОКИ. Далее эту задачу обозначим (*).

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

Определим следующие массивы ЕА и ЕВ о z е {1,...,d>, d = wax d.

t 1

EA(z) = ¡ { 0tJ : 7{j s 2, (¡tj = A. J¿ e E } | EB(z) = j { 0tj : ytJ s z, litj = B, J( e E } j Можно доказать следующую теорему.

Теорема 3.1 Для множества В s J существует допустимое относительно заданных директивных сроков расписание тогда и только тогда, когда EA(z) s z и EB(z) s 2 для всех z е {1,...,d}. Итак, задача (*) свелась к следующей задаче (*#): Найти в J подмножество в максимальной мощности такое, что EAU) S 2 и EBU) S Z ДЛЯ всех z е { 1,...,d >.

Далее решаем задачу (**). Переформулируем ее в векторной форме. Для удобства, каждое требование J{ отождествим с вектором Jt={JAt,JBt), где ЛЛ{=(Л4{(1),...,J4((d)) и JBt=(JB£(1).

.... JBt(d)), и JAt(z)=llOtj:Je{1.....ri},UiJ=A,

JB^(z)=|{0^j:Je{1,...,¡I^j=B, для всех ze(1,...,d},

ie{1,...,n}, d = max d,.

i 1

Нетрудно видеть, что каждое требование J{ однозначно определяется парой векторов JAt и «7В{. Поэтому далее не будем различать требование Ji и вектор .

Таким образом задачу (**) можно переформулировать следующим образом:

Из множества векторов j{, ieti.....п>, необходимо выбрать

наибольшее число векторов, сумма которых не превосходит вектора

С=(СА,СВ)=(1,2,... ,d,1,2.....а).

Далее в разделе 3.2 доказывается, что эту задачу можно решить за полиномиальное время, а общая трудоемкость алгоритма составит оыЬ. Таким образом, за время 0(rJ) в задаче J2 |t£y=1|ЕУ{ можно определить множество требований, которые будут завершаться без нарушения директивных сроков.

В разделе 3.3 доказывается NP-трудность задачи J2IIE tWjVj, и разрабатывается алгоритм трудоемкости О(п^-г) для ее решения.

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

п t

Обозначим множество всех операций Q- U Q , которые должны

1=1

быть выполнены на т машинах 11 - { 111.....tf }, и пусть <2={ 1,

...,q }. Для каждой операции t известен прибор необходимый для ее выполнения, и длительность t^a0. Кроме того, предполагается, что множество всех операций частично упорядочено отношением строгого порядка: если I —*J, то t® + tj£ tj. Понятно, что множество приборов М разбивает все множество операций на т непересекающихся подмножеств Q^: i е Q^ тогда и только тогда, когда Ц{ = М^, ksra. Построим смешанный орграф G=(Q,C,D), где каждой операции i ставится в соответствие вершина с весом t{,

С = { (i,J)| t—»}, t € Q, J <= Q }- множество дуг, и D = ( [ij]| I Je Qk, fee и порядок

выполнения операций ( и / не определен} - множество ребер. Существует взаимно однозначное соответствие между множеством всех активных расписаний, допустимых относительно G, и множеством P(G) = {С.,,... } всех бееконтурных (

ориентированных ) графов, порождаемых графом G в результате замены каждого ребра [i,J] е D одной из дуг (t,J) или (J,t). Каждому орграфу G3=(Q,C3)aP(G) соответствует активное расписание з, при котором выполнение операции ieQ начинается в наиболее ранний срок £° начала операции t относительно (?3. Таким образом, для решения задачи необходимо найти оптимальную ориентацию ребер. Расписание, полученное с помощью ориентации всех ребер, будет допустимым, если результируквдий орграф будет бесконтурным. Длительности операций представим в виде вектора

i—^g)*

Оптимальное по быстродействию расписание s определяется орграфом Gs с наименьшим весом критического пути.

Так, задача J| (с^^, может быть сформулированна, как задача нахождения ориентированного графа Gs, минимизирующего вес критического пути среди всех ориентированных графов P(G).

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

Пусть ^-множество всех номеров s оптимальных орграфов G3<£ е P(G), Ф - множество неотрицательных действительных q -мерных векторов с чебышевской метрикой: тах{|t{-t{I |icQ}

-расстояние от вектора t до вектора t'-(t^.....t^). Замкнутый

шар Op(i) радиуса р с центром в векторе t будем называть шаром устойчивости орграфа Gs, sep(t), если для любого вектора t'c Op(t)fftP номер з принадлежит ?(£'). Наибольшее значение радиуса р шара устойчивости Op(t) будем называть радиусом устойчивости G3 и обозначать Pa(t). Если является шаром устойчивости

G при любом сколь угодно большом р, то p_(t)=oo. Далее мы

S S

получим условия существования расписаний с бесконечным радиусом устойчивости для систем типа job-shop, проверка которых требует полиномиального времени. Обозначим А^- {i \ i ~* j, I е Q \ Qk, J <£ Qfe) и Bk = {J | i -» j, J e Q \ Qk, I g Qr}. Рассмотрим фактор-множества A^'J и 5^/J, считая две операции i ж J

-не-

эквивалентными тогда и только тогда, когда 8то операции по обслуживанию одного и того же требования ( е Ql, J е Q1.

Справедлива следующая теорема. Теорема 4.2 Для задачи J|¡С^^, существует оптимальный орграф GseP(G) с бесконечным радиусом устойчивости тогда и только тогда, когда для любого прибора е if такого, что \Q}/J\ > 1> выполняются соотношения Mjgl5? и \Bk\sl, причем, если существует требование JjcJ , для которого А^ п g и О1-f . то в орграфе (Q.C) найдется путь из вершины / в вершину g или / = g.

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

о

быть проведена за время 0(g). В разделе 4.2 аналогичная теорема доказывается для задачи Лргес|^.

ВЫВОДЫ

1. Доказана полиномиальная разрешимость задачи минимизации произвольной неубывающей целевой функции для многостадийных обслуживающих систем с произвольными фиксированными порядками прохождения приборов требованиями, содержащих фиксированное число требований и два прибора при произвольном числе стадий обслуживания и произвольных длительностях операций, иными словами для задачи J2\n=k\F разработан алгоритм трудоемкости

2. Разработан полиномиальный алгоритм трудоемкости 0{п log п) для задачи минимизации суммарного времени обслуживания требований в системе с двумя приборами и одинаковыми длительностями всех операций.

3. Разработан полиномиальный алгоритм трудоемкости 0(л ) для

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

минимизации взвешенного числа запаздывающих требований в

системе с двумя приборами и одинаковыми длительностями всех операций. Для задачи J2\t(j-1|£ V{ предложен псевдополиномиальный алгоритм трудоемкости 0(г п7).

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

СПИСОК ОПУБЛИКОВАННЫХ РАБОТ

1. Кравченко С.А. Минимизация суммарного времени обслуживания для систем с двумя приборами, различными маршрутами и единичными длительностями.- Препринт / ИТК АН Беларуси.-Минск, 1994.- N4.-14 с.

2. Кравченко С.А. Оптимальное обслуживание требований в многостадийных системах с двумя приборами, различными маршрутами и одинаковыми длительностями операций.-Препринт / ИТК АН Беларуси.- Минск, 1995.- N7.-30 с.

3. Кравченко С.А. Полиномиальный алгоритм минимизации взвешенного суммарного времени обслуживания ограниченного числа требований двумя различными приборами / Ред.журн. "Весц£ АНБеларусС. Сер. ф1з.-мат. навук".- Минск, 1994.-24с.- Деп.в ВИНИТИ 10.03.94, N 573-В94.

4. Кравченко С.А., Сотсков Ю.Н. Оптимальное по быстродействию расписание с бесконечным радиусом устойчивости // Becui АН Беларус!. Сер. ф!з.-мат. навук - 1993.- N 4-'~ 0. 85 - 91.

5. Кравченко С.А., Сотсков Ю.Н. Полиномиальный алгоритм оптимального по быстродействию обслуживания трех требований двумя приборами / Ред. журн. "Весц( АН Беларус{. Сер. ф!з. - мат. навук".- Минск, 1994. - 45 с. Деп. в ВИНИТИ

09.06.93, N 1608-B93.

6. Brucker P.,Kravchenko S.A..Sotskov Yu.N. On the complexity of two machine job shop scheduling with separable objective functions.-Preprint/TJniversitat Osnabrueclc.- Osnabru-eck, 1995- 10p.

7. Kravchenko S.A. On the tvro-machine unit-time job-shop scheduling problem // Conference of the European Chapter on Combinatorial Optimization:Abstracts.-Poznan,1995.-P.52.

8. Kravchenko S.A., Sotskov Yu.N. Optimal makespan schedule for three jobs on two machines // ZOR.-1996.- V.43 -P.233-238.

9. Kravchenko S.A., Sotskov Yu.N., Werner P. Optimal schedules with infinitely large stability radius.-Preprint / Technische Universitat "Otto von Guerioke" Magdeburg.-Magdeburg, 1992,- 24 p.

10. Kravchenko S.A., Sotskov Yu.N., Werner P. Optimal schedules with infinitely large stability radius // Optimization.- 1995.- Y.33 - P.271-280.

11. Kravchenko S.A. Ihe polynomial-time algorithm for a 3|2| J,ti>0|Cma2 problem // Workshop on Discrete Optimization: Abstracts - Magdeburg, 1993.- P.33.

Резюме .

Кравченко Светлана Алексеевна

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

Ключевые слова: многостадийные системы, прибор, операция, стадия обслуживания, критерий оптимальности, допустимое расписание, полиномиальный алгоритм, псевдополиномиальный алгоритм, устойчивость оптимального расписания.

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

Рэзюме

Краучанка Святлана Аляксееуна

"Пабудова аптымальных раскладау для шматстадыйных с1стем з фл-ксаваным! маршрутам! абслугоування патрабаванняу".

Ключавыя словы: шматстадыйныя с!стэмы, прыбор, аперацыя, стадия абслугоування, крытэрый аптымальнасц!, дапу-шчальны расклад, пал1нам!яльны алгарытм, псеу-дапал!нам1яльны алгарытм, устойЛ1васць апты-мальнага расклада.

Аб'ектам даследвання з'яуляюода шматстадыйныя абслуговыя с!стэмы з ф!ксаваным! парадкам! праходаання прыборау патрабаванням!. Мэта працы зводз!цда да распрацоук! эфектыуных алгарытмау пабудовы аптымальных раскладау, м!н!м!зуючых дадзены крытерый аптымальнасц!. Праведзенныя даеледваню. 1стогна выкарыстоуваюць апарат тэоры! графау 1 творьи складанасц! вылгчэнняу, Асноуным1 выш.кам1 з'яуляюцца: распрацоука пал!нам!яльнага алгарытма пабудовы раскладу м1н!м1з1руючага адвольны рэгуляриы крытэрый для сл.стэм з ф1ксаванай колькасцю патрабаванняу, двума приборам! ! адвольнай колькасцю абслугоуваючых стадый; распрацоука пал1нам!яльных 1 псеудапалзяамхяльных алгарытмау пабудовы аптымальных раскладау для с1ствм з дзвума прыборам! ! аднолькавым! працягласцям! аперацый пры адвольнай колькасц1 патрабаванняу 1 стадий абслугоування; атрыманне неабходных 1 дастатковых умоу для !снавання аптымальных раскладау з бясконцым радыусам устойл1васц!. Усе вын!к1, атрыманныя у дысертацы!, з'яуляюода новым!. Вын!к! мокна выкарыстоуваць пры вырашэнн! практичных задач каляндарнага планавання ! аптымальнага упарадкавання.

Summary

Svetlana A. Kravchenko

"Optimal scheduling for Job shop systems"

Key words: job shop, job, operation, optimal criterion,

feasible schedule, polynomial algorithm, pseudo-polynomial algorithm, stability of an optimal schedule.

In the thesis the job shop problems are considered. The aim is to find a schedule minimizing some objective function. The investigations use the graph theory and complexity theory methods. The main results are the polynomial algorithms for constructing optimal schedule with given nondecreasing objective function for the job shop system with two machine and fixed number of jobs; the polynomial and pseudopolynomial algorithms for the two machine, unit time operations and any number of processing stages; the necessary and sufficient conditions for the existing optimal schedule with the infinitely large stability radius. All results are new. The results can be used for the production scheduling and optimal sequenoing.