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

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

ъГ-

РОМАНОВА Анна Анатольевна

РАЗРАБОТКА ТОЧНЫХ И ПРИБЛИЖЕННЫХ АЛГОРИТМОВ ПОСТРОЕНИЯ РАСПИСАНИЙ ДЛЯ ПРОИЗВОДСТВЕННЫХ

СИСТЕМ

05.13.01 — Системный анализ, управление и обработка информации (в научных исследованиях)

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

Омск - 2006

Диссертационная работа выполнена в ГОУ ВПО "Омский государственный университет им. Ф.М.Достоевского"

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

Сервах Владимир Вицентьевич.

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

наук, профессор

Севастьянов Сергей Васильевич, кандидат физико-математических наук, доцент

Симанчев Руслан Юрьевич.

Ведущая организация: Институт вычислительной математики

и математической геофизики СО РАН

Защита состоится 11 мая 2006 г. в 14 часов на заседании диссертационного совета ДМ 212.179.03 при ГОУ ВПО "Омский государственный университет им. Ф.М. Достоевского" по адресу: 644077, г. Омск, ул. Нефтеза-водская, 11.

С диссертацией можно ознакомиться в библиотеке Омского государственного университета им. Ф.М. Достоевского

Автореферат разослан апреля 2006 г.

Ученый секретарь диссертационного совета к.ф.-м.н., доцент

А.М.Семенов

Аор£А

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

Актуальность темы. На многих предприятиях производство представляет собой сложный технологический процесс, для управления которым требуется решать большое число задач эффективного распределения ресурсов и построения расписаний. В связи со сложностью рассматриваемых задач при принятии решений целесообразно использовать модели и методы системного анализа, исследования операций и оптимизации. Изучению таких задач и построению алгоритмов их решения посвящены [3, 4, 7, 8, 15] и другие работы.

В последние годы значительное внимание уделяется составлению циклических расписаний [9, 14, 16], которые часто используются в производственных системах в силу их простоты и удобства применения. Поэтому разработка эффективных алгоритмов решения таких задач является актуальным направлением в теории расписаний. Исследование задач построения расписаний для классических производственных систем, например, систем открытого типа, также представляет большой научный интерес ввиду их широкой известности и практической важности [5].

Многие задачи теории расписаний относятся к числу Л/Р-трудных. В связи с этим значительное число исследований посвящено разработке приближенных алгоритмов с гарантированными оценками точности, в частности, аппроксимационных схем, с помощью которых можно получать решения задач с любой наперед заданной точностью [1, 2,13]. Построение таких алгоритмов является одним из перспективных направлений в современной теории расписаний и других разделах дискретной оптимизации.

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

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

Научная новизна. В работе проведено теоретическое и экспериментальное исследование задач построения расписания и распределения ресурсов для ряда производственных систем. Предложены точные и приближенные алгоритмы решения задач сорт^щёЩЩ^Щ^^^го расписания и

библиотека.

С-Петер«у

ЛПОТЕКА I

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

Основные результаты работы заключаются в следующем.

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

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

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

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

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

Апробация работы. Результаты диссертации докладывались на XL Международной научной студенческой конференции "Студент и научно-технический прогресс" (Новосибирск, 2002), X Всероссийской конференции "Математическое программирование и приложения"(Екатеринбург, 2003), Российской конференции "Дискретный анализ и исследование операций" (Новосибирск, 2002, 2004), II Международном семинаре "Discrete Optimization Methods in Production and Logistics"(Омск-Иркутск, 2004), XVIII Conference of the European Chapter on Combinatorial Optimization

(Минск, 2005), а также на семинарах в Омском государственном университете, Институте математики им. С.Л. Соболева СО РАН и его Омском филиале.

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

Структура и объем работы. Диссертация состоит из введения, четырех глав, заключения и списка литературы (75 наименований) и приложения. Общий объем диссертации -113 страниц. В каждой главе используется своя нумерация параграфов, утверждений, теорем и формул. Работа содержит 12 рисунков и 2 таблицы.

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

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

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

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

Дадим постановки исследуемых в работе задач. Рассмотрим задачу построения циклического расписания для производственной линии, состоящей из т различных машин [9, 14, 16]. На этой линии необходимо произвести большую партию однотипных деталей. Все детали проходят одинаковый технологический маршрут обработки, состоящий из п операций. Операция ] требует р3 & единиц времени выполнения на машине у = 1,... ,п. Машины в технологическом порядке могут повторяться. На машине не может одновременно выполняться более одной операции. Прерывания выполнения операций недопустимы.

Дадим определение циклического расписания. Обозначим через к)

время начала выполнения j-ой операции для fc-ой детали. Расписание является циклическим, если для любого j = 1,... ,п и произвольного k € Z выполняется t(j: к) = t(j;k — l) + C, где С - время цикла или циклическое время. Очевидно, что t(j; k) = tj + Ск, где t3 = i(j; 0). Таким образом, циклическое расписание определяется заданием времени начала выполнения каждой операции для одной из деталей, например, величинами t3, j = 1,..., п, а также временем цикла С.

Кроме времени цикла, введем еще две характеристики циклического расписания: F - время нахождения детали в системе, т.е. промежуток времени между началом выполнения первой операции детали и завершением выполнения последней операции для той же детали; h - максимальное число одновременно обрабатываемых деталей. При этом считаем, что деталь находится в обработке, если выполнение каких-то ее операций уже началось, но последняя операция еще не завершилась.

Рассмотрим следующие варианты задач построения циклического расписания:

1) минимизация циклического времени С;

2) двухкритериальная задача минимизации С и F;

3) минимизация F при ограниченном С;

4) минимизации С при ограниченном h.

Первая задача полиномиально разрешима [9]. С остальными критериями задача становится /VP-трудной в сильном смысле [14, 16].

Далее рассматривается задача минимизации общего времени обслуживания в системе открытого типа, или open-shop. Она является классической в теории расписаний и состоит в следующем. Пусть имеется множество N = {1,2,...,п} требований и множество М = {1,2,...,т} обслуживающих приборов. Известны длительности ptJ > 0 обслуживания требования j прибором г для всех г е M,j € N. Каждый прибор может обслуживать требования в любой последовательности, но одновременно не более одного требования. Порядок прохождения приборов не задан и может быть различным для разных требований. Каждое требование одновременно обслуживается не более чем одним прибором. Процесс обслуживания требования прибором предполагается непрерывным. Необходимо построить расписание, при котором общее время обслуживания всех требований минимально.

Для задачи open-shop Гонзалесом Т. и Сахни С. [12] доказаны полино-

миальная разрешимость в случае двух приборов и NP-трудность при большем числе приборов. Севастьянов C.B. и Воегингер Г.Д. [lj предложили для этой задачи полиномиальную аппроксимационную схему (PTAS).

В этой же главе рассматривается задача управления поставками в следующей постановке. Имеется п поставщиков и m потребителей. Поставщики направляют некоторый продукт потребителям. При этом потребителю j требуется по крайней мере Aj единиц продукта, j = 1,..., то, а поставщик i не может доставить больше Mi единиц продукта, г = 1,..., п. Известна нижняя граница Шу для объема поставки от поставщика г потребителю j, i — 1,..., n; j = 1,..., т. Необходимо минимизировать суммарные затраты на поставку продукции при условии, что спрос всех потребителей будет удовлетворен. Пусть хч - объем поставки от поставщика г потребителю j, i — 1,..., n; j = 1,..., то. Исследуется задача с кусочно-линейной функцией затрат:

д. ) _ ή' если хч =

'J 13 \ a,ij + bijXij, если Xi} > О,

i = l,...,n;j = 1, ...,т.

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

Дх) = Ê Ê кг] (хгЛ -»• min, »=1j=i

Е Xi] > Aj, j = l,...,m,

m

E Жу < M„ i = l,...,n,

3=1

Xi, € {0}U [mtJ,Мг], г = 1,... ,n; j = 1 ,...,m,

Параметры c^, ôy, my, Мг, Л^ предполагаются целочисленными и неотрицательными для всех i,j.

Эта задача является ослабленной версией задачи управления поставками с вогнутой целевой функцией, рассмотренной в [11,10]: в ней потребителю j необходимо поставить в точности А3 единиц продукции, j = 1,..., то, а функции стоимости неотрицательные и вогнутые. Нахождение любого допустимого решения задачи в такой постановке является NP-трудной задачей даже при одном потребителе, хотя существует псевдополиномиальный точный алгоритм ее решения [10].

Рассматриваемая нами задача является TVP-трудной при фиксированном т, так как она содержит задачу о рюкзаке как частный случай. Кроме

того, задача нахождения допустимого решения является /VP-трудной даже для двух потребителей.

В случае нефиксированного т имеется еще более сильный результат. Еремеевым A.B. [23] было доказано, что задача управления поставками и задача нахождения р(п,тп)-приближенного решения, где р(п,т) - полином с положительными коэффициентами, NP-трудны в сильном смысле.

В связи с этим представляет интерес исследовать задачу в случае одного потребителя. Далее в работе будет показано, эта задача имеет наилучшую возможность приближения, т.е. для нее существует вполне полиномиальная аппроксимационная схема (FPTAS).

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

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

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

Для первой задачи предлагается точный алгоритм ее решения. Минимальное время цикла при этом равно суммарному времени выполнения всех операций на самой загруженной машине С* = max Е р„ где Ni -множество операций, выполняемых на машине г, г = 1,..., т. Идея алгоритма следующая. Начинаем выполнение операций в порядке, установленном в соответствии с технологией обработки детали, пытаясь это сделать тогда, когда освобождается нужная машина. Если нарушается отношение предшествования операций, то передвигаем выполнение текущей операции вперед на время, равное С*.

Достоинство циклического расписания с минимальным временем цикла в том, что детали выпускаются с наибольшей производительностью. Действительно, через каждые С* единиц времени производственная линия выпускает новую деталь. Недостаток такого расписания состоит в том, что выполнение детали может растягиваться на долгое время. Это требует транспортировки и хранения деталей, обработка которых еще не завершилась, а также большей потребности в оборотных ресурсах. В [21] построен

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

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

п

ЦРу

3=1

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

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

Характеристика Н становится важной, когда на производственной линии нет позиций для хранения незавершенных деталей, либо число этих позиций ограничено.

Утверждение 2.2. В циклическом расписании величины Г, С иН связаны соотношением к = .

Таким образом, при ограничении величины /г и минимизации времени цикла С одновременно ограничивается и время Р нахождения детали в системе. В связи с этим рассмотрим задачу минимизации времени цикла С при ограниченном числе одновременно обрабатываемых деталей. Заметим, что при Н >п эта задача полиномиально разрешима.

Ввиду ЛГР-трудности задачи встает вопрос о построении малотрудоемких приближенных алгоритмов. Прежде всего, рассмотрим вопрос о существовании вполне полиномиальной аппроксимационной схемы. Доказано, что если Р ф ИР, то в случае нефиксированного Н данная задача не имеет РРТА8. В главе 3 показано, что для задачи в случае фиксированного Я имеется наилучшая возможность приближения.

В п.2.3. рассматриваются две постановки задачи минимизации времени

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

Идея алгоритмов для обеих постановок схожая. Она состоит в следующем. Необходимо, чтобы в течение одного цикла был выполнен весь набор операций, но разные операции могут относиться к разным деталям. Причем в одном цикле могут присутствовать операции не более, чем Я различных деталей. Очевидно, что если в цикле выполняются операции j и к, принадлежащие одной детали, то и все операции j + l,j+2,... ,к — 2, к— 1 должны быть выполнены в этом же цикле. Поэтому из различных деталей необходимо взять различные цепочки операций. Учитывая, что цикл можно начать с любой операции, то действуем следующим образом. Сначала в технологическом маршруте идут операции первой детали, потом в каком-то месте происходит переход на другую деталь (при этом продолжение обработки первой детали выполняется в следующем цикле), потом - на следующую и т.д. Между операциями различных деталей нет ограничений предшествования. Это означает, что технологический маршрут разбивается на Я различных цепей. Если с каждой цепью связать деталь, то получаем известную задачу job-shop с Я деталями и т машинами. Решаем ее алгоритмом динамического программирования трудоемкости 0(2нНВ1В2...В) операций, где Вг - сумма длительностей операций г-ой цепочки. Таким образом, трудоемкость составляет не более 0(Н(2пртах)н) операций, так как Вк < прщах, где рт¡^ = max р.. Осталось только выбрать, в каких местах делать переход.

Сначала рассмотрим случай, когда к концу цикла нет незавершенных операций. В этом случае описываемый алгоритм будем обозначать CHi. Тогда число способов выбора набора переходов равно , т.е. 0(пн).

Теорема 2.4 Алгоритм С Hi решает задачу минимизации времени цикла при отсутствии к концу цикла незавершенных операций и ограниченном числе деталей, обрабатываемых в течение цикла, за 0(Н{2п2ртвх)н) операций.

Видно, что при фиксированном Н для 3 < Н <п алгоритм становится псевдополиномиальным. При Н = 2 результат может быть усилен.

Утверждение 2.5 Задача минимизации времени цикла в случае, когда в течение цикла обрабатывается не более двух деталей и к концу цикла нет незавершенных операций, полиномиально разрешима за время 0{пг\о^2 п).

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

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

Рассмотрим множество чисел

= рег,деМ,тД(р,д) = 1,д<Н}.

Теорема 2.5. Величина общего времени обслуживания С* в оптимальном расписании для задачи минимизации времени цикла при ограниченном числе одновременно обрабатываемых деталей принадлежит множеству <3я- Существует оптимальное расписание {£,} для этой задачи такое, что £4 € С}н, г = 1,..., п.

Таким образом, исследована структура оптимального решения этой задачи. Данная теорема дает способ решения задачи. Обозначим Р =

п

£ Р]- Тогда достаточно рассмотреть переходы в точках вида р/д, где р~=1,...,Р;д = 1,...,Я.

Алгоритм С#2-

Полагаем С* = пршах, = 0, г = 1,..., п.

Цикл от д = 1 до Н:

1. Выбрать Я — 1 операций ... ,0]И_,, в которых будем делать переход.

2. Определить момент перехода внутри каждой операции.

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

job-shop с дополнительными ограничениями и длительностями операций

_new_л«

Р] = QPj-

Пусть st - решение построенной задачи, i = 1,..., п, С - длина полученного расписания. Если C/q < С*, то обновляем текущий рекорд: С* = Cfq, U = зг/д+(к— 1 )С*, i = 1,..., п, где к - номер детали, в которой оказалась операция 02 (или 0j) при разбиении. Конец.

На первом шаге выбор можно сделать — 0(пн) способами. Внутри операции 0Jk переход достаточно произвести в точках вида u/q, где и = 0,1,... ,qpjh. Их количество не превышает 0(praaxq), где ртах — max р3. Так как для перехода необходимо выбрать Я — 1 операцию, то трудоемкость второго шага составляет 0((pmaxq)H).

На третьем таге сумма длительностей операций для каждой из получившихся Н деталей не превышает дРтЛХп. поэтому решение задачи jobshop требует не более 0(2НH(qpmilxn)H) операций.

Теорема 2.6. Алгоритм СЯг решает задачу минимизации времени цикла при ограниченном числе одновременно обрабатываемых деталей в общей постановке за время 0(2я(ртахп)2ЛЯзя+1).

Таким образом, алгоритм СЯг является псевдополиномиальным при фиксированном числе одновременно обрабатываемых деталей.

Результаты второй главы опубликованы в [21, 22, 25].

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

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

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

Под вполне полиномиальной аппроксимационной схемой будем пони-

мать семейство (И-е)-приближенных алгоритмов при всевозможных е > О с временной сложностью, полиномиально зависящей от длины входа задачи и от 1/е.

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

Теорема 3.1 Для задачи минимизации времени цикла при ограничении числа одновременно обрабатываемых деталей фиксированной величиной Н (3 < Н < п) существует вполне полиномиальная аппроксимационная схема. В случае, когда нет незавершенных операций к концу цикла, трудоемкость этой схемы составляет 0((~ + п2)я) операций. Для общей постановки задачи трудоемкость равна 0((у + п)2Н) операций.

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

Для упрощения обозначений запишем задачу управления поставками в случае т = 1 в более компактном виде:

Стоимость доставки продукции для г-го поставщика равна

ад Л0' ь

[а, + внесли х,- > О,

где > 0 и Ь{ > 0, i = 1,..., п.

Чтобы получить FPTAS для указанной задачи, сначала строится эффективный жадный 2-приближенный алгоритм, а затем - псевдополиномиальный алгоритм, основанный на динамическом программировании.

Рассмотрим жадный алгоритм Gr для более общей задачи, предполагая, что стоимости доставки kt(xt),i = 1,... ,п, заданы функциями

Е Ых») min,

n

Е xt > А,

Xi € {0} U [77lj,M,],i = 1,. . ~п.

0, если х, = 0;

а, + <7,(х^),если х, > 0,

где для всех г имеем щ > 0, а р,(а:г) - вогнутая неотрицательная неубывающая функция при ж,- € [0,М,-]. Через у = (у;) обозначим приближенное решение, построенное жадным алгоритмом (вначале оно нулевое); Ь - текущее количество продукта, которое необходимо доставить потребителю. При построении решения используем "жадное" правило:

выбрать ^ е {1,2,..., п} так, что yj = 0 и

к3( тт{тах{Ь,ш;},М7}) &«(тт{тах{£,1Пв}, М8}) т т{Ь,М3) ~ тт {Ь,М3}

для всех в таких, что уа = 0.

Пусть Т3 - верхняя граница временной сложности вычисления функции для всех г и хг.

Теорема 3.4. Жадный алгоритм (7г является 2-приближенпым алгоритмом для задачи управления поставками с вогнутой целевой функцией в случае одного потребителя.

В ходе построения алгоритма существенно используется следующее свойство [11]. Разрешимая задача управления поставками в случай одного потребителя имеет оптимальное решение г € Zn, где г* € {0, ттг,, М,} для всех г = 1,2,... ,п, кроме, может быть, одного.

Для построения ЕРТАв удобно использовать следующую переформулировку задачи (с учетом вышеуказанного свойства):

Е («¿и, + -> тт,

¿=1

Е (тПгЩ + (М4 - Шг)«,) > А,

»=1

щ < ии i = \,...,n.

щ е {0,1},ьг е г = 1 ,...,п.

Если в этой задаче условие дискретности для V, заменить на условие V, £ {0,1}, г — 1,...,п, то для ее решения можно предложить схему динамического программирования. Из рассмотренного свойства следует, что решение переформулированной задачи можно разбить на п этапов. На этапе г значение переменной г>г ищется в множестве {0, м ,..., 1} при щ = 1, а значения остальных переменных находятся с помощью схемы динамического программирования, г = 1,..., гг. Далее выбирается лучшее из полученных решений.

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

одного потребителя за 0{n2UВ) арифметических операций, где UB - верхняя оценка для значений целевой функции задачи.

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

Теорема 3.3. В случае одного потребителя для задачи управления поставками с кусочно-линейной целевой функцией существует вполне полиномиальная аппроксимационная схема с временной сложностью 0(пЦ + п2).

Результаты третьей главы опубликованы в [23, 24, 25].

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

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

Заметим, что общее время обслуживания требований приборами огра-

f rt т .

ничивается снизу величиной L™, = maxi max £ р„, max £ р» К

Допустимое расписание длины Lmax будем называть нормальным. Нами исследуется структура тех расписаний в задаче с п требованиями и тремя приборами, которые не являются нормальными.

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

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

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

критический путь.

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

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

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

В случае трех приборов и трех требований исследованы некоторые свойства критических путей.

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

/

дующих классов:

ххх

(хх-\

X--

'ххх^

X--

/ \ X X —

XX —

/ X X х^

— X — X--

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

В п.4.2 для этой предлагается модель целочисленного линейного программирования и исследуются некоторые ее свойства.

Результаты четвертой главы опубликованы в [17-20}.

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

Список литературы

[1] Воегингер Г.Д., Севастьянов С.В. Линейная аппроксимационная схема для многопроцессорной задачи Open Shop // Дискретный анализ и исследование операций - 1999. - Серия 1, Т. 6, N 2. - С. 3-22.

[2] Гене Г.В., Левнер Е.В. Эффективные приближенные алгоритмы для комбинаторных задач. - Препринт, 1981, Москва, ЦЭМИ.

[3] Конвей Р.В., Максвелл В.Л., Миллер Л.В. Теория расписаний. - М.: Наука, 1975.

[4] Попков В.К. Математические модели связности. В трех частях. ИВМ и МГ СО РАН. - Новосибирск, 2000-2002. - 560 с.

[5] Севастьянов С.В. Эффективное построение расписаний в системах открытого типа // Сибирский журнал исследования операций. - 1994. -Т. 1, N 2. - С. 67-99.

[6] Сервах В.В. Эффективно разрешимый случай задачи календарного планирования с возобновимыми ресурсами // Дискретный анализ и исследование операций. - 2000. - Серия 2, Т. 7, N 1. - С. 75-82.

[7] Танаев В.С, Гордон B.C., Шафранский Я.М. Теория расписаний. Одностадийные системы. - М.: Наука, 1984.

[8] Танаев В.С, Сотсков Ю.Н., Струсевич В.А. Теория расписаний. Многостадийные системы. - М.: Наука, 1989.

[9] Brucker P., Kampmeyer Т. Tabu search algorithms for cyclic machine scheduling problems. - Preprint, 2002, Osnabrueck. - 24 p.

[10J Chauhan S. S., Eremeev A. V., Kolokolcrv A. A., Servakh V. V. Concave cost supply management for single manufacturing unit // Supply chain optimisation. Product/process design, factory location and flow control. New York: Springer. Applied Optimization. - 2005. - V. 94. - P. 167-174.

[11] Chauhan S.S., Proth J.-M. The concave cost supply Problem // European Journal of Operational Research. - 2003. - Vol. 148, N. 2. - P. 374-383.

[12] Gonzalez Т., Sahni S. Open shop scheduling to minimize finish time // J.Assoc.Comput.Mach. - 1976. - V. 23, N. 4. - P. 655-679.

[13] Ibarra 0., Kim C.E. Fast approximation algorithms for the knapsack and sum of subset problems // Journ. of the ACM. -1975. - V. 22. - P. 463-468.

[14] Hanen C. Study of a NP-hard cyclic scheduling problem: The recurrent job-shop // European Journal of Operational Research. - 1994. - V. 72. -P. 82-101.

[15] Lenstra J.K., Rinnooy Kan A.H.G. Computational complexity of discrete optimization problems // Ann. Discrete Math. -1979. - V. 4. - P. 121-140.

[16] Roundy R. Cyclic schedules for job shops with identical jobs // Mathematics of Operations Research, - 1992. - V. 17, N 4. - P. 842-865.

РАБОТЫ АВТОРА ПО ТЕМЕ ДИССЕРТАЦИИ

[17] Романова А.А., Сервах В.В. О структуре оптимальных расписаний в задаче с нефиксированными маршрутами размерности 3x3. - Препринт, 2002, Омск: изд-во ОмГУ. - 40 с.

[18] Романова А.А. Об одной модели целочисленного программирования для задачи с нефиксированными маршрутами // Материалы X Всероссийской конференции "Математическое программирование и приложения", Екатеринбург, 2003. - С. 208-209.

[19] Романова А.А., Сервах В.В. О структуре оптимальных расписаний задачи с нефиксированными маршрутами // Материалы Международной конференции "Дискретный анализ и исследование операций", Новосибирск, 2002. - С. 221.

[20] Романова А.А. О структуре оптимальных расписаний в задаче с нефиксированными маршрутами // Материалы XL Международной студенческой конференции "Студент и научно-технический прогресс", Новосибирск, 2002. - С. 125-126.

[21] Романова А.А., Сервах В.В. О построении циклических расписаний для задачи обработки однотипных деталей // Материалы конференции "Дискретный анализ и исследование операций", Новосибирск, 2004. - С. 175.

[22] Романова А.А., Сервах В.В. Алгоритмы решения одной задачи построения циклического расписания // Материалы XIII Байкальской

международной школы-семинара "Методы оптимизации и их приложения", Иркутск, 2005. - С. 557-582.

[23] Chauhan S.S., Eremeev A.V., Romanova А.А., Servakh V.V. Approximation of linear cost supply management problem with lower-bounded demands // Proceedings of Discrete Optimization Methods in Production and Logistics (DOM'2004). Omsk. Nasledie Dialog-Sibir Pbs., 2004. - P. 16-21.

[24] Chauhan S.S., Eremeev A.V., Romanova A.A., Servakh V.V., Woeginger G. J. Approximation of the supply scheduling problem // Operations Research Letters. - 2005. - Vol. 33. - P. 249-254.

[25] Romanova A.A., Servakh V.V. On some cyclic machine scheduling problem // Abstracts of the XVII European Conference of Combinatorial Optimization (ECCO'2005), Minsk, 2005. - P. 58-59.

Отпечатано с оригинал-макета, предоставленного автором

Подписано в печать 03.04.06. Формат 60 x 84/16. Печ. л. 1,25. Уч.-изд. л. 1,3. Тираж 120 экз. Заказ № 99.

Отпечатано в издательско-полиграфическом отделе ОмГУ 644077, г. Омск, пр. Мира, 55а

¿OOGfy

74 V7

Введение

1. Задачи теории расписаний и сложность их решения

1.1. Формулировки задач.

1.2. Алгоритмическая сложность решения задач

2. Построение циклических расписаний для производственной линии

2.1. Сложность и свойства задач с различными критериями

2.2. Задача минимизации времени цикла с ограничением

2.3. Алгоритм для задачи минимизации времени цикла с ограничением

3. Аппроксимационные схемы решения задач

3.1. Основные определения.

3.2. Аппроксимационная схема для задачи минимизации времени цикла с ограничением.

3.3. Аппроксимационная схема для задачи о поставках продукции с одним потребителем.

4. Задача построения расписания для производственной системы открытого типа.

4.1. Исследование структуры оптимальных решений

4.2. Модель целочисленного программирования и ее свойства

На многих предприятиях производство представляет собой сложный технологический процесс, для управления которым требуется решать большое число задач эффективного распределения ресурсов и построения расписаний. В связи со сложностью рассматриваемых задач при принятии решений целесообразно использовать модели и методы системного анализа, исследования операций и оптимизации. Изучению таких задач и построению алгоритмов их решения посвящены [4,6,8,14,19,31,32,34,53,58,64] и другие работы.

В последние годы значительное внимание уделяется составлению циклических расписаний [44,56,70], которые часто используются в производственных системах в силу их простоты и удобства применения. Сложность задач построения циклических расписаний исследовалась в [55,56,60,63,65,70]. В силу трудности большинства таких задач основное внимание исследователей уделяется построению приближенных и эвристических алгоритмов. Такие алгоритмы предлагаются в [38,40,44,68]. С другой стороны, в [56,70] разработаны точные алгоритмы решения задач, основанные на методе ветвей и границ.

Исследование задач построения расписаний для классических производственных систем, например, систем открытого типа, также представляет большой научный интерес ввиду их широкой известности и практической важности [29,43].

Среди методов получения оптимальных решений задач построения расписаний следует выделить метод динамического программирования [2], метод ветвей и границ [43,56,70], различные алгоритмы комбинаторного характера [4,31,32,53,59].

При разработке методов решения задач теории расписаний важную роль играют свойства оптимальных решений, на основе которых поиск оптимального решения можно вести на сужении множества допустимых решений. Данный подход применяется к задаче построения расписания в производственной системе открытого типа [37,41].

Другим перспективным направлением является сведение задачи построения расписания к задаче целочисленного линейного программирования (ЦЛП). Этот подход используется, например, в [44,56]. В ряде известных методов решения задач ЦЛП применяется сведение исходной задачи к последовательности задач непрерывной оптимизации. На этом подходе основаны алгоритмы отсечения [3,11,34,35], декомпозиции [39], перебора L-классов [12], методы ветвей и границ [15,34].

Многие задачи теории расписаний относятся к числу iVP-трудных. В связи с этим значительное число исследований посвящено разработке приближенных алгоритмов их решения. Однако, как показывают современные результаты для ряда оптимизационных задач, мы сталкиваемся с некоторым "пределом приближаемости". Для одних задач существуют полиномиальные по времени аппроксимационные схемы (PTAS), когда при любом фиксированном е > 0 удается предложить полиномиальный алгоритм с относительной погрешностью, не превосходящей 1 + е. Для других задач не существует аппроксимационной схемы, но удается построить приближенные алгоритмы с константной оценкой точности. В этом случае имеется "барьер приближаемости", то есть такая константа С, что для любого С' < С задача нахождения С"-приближенного алгоритма является iVP-трудной задачей. Наконец, для задач третьего класса ни при какой константе С невозможно построение полиномиального С'-приближенного алгоритма (при условии Р ф NP). Естественно, важным представляется вопрос о том, к какому классу относится та или иная задача. В настоящее время исследование вопроса построения полиномиальных аппроксимационных схем представляет собой интенсивно развивающееся направление в разработке алгоритмов решения задач дискретной оптимизации [4,5,52,58].

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

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

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

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

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

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

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

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

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

Заключение

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

1. Ахо А., Хопкрофт Дж., Ульман Дж. Построение и анализ вычислительных алгоритмов. М.: Мир, 1979.

2. Беллман Р. Динамическое программирование. Москва: ИЛ, I960. - 400 с.

3. Булатов В.П. Методы погружения в задачах оптимизации. Новосибирск: Наука, 1977. - 161 с.

4. Воегингер Г.Д., Севастьянов С.В. Линейная аппроксимационная схема для многопроцессорной задачи Open Shop // Дискретный анализ и исследование операций 1999. - Серия 1, Т. 6, N 2. - С. 3-22.

5. Гене Г.В., Левнер Е.В.: Эффективные приближенные алгоритмы для комбинаторных задач. Препринт. - ЦЭМИ, Москва, 1981.

6. Гери М., Джонсон Д. Вычислительные машины и труднорешае-мые задачи. М.: Мир, 1982.

7. Гимади Э.Х., Глебов Н.И. Дискретные экстремальные задачи принятия решений. Учебное пособие. - Новосибирск: НГУ, 1991.

8. Гимади Э.Х., Глебов Н.И., Перепелица В.А. Алгоритмы с оценками для задач дискретной оптимизации // Проблемы кибернетики. М: Наука, 1975. - Вып. 31. - С. 35-42.

9. Глебов Н.И. Алгоритм составления расписания для двух работ // Управляемые системы. 1968. - Вып. 1. - С. 14-20.

10. Девятерикова М.В., Колоколов А.А. Анализ устойчивости некоторых алгоритмов дискретной оптимизации // Автоматика и телемеханика. 2004. - N 3. - С. 48-54.

11. Колоколов А.А. Методы дискретной оптимизации. Учебное пособие. - Омск: ОмГУ, 1984. - 75 с.

12. Колоколов А.А. Регулярные разбиения и отсечения в целочисленном программировании // Сиб. журн. исслед. операций. Новосибирск. - 1994. - Т.1, N 2. - С. 18-39.

13. Конвей Р.В., Максвелл B.JL, Миллер JI.B. Теория расписаний. -М.: Наука, 1975. 3G0 с.

14. Корбут А.А., Финкелыитейн Ю.Ю. Дискретное программирование. М.: Наука, 1969. - 368 с.

15. Кристофидес Н. Теория графов. Алгоритмический подход. М.: Мир, 1978. - 432 с.

16. Кук С.А. Сложность процедур вывода теорем // Киберн. сб. Новая серия. 1975. - вып.12. - С. 5-15.

17. Пападимитриу X., Стайнглнц К. Комбинаторная оптимизация: Алгоритмы и сложность/ Пер. с англ.- М.: Мир, 1985. 512 с.

18. Попков В.К. Математические модели связности. В трех частях. ИВМ и МГ СО РАН. Новосибирск, 2000-2002. - 560 с.

19. Романова А.А., Сервах В.В. О структуре оптимальных расписаний в задаче с нефиксированными маршрутами размерности 3x3. Препринт, 2002, Омск: изд-во ОмГУ. - 40 с.

20. Романова А.А. Об одной модели целочисленного программирования для задачи с нефиксированными маршрутами. Материалы конференции "Математическое программирование и приложения", Екатеринбург, 2003, С. 208-209.

21. Романова А.А., Сервах В.В. О структуре оптимальных расписаний задачи с нефиксированными маршрутами // Материалы Международной конференции "Дискретный анализ и исследование операций", Новосибирск, 2002. С. 221.

22. Романова А.А. О структуре оптимальных расписаний в задаче с нефиксированными маршрутами // Материалы XL Международной студенческой конференции "Студент и научно-технический прогресс", Новосибирск, 2002. С. 125-126.

23. Романова А.А., Сервах В.В. О построении циклических расписаний для задачи обработки однотипных деталей // Материалы конференции "Дискретный анализ и исследование операций", Новосибирск, 2004. С. 175.

24. Романова А.А., Сервах В.В. Алгоритмы решения одной задачи построения циклического расписания // Материалы XIII Байкальской международной школы-семинара "Методы оптимизации и их приложения", Иркутск, 2005. С. 557-582.

25. Сервах В.В. О задаче Акерса-Фридмана // Управляемые системы. Новосибирск: ИМ СО АН СССР, 1983, - Вып. 23. - С. 70-82.

26. Сервах В.В. Эффективно разрешимый случай задачи календарного планирования с возобновимыми ресурсами // Дискретный анализ и исследование операций. 2000. - Серия 2, том 7, N 1, -С. 75-82.

27. Севастьянов С.В. Полиномиально разрешимый случай задачи open-shop с произвольным числом машин // Кибернетика и системный анализ. 1992. - N 6. - С. 135-154.

28. Севастьянов С.В. Эффективное построение расписаний в системах открытого типа // Сибирский журнал исследования операций. 1994. - Т. 1, N 2. - С. 67-99.

29. Севастьянов С.В., Черных И.Д. Достаточное условие эффективной разрешимости задачи open shop // Дискретный анализ и исследование операций. 1996. - Т. 3, N 1. - С. 57-74.

30. Танаев В.С, Сотсков Ю.Н., Струсевич В.А. Теория расписаний. Многостадийные системы. М.: Наука, 1989.

31. Танаев В.С, Гордон B.C., Шафранский Я.М. Теория расписаний. Одностадийные системы. М.: Наука, 1984.

32. Тимковский В.Г. Приближенное решение задачи составления расписания циклической системы // Экономика и математические методы, АН СССР. 1986. - N 1. - С. 171-174.

33. Ху Т. Целочисленное программирование и потоки в сетях. М.: Мир. - 1974. - 520 с.

34. Шевченко В.Н. Качественные вопросы целочисленного программирования. М.: Физматлит. - 1995. - 190 с.

35. Akers S.E. A graphical approach to production scheduling problems. // Operations Research. 1956, - Vol. 4, N 2. - P. 244-245.

36. Akers S.B., Friedman J. A non-numerical approach to production scheduling problems. // Oper. Res. 1955, - Vol. 3. - P. 429-442.

37. Aldakhilallah К.A., Ramesh R. Cyclic scheduling heuristics for a reentrant job shop manufacturing environment // International Journal of Production Research. 2001, - Vol. 39(12). - P. 2635-2675.

38. Benders J.F. Partitioning Procedures for Solving of Mixed-Variables Programming Problems// Numer. Math. 1962. - Vol. 4, N 3. - P. 238-252.

39. Boudoukh Т., Penn M., Weiss G. Scheduling jobshops with some identical or similar jobs // Journal of Scheduling. 2001. - Vol. 4. -P. 177-199.

40. Brasel H., Harborth M., Tautenhahn Т., Willenius P. On the set of solutions of an Open Shop problem. Magdeburg, 1997.

41. Brasel H., Kluge D., Werner F. A polynomial algorithm for an open shop problem with unit processing times and tree conatraints // Discrete Appl. Math. 1995. - Vol. 59(1). - P. 11-21.

42. Brucker P., Hurink J., Jurisch В., Wostmann B. A branch & bound algorithm for the open-shop problem // Discrete Appl. Math. 1997. - Vol. 76. - P. 43-59.

43. Brucker P., Kampmeyer T. Tabu search algorithms for cyclic machine scheduling problems. Osnabrueck, Preprint, 2002, - P. 24.

44. Brucker P., Kravchenko S.A., Sotskov Y.N. On the complexity of two machine job-shop scheduling with regular objective functions. OR Spektrum. 1997. - Vol. 19(1). - P. 5-10.

45. Chauhan S.S., Eremeev A.V., Kolokolov A.A., Servakh V.V. Concave cost supply management problem for single manufacturing unit. In: Supply chain optimisation. Ed. by A. Dolgui, J. Soldek, O. Zaikin. Kluwer. Acad. Pbs., 2004. - P. 167-174.

46. Chauhan S.S., Eremeev A.V., Romanova A.A., Servakh V.V., Woeg-inger G. J. Approximation of the supply scheduling problem. // Operations Research Letters. 2005. - Vol. 33. - P. 249-254.

47. Chauhan S.S., J.-M. Proth: The concave cost supply Problem. // European Journal of Operational Research. 2003. - Vol. 148, N. 2, - P. 374-383.

48. Chen В., Potts C.N., Woeginger G.J. A review of machine scheduling: complexity, algorithms and approximability // Handbook of Combinatorial Optimization. Boston, MA: Kluwer Acad. Publ., 1998. V. 3. - P. 21-169.

49. Garey M.R., Johnson D.S. Scheduling tasks with nonuniform deadlines on two processors. SIAM J. Comput., 1977. Vol. 6(3). - P. 416-426.

50. Garey M.R., Johnson D.S. Strong NP-completeness results: Motivation, examples, and implications. // Journal of the ACM, 1978, Vol. 25, - P. 499-508.

51. Gonzalez Т., Sahni S. Open shop sheduling to minimize finish time// J.Assoc.Comput.Mach. 1976. - Vol.23. - N. 4. - P. 655-679.

52. Gonzalez Т., Sahni S. Flowshop and jobshop schedules: complexity and approximation. Oper. Res., 1978. - Vol. 26, N.l, - P. 36-52.

53. Hall N.G., Lee Т.Е., Posner M.E. The complexity of cyclic shop scheduling problems. //Journal of Scheduling, 2002. - Vol. 5, - P. 307-327.

54. Hanen C. Study of a NP-hard cyclic scheduling problem: The recurrent job-shop // European Journal of Operational Research. 1994.- Vol. 72. P. 82-101.

55. Hardgrave W.W., Nemhauser G.L. A geometric model and a graphical algorithm for a sequencing problem // Operations Research. -1963, Vol. 11, N 6, - P. 889-900.

56. Ibarra O., Kim C.E. Fast approximation algorithms for the knapsack and sum of subset problems.// Journ. of the ACM. 1975.- Vol. 22.- P. 463-468.

57. Johnson S.M. Optimal two-and-three-stage production schedules with set-up times included // Naval Res. Logist. Quart. 1954. -Vol. 1. - P. 61-68.

58. Kamoun H., Sriskandarajah C. The complexity of scheduling jobs in repetitive manufacruring systems // European Journal of Operational Research. 1993. - Vol. 70. - P. 350-364.

59. Karp R.M. Reducibility among combinatorial problems, in R. E. Miller and J. W. Thatcher (eds.), Complexify of Computer Computations, Plenum Press, New York, 1972. P. 85-103.

60. Kononov A., Sevastianov S. and Tchernykh I. When difference in machine loads leads to efficient scheduling in open shops // Annals of Oper. Res. 1999. - Vol. 92. - P. 211-239.

61. Lee Т., Posner M. Performance measure and schedules in periodic job shop // Operations Research. 1997. - Vol. 45. - P. 72-91.

62. Lenstra J.K., Rinnooy Kan A.H.G. Computational complexity of discrete optimization problems // Ann. Discrete Math. 1979. - Vol. 4.- P. 121-140.

63. McCormick S.T., Rao U.S. Some complexity results in cyclic scheduling // Mathematical and Computer Modeling, 1994. - Vol. 20. - P. 107-122.

64. Middendorf M., Timkovsky V.G. Transversal graphs for partially ordered sets: sequencing, merging and scheduling problems // J. Comb. Optim. 1999. - Vol. 3(4). - P. 417-435.

65. Prince C. Competetive genetic algorithms for open-shop sheduling problem // Math Meth Oper Res. 2000. - Vol. 52. - P. 389-411.

66. Rao U., Jackson P. Identical Jobs Cyclic Scheduling: Subproblems, Properties, Complexity and Solution Aproaches (Ithaca, NY: Cornell University Press), 1993.

67. Romanova A.A., Servakh V.V. On some cyclic machine scheduling problem // Abstracts of the XVII European Conference of Combinatorial Optimization (ECCO'2005), Minsk, 2005. P. 58-59.

68. Roundy R. Cyclic schedules for job shops with identical jobs // Mathematics of Operations Research, 1992, - Vol. 17, N 4, - P. 842-865.

69. Servakh V.V. A dynamic programming algorithm for somme project management problems. // Proceedings of the International Workshop "Discrete optimization methods in scheduling and computer-aided design", 2000. P. 90-92.

70. Sevast'janov S.V. Vector summation in Banach space and polynomial algorithms for flow shops and open shops // Math.Oper.Res. 1995.- V.20, N. 1. P. 90-103.

71. Sevastianov S.V., Woeginger G.J. Makespan minimization in open shops: A polynomial time approximation scheme // Math. Programming. 1998. - Vol.82, N 1-2. - P. 191-198.

72. Williamson D.P., Hall L.A., Hoogeveen J.A., Hurkens C.A.J., Lenstra J.K., Sevastianov S.V., Shmoys D.B. Short shop schedules // Opcr. Res. 1997. - Vol. 45, N 2. - P. 288-294.

73. Woeginger G. J. When does a dynamic programming formulation guarantee the existence of a fully polynomial time approximation scheme (FPTAS)? // INFORMS J. on Computing. 2000. - V. 12, N 1. - P. 57-74.