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

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

МИРЕЦКИЙ Игорь Юрьевич

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

Специальность 05.13.01 - Системный анализ, управление

и обработка информации

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

ПЕНЗА 2003

Работа выполнена в Пензенском государственном yнивepcитete и Волжском гуманитарном институте (филиале) Волгоградского государственного университета.

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

профессор Щербаков М. А.

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

профессор Сперанский Д. В.; доктор физико-математических наук, профессор Смирнов Ю. Г.; доктор технических наук Иванов А. И.

Ведущая организация — Институт проблем управления РАН.

Защита состоится 27 ноября 2003 г., в 14 часов, на заседании диссертационного совета Д 212.186.04 Пензенского государственного университета по адресу: 440026, г. Пенза, ул. Красная, 40.

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

Автореферат разослан «_» _2003 г.

Ученый секретарь диссертационного совета доктор технических наук,

профессор Смогунов В. В.

общая характеристика работы

Актуальность темы. Вопросам повышения эффективности функционирования систем неизменно уделяется значительное внимание. С середины 50-х годов XX века (после опубликования результатов исследований С. Джонсона и Р. Беллмана по планированию работы сборочных линий) для решения задач оптимизации работы дискретных систем активно используют модели и методы теории расписаний.

Исследования в теории расписаний имеют как теоретическую, так и практическую значимость. Они проводятся с целью уменьшения длительности производственного цикла, уменьшения запаздывания работ относительно установленных сроков и т. п., то есть в конечном итоге направлены на совершенствование механизмов планирования и управления производственными процессами. Этим объясняется неослабевающий интерес к задаче Беллмана-Джонсона и ее обобщениям - классу задач теории расписаний, связанных с решением проблемы составления оптимального плана работы систем последовательного типа (дискретных многостадийных систем). Задачи этого класса являются предметом диссертационного исследования.

Задачи теории расписаний в большинстве своем оказываются трудно решаемыми (Garey M. R., Johnson R. S.). Задача Беллмана-Джонсона является iVjP-трудной. Первоначально для ее решения предлагались точные подходы, а также метод случайного поиска (Heller J., Nugent С. Е.). Аналитические результаты получены в основном средствами комбинаторного анализа. Комбинаторные исследования проводились при рассмотрении частных случаев, для выявления условий элиминации и доминирования (Белов И. С., Бурдюк В. Я., Столин Я. Н., Johnson S. M., Gupta J. N. D., Nabeshima I., Szwarc W.).

Как точные методы решения задачи Беллмана-Джонсона и ее обобщений предлагались схемы ветвей и границ (Schräge L., Ignal Е., Dudek R. A., Campbell H. G., Lawler E. L., Lenstra J. K., Rin-nooy Kan A. H. G.), динамического программирования (Беллман P., Карп P., Якимов P. M.), целочисленного программирования (Manne A. S., Story A. E., Wagner H. M.). Однако точные методы можно

РОС НАЦИОНАЛЬНА» j БИБЛИОТЕКА j

использовать лишь для решения задач небольшой размерности.

После того, как была установлена NP-трудность задачи Беллма-на-Джонсона (Garey М. R., Johnson R. S., Sethi Ravi), исследования в основном проводятся в области приближенных подходов и связаны с построением эффективных приближенных алгоритмов. Наиболее интенсивные разработки ведутся в области алгоритмов с гарантированными оценками точности и алгоритмов локального поиска.

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

Другим перспективным направлением исследований является локальный поиск. На базе схем последовательного улучшения развились новые мощные средства - алгоритмы имитации отжига, поиск с запретами, генетические алгоритмы (Aarts Е. Н. L., Brucker Р., Werner F., Lenstra J. К., Taillard E., Glover F., Gupta J. N. D., Laguna M., Reeves С. R., Nowicki E., Smutnicki С.). Интерес к поиску в локальной окрестности носит не только практический, но и теоретический характер: исследуются сложностные аспекты и асимптотическое поведение алгоритмов. Проблемы в области локального поиска связаны с выбором окрестности и направления движения на множестве допустимых решений, со сложностью оценки качества решения.

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

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

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

Основные задачи исследования.

1. Построение математических моделей дискретных многостадийных систем.

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

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

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

5. Разработка эффективных алгоритмов для планирования работы систем последовательного типа.

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

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

Научная новизна работы.

1. Дана новая формализация задачи Беллмана-Джонсона. Построена математическая модель системы последовательной обработки с повторным обслуживанием.

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

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

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

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

6. Получены оценки эффективности преобразований, составляющих композицию, и условия согласованности оценок эффективности композиции и преобразований, входящих в ее состав. Доказаны необходимые условия эффективности композиции преобразований и предложены способы построения эффективных композиций. Разработан метод построения «-оптимальных расписаний (« > 2), основанный на проведении эффективных композиций преобразований.

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

8. Разработаны эффективные алгоритмы поиска «-оптимальных расписаний (я> 1), определена их сложность и доказана сходимость.

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

Аналитические результаты, представленные в работе, дают возможность строить легко реализуемые на ЭВМ эффективные алгоритмы синтеза приближенно оптимальных расписаний. Разработанные алгоритмы применимы для оптимального планирования работы различного рода систем последовательного типа, например, при планировании производственных процессов в сборочных, инструментальных цехах предприятий машиностроения и т. п. Использование алгоритмического обеспечения в АСУТП позволяет улучшить ряд показателей эффективности работы предприятий, в том числе увеличить объем производства на планируемый период, уменьшить длительность простоев оборудования по организационным причинам, снизить энергозатраты в расчете на единицу выпускаемой продукции, уменьшить штрафы, связанные с несвоевременным выполнением заказов.

Реализация и внедрение результатов. Результаты диссертационной работы в виде алгоритмов и пакетов программ внедрены в системах технологической подготовки производства Волжского подшипникового завода ОАО «ВПЗ-15», г. Волжский Волгоградской обл., и ОАО «Волжский трубный завод», г. Волжский Волгоградской обл.

Материалы диссертации используются в учебном процессе кафедры прикладной математики и информатики Волжского гуманитарного института (филиала) Волгоградского государственного университета при проведении курса «Теория расписаний».

Основные положения, выносимые на защиту:

1. Концепция «-оптимальности.

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

3. Математическая модель системы последовательной обработки с повторным обслуживанием.

4. Метод анализа матричных моделей дискретных многостадийных систем с помощью аппарата критических путей и их образов (развитие метода критических путей).

5. Метод преобразований при построении приближенно оптимальных расписаний, операторы преобразования расписаний и их свойства.

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

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

8. Метод построения «-оптимальных расписаний (« > 2) с использованием композиций преобразований и их семейств.

9. Алгоритмы синтеза «-оптимальных расписаний (« > 1).

Апробация работы. Результаты диссертационной работы докладывались и обсуждались на научно-техническом семинаре «Проблемы создания интеллектуальных САПР» (Геленджик, 1988), VIII Всесоюзной конференции «Проблемы теоретической кибернетики» (Горький, 1988), международных научных и научно-технических конференциях «Непрерывно-логические методы и модели в науке, технике и экономике» (Пенза, 1995), «Математические методы и компьютеры в экономике» (Пенза, 1996, 1997, 1999), «Логико-математические методы в технике, экономике и социологии» (Пенза, 1998, 1999), «Математические методы в технике и технологиях» - ММТТ-12 (Великий Новгород, 1999), «Математические методы и информационные технологии в экономике» (Пенза, 2000, 2001), «Математические методы

и информационные технологии в экономике, социологии и образовании» (Пенза, 2001), «Математические методы в технике и технологиях» - ММТТ-2000 (Санкт-Петербург, 2000), Четвертом сибирском конгрессе по прикладной и индустриальной математике - ИНПРИМ-2000 (Новосибирск, 2000), Российской конференции «Дискретный анализ и исследование операций» - ОАСЖ 2002 (Новосибирск, 2002), семинарах по дискретной математике и теории информации (Пенза, завод-втуз, 1987-1992), ежегодных конференциях профессорско-преподавательского состава Волжского гуманитарного института (филиала) Волгоградского государственного университета (1996-2003).

Публикации. По теме диссертации опубликована 51 научная работа, включая монографию, 22 статьи, 26 тезисов докладов и 2 изобретения.

Структура и объем работы. Диссертация состоит из введения, четырех частей, включающих 8 глав, заключения, библиографии из 190 наименований и приложений. Объем работы составляет 337 страниц основного машинописного текста и 26 страниц приложений; в диссертации 22 рисунка и 15 таблиц.

СОДЕРЖАНИЕ ДИССЕРТАЦИИ

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

Первая часть «Минимизация длительности производственного цикла в системах последовательной обработки» содержит три главы (1-3). В главе 1 «Преобразование расписаний в задаче оптимизации работы сборочной линии» и главе 2 «Построение приближенно оптимальных расписаний для систем конвейерного типа» рассматриваются модели систем с единым порядком выполнения работ на разных машинах, в главе 3 «Оптимизация в конвейерных системах без ограничений на очередность выполнения работ» исследуются системы обработки, в которых работы на разных машинах могут выполняться в различной очередности. Главы 1 и 2 являются основополагающими. Здесь дается концепция ¿-оптимальности, разрабатывают-

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

В главах 1,2 решается задача Fm \perm | Стах об оптимальном перестановочном расписании, состоящая в минимизации длительности производственного цикла в системах конвейерного типа. Рассматривается система из m последовательно работающих машин М\,..., Мт, на которых требуется выполнить п заданий-работ tu ..., /„. Работа tp j-\n, состоит из m операций 0\р ..., Omj, причем каждая операция О,j выполняется соответствующей машиной М„ г = \,т, за время ai}. Очередность выполнения работ на всех машинах одна и та же. Требуется определить оптимальную последовательность обработки (расписание), для которой общее время выполнения всех работ на всех машинах (длина расписания Стах» или просто С) минимально.

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

Математическая модель. Пусть Ри множество всех перестановок из и элементов 1, 2,..., п; р(г) - г-й элемент перестановки р е Р„. Перестановке р соответствует расписание п(р) = (fai),..., fa„)) е Р. Если p(r) = к, то работа в расписании %(р) занимает r-е место. Момент завершения выполнения /-й операции работы far) вычисляется по известной формуле и обозначается С^Г)(%, /). Длина расписания п(р) есть Ср(П)(п, m): С(п) = Ср(„)(я, ni). Задача состоит в нахождении расписания iw C(7t00t)=min С(п).

хеР

Задача решается на матричной модели. Работа tp j = 1 ,п, описывается вектором Aj-[a\p...,amj^, расписание п(р) - матрицей времен выполнения работ Л(тг(р))=[.4д1),...,/4р(П)]. Задача сводится к нахождению экстремальной перестановки столбцов в матрице А(п).

При решении задачи в матрице А(п) = [а,;]тхп рассматриваются пути и их сегменты. Последовательность элементов-клеток матрицы образует сегмент SCÍ¡ пути S = если первый ее элемент есть (a, ti), последний - (с, d) и любой элемент (/, г) Ф (с, d) предшествует одному из элементов (/ + 1, г) или (/, г+1). Множество элементов матрицы, расположенных на сегменте abScd, обозначается M(abScd).

Путь Su, сумма элементов матрицы А(п) вдоль которого максимальна, является критическим; ]T(( /j(r))6Su ai p(r) = С(я). Множество всех критических путей в матрице А{%) обозначается М(я); 1м(я) = {и | ие {1,2,...}, Su е М(я)}.

Оператор преобразования Qkj. Пусть п(р) - произвольное расписание, A(n) = [Ap(i), ...,Ар(„)]. Зададим над я оператор преобразования £\/, к, I е {1,..., и}, который переносит работу t^k) на позицию / и выполняет преобразование расписания п(р) в расписание 7ii = Q*,/(я), такое, что

А(п\) = [Ар( 1), Ар(2),..., Ар()ц), A^k+i),..., АрЦ), А[ф, A^i+iy,..., А^„)] при к < 1, A(ni) - ApQ),..., Ад-1),..., Ар^.х), А^щ,..., при к > I, А(щ) = А(л) при к-l(пустой оператор).

Композиция операторов преобразования (композиция преобразований) Q.ksulsX(Çlks_2j's_2...(Çlkuh(Çlkj(n(p))))...) есть последовательность nkJ(n), Пк[Л (щ),..., C2ts 2 /s 2(ns_2), П*,_1Л_, (ns_i) преобразований, где щ sn1(pï) = Qkl(n)eP, я2 = п2{р2) = Пки1}(щ) е Р иг. д-Расписание ns(ps) = Ciks_uis_1(Qks_2Js_2... (ft*b/l (QM(rc)))...) е Р однозначно определяется расписанием я и набором индексов к,1мкр 1Р где j = 1,5-1. Расписание л.pj е {1, ...,s- 1}, называется потомком исходного расписания я. Число непустых операторов преобразования, входящих в композицию, называется длиной композиции.

Концепция s-оптимальности. Доказана замкнутость множества расписаний класса Р относительно оператора i\/. Это позволяет использовать преобразования и композиции преобразований для нахождения оптимального расписания.

Пусть я, Я1 g Р — два произвольных расписания для системы заданий {/i,..., t„), а 0(я, Я]) - множество всех композиций, переводящих расписание я в щ. Обозначим через ir длину r-й композиции множества Г2(я, ж{) и образуем множество 1= {/ь ..., /„...}. Из множества П(я, яО выделим композицию минимальной длины s = min ir. Верно

неравенство 0 < s < п - 1, причем « = 0в том и только в том случае,

когда л = 7ti. Вводится функция p(7i,7ti) = « (= min ir). Доказывается,

irel

что эта функция определяет метрику на множестве Р.

S-окрестностъю расписания 7t называется множество P.Án) = {пг | %г е Р, p(7t,7t,) < «}.

Пусть критерий оценки расписания есть fin), а задача состоит в его минимизации. Расписание л называют оптимальным относительно критерия/в некоторой окрестности, если оно принадлежит этой окрестности nfi я) <flnr) для любого расписания лг из этой окрестности.

Расписание л* называется s-локально оптимальным, или просто s-on-тимапьным, относительно критерия fin), если оно оптимально (относительно f) в своей «-окрестности Р£п*): fin*) <finr), У(лг) б Ps(n'). Субоптимальным называется любое «-оптимальное расписание.

^-оптимальное расписание является «i-оптимальным при любом «i<«. Оптимальное решение является «-оптимальным при любом «. Субоптимальное решение тем точнее (ближе к оптимальному), чем больше значение «; (я - 1)-оптимальное расписание является безусловно оптимальным.

Понятие «-оптимальности применимо к широкому классу задач, которые можно поставить на множестве перестановок.

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

ni —> Пг -> — —> я, —» ... -> Яорь

где 7С| - исходное расписание, л, е Р^«(/) <«s i = 2,h, s(h) = s, причем fin,) <Дл), Ул б Р5(,)(л,_]). В целом схема описывает процесс последовательного улучшения, но при построении промежуточного расписания л, возможны отклонения от этого принципа. Процесс построения расписания л, иллюстрируется цепочкой

я,-] -> л/(1) -кл,(2) -> ... -> л,(i) -> ... -> = п„

где л,(<г) е Pk(n¡ i). Как и в процедурах имитации отжига, допускается ухудшение: возможно finl{k)) >.Дл,_1), k е {1,...,«(/)- 1}. Однако

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

Образ пути. В матрице А(п(р)) рассматривается сегмент Г«'г8г г, образованный при пересечении пути Би с г-м столбцом г = 1, п :

ЯнпЧ,г= гийги. (1)

Пусть тсхСрг) = С1к,£п(р)). Разобьем путь на три сегмента

^ = 'Ч.ПР,^)}, = ~к-%иЛ, 53 = \ {(*„,*)}.

В матрице А(К\) выделим путь = 51* и52* и5"3*, такой, что

1) 51* = 51, Я2* = 52, 53* = Я3, если к=1,

2) 81' = Я1, 5®' = Я2, й8' = {(«, г) | г < /, (5, г + 1) е 53 \ {*,„ к + 1}} и и /)} и {(5, г) | г > /, (.у, г) е Я3}, если к < I

3)^*»^, 53* = 53, 51*={(«,г)|г</,(5,г)е51}и{(/и,/)}и и {(я, г) I г > (5, г - 1) е 5"1 \ { ки, к +1}}, если к> /.

Путь в матрице А(щ) называется образом пути £„ в матрице А(п) при преобразовании О^КтО-

Эффективные преобразования. Определяется мера эффективности преобразования Ц^я): Д*./(я) = тах{С(я) - С{0.к,{к)), 0}. Преобразование 0Ь/(7с) называется эффективным, если > 0, и неэффективным, если А*,/(п) = 0. Аналогичным образом определяется эффективность композиции преобразований. Эффективные преобразования и композиции уменьшают значение критерия качества С(п) расписания («улучшают» расписание).

При анализе эффективности преобразований удобен аппарат образов путей, поскольку существует возможность сопоставления длины расписания п и оценки (снизу) длины его расписания-потомка п,:

Здесь Би* - путь в матрице А(%\{р\У), щ(р\) - являющийся об-

разом критического пути 5И е М(я).

Для произвольного пути £„ и индексов к, I е {1,..., и} вводится:

6?,00 =

к„-\

x (ai,p(k)-alip(k+i)) + (.aku,p{k)-aiuip(k)), к <l\ ,-к„ (2) -и

/=*» +1 Доказывается, что

Ак/(л)й min тах{8*/(л),0}, к, I е {1,..., п). (3)

»eiM(n)

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

Теорема 1. Для того чтобы расписание л было 1-оптимальным, достаточно, чтобы для каждой пары (к, I), к, I е {1,..., я}, существовало и е 1м(тс), такое, что (л) < 0.

В главе 2 разрабатывается метод построения «-оптимальных расписаний (s > 2). Для получения признаков «-оптимальности проводится анализ композиций преобразований и изучение их специальных свойств. Сначала исследуется проблема 2-оптимальности. Получена оценка длины расписания л2 ~ (Дь,/(я)) по исходному расписанию л и определены значения индексов к, I, к\, при которых композиция (Qkj(n)) является эффективной. Установлена согласованность оценок эффективности преобразований, входящих в композицию, с системой оценок (2), построенной для исходного расписания. Указан механизм построения эффективной композиции длины 2, основанный на использовании специального преобразования-склейки. Доказаны свойства склейки. Остановимся на общем случае (« > 2).

Построение «-оптимальных расписаний. Для получения «-оптимальных расписаний используются эффективные преобразования и композиции преобразований. Ключевым является вопрос оценки длины расписания

*s(Ps) = nki_lJs_1(nks_2,ls_2... (üku/l(ükJ(n)))...)ePs(n) (4)

по исходному расписанию я при произвольных значениях индексов преобразований к, I, кр l} е {1,..., п}, j = 1,« -1, то есть вопрос оценки эффективности композиции.

Для получения расписания ns(ps) (4) необходимо построить s -1 промежуточных расписаний-потомков

щ(р1) = Пк1(п\ щ(р2) = &кь1](щ\ -,its.l(ps.1) = Cik^bls_2(ns_2). (5)

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

р(к) * pik,), / = 1,5-1, р,(к,) * pj(kj), /, у = l,s-l, / Ф]. (6)

Ставится задача: определить значения параметров к, I, кр 1Р при которых композиция (4) эффективна. Для решения этой задачи строятся множества

H(<Sa,п)= {p(r)\ru=ru,\ <r<n}, V(Su,n)={i,...,n}\H(Stan), (7) где S„ - произвольный путь в матрице А(л(р)), а значения ги и ги определяются в соответствии с (1). В матрицах А(%\), А(п2),..., ^(tc.s.i) выделяются пути: Sl* - образ пути Su в матрице A(ni), S'u* - путь в матрице А(п,), являющийся образом пути S^1 в матрице А(щ.i), / = 2,5 . Доказывается следующее утверждение.

Пусть |Н(£И, 7t(p))| > s, ns(ps) определяется (4) и

p(k) е Н(Su, п), pik,) € Н( S'K, ,щ), i = 17-1 • (8)

Тогда существует, по крайней мере, ОЩ^, я)| - s) > 0 индексов v из множества {1,..., и}, таких, что 5"'w(ns) = 5" ^(тс), причем между парами (v, w) и (v, w) можно установить соответствие.

При доказательстве утверждения указывается способ установления соответствия между парами (v, w) и (v, w) и устанавливается инвариантность множества Н(5И, л) относительно преобразований Q/t/n), р(к) g V(SU, я). Утверждение показывает согласованность оценок: оценки 5/,(?!() эффективности преобразований расписаний-

потомков nh г = l,s -1, содержатся в системе оценок 5¿,/(л) (2), построенной для исходного расписания ж. В то же время пары индексов преобразований (к, I) и (к„ /,), / = 1,5 -1, однозначно определяют расписание (композицию) (4). Поэтому при выполнении условий (6) и (8) появляется возможность оценки длины расписания-потомка ns по исходному расписанию я.

Далее указывается способ конструирования эффективной композиции - вторая (и главная) часть проблемы синтеза 5-оптимальных рас-

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

Пусть в расписании л(р) определены s работ с индексами р(к0), р(кх), позиции которых следует изменить на /0, /,, ..., ls_x

соответственно. Эти работы и позиции могут быть выделены, например, в результате анализа системы оценок (2), в предположении, что проведение комплекса преобразований QE .(л), / = 0,s-l, приведет

к расписанию, длина которого меньше длины С(л) исходного. Суммарная эффективность преобразований Q. г(л), i = 0,s-\, оценивается как 8 (л) — ХГГо^с т (я)- Задача состоит в том, чтобы определить композиции , (Qkuh(nko lo(n)))...) и преобразова-

ния, их составляющие, для которых справедлива оценка 8 (л).

Задача не является тривиальной, поскольку нельзя применить s операторов Qt -(я), »= 0,s-l, к одному и тому же расписанию л.

*/■ ч

При решении этой задачи используется свойство инвариантности множества Н(Su, л). Показывается, что любая композиция вида (4), удовлетворяющая условиям (6) и (8), может быть описана последовательностью из s преобразований Ц^л) самого расписания л в виде схемы

Qtt>,/0), (*1 А).....(ks-l,ls-l№ ' ^

В записи (9) пары индексов (к,, It), i = 0,5 -1, определяют преобразования ^(л), которые необходимо провести. Запись (9) является схемой проведения преобразований. Показывается, что с помощью этой схемы описывается семейство композиций, в котором каждая композиция имеет оценку эффективности 8 (л). Устанавливается состав семейства. Указывается способ доопределения схемы (9) на случай, когда среди индексов к, существуют такие, что p(icj) е V(SU, л). После доопределения любую композицию из s преобразований, а значит, и любое расписание из окрестности Р*(я), можно описать схемой (9). Семейство расписаний, соответствующих схеме (9) при фиксированном наборе k,,Th / = 0,5-1, обозначается П,(я): Щл) = ^ i j 1}(л) с Ps(n). Механизм построения

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

Теорема 2. Пусть Н - произвольное подмножество множества {{к, t)\k& {1,...,«}, / е (1,...,«}}, |Н| = « > 1. Для того чтобы расписание я, е Щя) = где {k„l) е Н, ,' = 0,5-1,

обладало свойством C(ns) < С(я), необходимо, чтобы для каждого и е 1м(я) выполнялось либо Н n V„ * 0, либо

НлУ„ = 0и £ 8£Ля)+ £ 5 ¡tíl(n)>0.

(jF,,/,)eHnHÍ ' (f,J,)eHnH;

В теореме использованы следующие обозначения: я: = {(k,l)\p(k)en(Su,n), I е {1, и},5;,|(я)>о}, HZ ={(k,l)\p(k)en(Su,%), I б{1, n},5it/(ji)i0}, V„ = {(*,/)!/>(*) eV(SB, я), и}}.

Теорема 2 решает проблему выбора направления движения к локальному оптимуму. Из теоремы следует, что если выполняются условия 1) Эи е 1м(я): |Н~|ä« и 2) V/= 0,5-1: (fc¡,Ti) е Н~, то любое расписание из семейства (9) имеет длину, не меньшую, чем длина исходного расписания. Это следствие теоремы используется для элиминации неэффективных композиций преобразований.

Аналитические результаты, полученные в главах 1 и 2, являются основой алгоритмов синтеза приближенно оптимальных расписаний. Разрабатываются и исследуются эффективные алгоритмы поиска «-оптимальных расписаний («-оптимальные алгоритмы), доказывается их сходимость к некоторой точке локального минимума.

1-оптимальные алгоритмы А2.1 (градиентного типа) и А2.2 (прекращающий поиск в текущей окрестности при первом найденном улучшении) имеют сложность 0(п ). Сложность 2-оптимальных алгоритмов А2-3 и А2.4 (усеченный алгоритм А23) составляет 0(п5) и 0(п4) соответственно; в алгоритмах используются специальные свойства композиций длины 2 и преобразования-склейки.

^-оптимальный алгоритм А2.5 работает по схеме: 1) задаются точность решения Aog > 0 и размер окрестности s > 1; 2) выбирается исходное (опорное) расписание я; 3) в /-окрестности Р,(п) расписания я ищется расписание я„ удовлетворяющее условию С(л,) < С(я), где /

последовательно пробегает значения 1,2,..., s (поиск прекращается сразу после получения расписания я,); 4) если расписание я, найдено, то оно объявляется опорным (я := я,) и с ним выполняется п. 3, в противном случае я - искомое 5-оптимальное решение. Сложность алгоритма Ctyi2*1). Разработана модификация алгоритма А2.5 - алгоритм А2.6, сложность которого СНп).

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

В главе 3 решается задача Беллманаг-Джонсона (Fm 11 Спи*), в постановке которой, в отличие от задачи Fm \perm | Сщах (главы 1 и 2) отсутствует ограничение «очередность выполнения работ на всех машинах одна и та же». Требуется построить расписание, оптимальное относительно критерия С^: определить для каждой машины (индивидуальный) порядок выполнения работ так, чтобы общее время выполнения всех работ на всех машинах было минимальным. Оптимальное расписание принадлежит классу G э Р.

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

Псевдоработой t/Jc, г) работы t} называется группа операций Okj, Ok+lJ,..., Orj, последовательно выполняемых над работой t} на машинах Мк, Мк+и ..., М,. Псевдоработе tj{k, г) соответствует вектор

Aj{k, г) = [а;]их1 = [0,..., О, a¡g,..., аф 0,..., 0]т, 1 £кйг<т,

называемый фрагментом работы Наряду с г) и Afk, г) будем использовать обозначения tj и Аг Задача поиска оптимального расписания в классе G сводится к нахождению экстремальной перестановки псевдоработ следующим образом.

Рассмотрим класс R — {/?ь ..., Rn\ множеств всевозможных разбиений п работ t\,..., t„ на псевдоработы и соответствующий класс множеств фрагментов F = {Fb ..., F„). R} (Fj) представляет собой мно-

жество псевдоработ (фрагментов) работы tj. В классе R будем составлять перестановочные расписания для псевдоработ. Упорядочение я* псевдоработ t* е R] с RJt j = 1,л, называется допустимым (или расписанием класса G, я* е G), если

V/ = й: I Aj(k,r) = Aj, (Ю)

Aj(k,r)eF

Vj=\^,r<s: tj(k, r) < tj(s, t). (11)

Из множества всех допустимых расписаний необходимо выделить расписание минимальной длины. Достаточно рассматривать только квазикомпактные расписания. Далее под л* понимается допустимое квазикомпактное расписание класса G.

Пусть я - (ii,..., t„) 6 Р - расписание с матрицей времен выполнения работ А(л). В соответствии с (10) выполним произвольное разбиение работ на N>n псевдоработ. Упорядочение псевдоработ, выполненное в соответствии с (11), образует расписание it'eC с матрицей Л*(я*)= [.¿('i),^),...,^)]* где А'(к)- фрагмент некоторой работы tj. Фрагмент Л'*) соответствует псевдоработе t) = t*(k), находящейся на к-й позиции в расписании я*. Расписание я* е G, упорядочивающее N>n псевдоработ, можно рассматривать как перестановочное, если под системой заданий понимать систему из N псевдоработ. Поэтому

СфС, 1) = £a'lk J = 1 ,N, С(Г)(л*, i) = ¿>Îi, / = \,т,

к=\ ¿=1 __ _

С^(я*, /) = тах{С(д(я*, г - 1), Сс,_,)(я*, 0} + , i= 2,m,j= 2 ,N,

С(я*)=С(лг)(я*,ти). Здесь я', i)} ~ момент завершения обработки машиной М, псевдоработы, занимающей в расписании я* j-e место. Следует найти расписание С(я*р1) = ттС(л*).

Преобразование расписаний. Пусть к-ю позицию в расписании л* е G занимает псевдоработа /,. В классе G вводится оператор преобразования Qa,u» ^ е О» 2}, К le {l,...,iV}, ig {1,...,ти}, - обобщение fi и- fi 2,ит(л* ) = fiiX71* )• При кф2, ¡фт оператор fi/,.*./,, заменяет псевдоработу t] двумя псевдоработами //(1, i+h-2) и tj(i+h-1, m) и во вновь полученном расписании выполняет перенос или (,*( 1, i+h-2) на позицию / +1 (если h = 1, i Ф 1, к < Г), ил и tj(i+h -1, m) на позицию

/ (если h = 2,k>l). Cïh,KiÀ) e G-

Доказывается, что если nePun'eG- два произвольных расписания для системы заданий {t\,...,tn}, то л' за конечное число шагов может быть получено из ж последовательным применением оператора £1/, Отсюда следует, что оптимальное расписание Tt£pte G может быть получено за конечное число шагов из произвольного расписания п е Р последовательным применением оператора Пили-

Приведенные результаты позволяют при построении ¿■-оптимальных расписаний использовать методы глав 1, 2. Понятие s-оптималь-ности в классе G вводится так же, как в классе Р, только относительно оператора Qhxu-

Эффективность преобразований. Рассматривается произвольное расписание ж* е G, А(п* ) = [а* ] и определяются индексы

Критические пути Sp (правый верхний путь) и Su (левый нижний путь) в матрице А(тс* ) обозначаются RH и LD соответственно. Доказываются следующие условия эффективности преобразований.

Для того чтобы преобразование £\и<() было эффективным, необходимо, чтобы выполнялось одно из условий: 1 ) 3iRH > i: а*шк е M (RH) (в случае преобразования Qi.u» к < Г), 2) 3iw > г: а*юЛ е M(LD) (в случае преобразования Огждо ' ï т)-

Для того чтобы преобразование Qf„k,u(n' ) было эффективным, необходимо, чтобы в матрице А(п' ) не существовало ни одного критического пути, для сегмента r'y'lSrtW+} которого выполнялось бы неравенство min[min(£, /) - v, w - max(k, /)] > 0.

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

Доказывается аналог теоремы 1 — достаточное условие 1-оптимальности расписания класса G. Показывается, что для оценивания эффективности преобразований в классе G применима система оценок (2). Поэтому процедуры синтеза ¿-оптимальных расписаний можно строить, основываясь на принципах, описанных в главе 2. Все тео-

р - arg mm к *е!м(я')

X h у м = arg max

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

В главе 3 представлен алгоритм А3.1 синтеза 1-оптимальных расписаний класса G сложности 0(и3). Исследования 1-оптимальных решений, полученных с помощью алгоритма, показали, что доля расписаний, которые предписывают различный порядок выполнения работ на разных машинах, заметно растет с ростом т и п (на моделях с параметрами /м> 9 и «>20 эта доля превышает 0,7). При построении алгоритма используется утверждение: среди преобразований Qh,k,iAn') найдется, по крайней мере, одно неэффективное. Доказательство утверждения является конструктивным. Сначала показывается существование неэффективного преобразования. Затем произвольно выбирается преобразование Qh.k.i.ln*) и> в предположении, что оно неэффективно, определяются параметры h и i других неэффективных преобразований (сами преобразования не проводятся).

В главе также показана возможность использования методов исследований, описанных на примере задачи Fm \ perm | Cmax, для решения задач Fm \ r} | Стах (задача Fm \ | Ста* при неодновременном поступлении работ), Fm \prec | Сшах (задача Fm |) С^ при заданных отношениях предшествования работ) и Jm | | Стах (задача с разными маршрутами).

Вторая часть «Оптимизация в системах последовательной обработки при заданных директивных сроках» содержит две главы (4, 5). Решается задача Fm \ dj \ Тт^ составления расписания, минимизирующего максимальное временное запаздывание работ относительно заданных директивных сроков. Задача является М'-трудной. При ее решении обсуждается проблема построения оптимального расписания класса Р (в главе 3 было показано, что задача об оптимальном расписании класса G есть задача об оптимальном перестановочном расписании для псевдоработ). В главе 4 «Оптимизационный анализ системы» дается описание математической модели задачи и методов проведения оптимизационного анализа. При проведении исследований устанавливаются признаки эффективности преобразований (при

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

Для каждой работы j = \,п, помимо величины ач (длительность ее обработки машиной М„ i = \,т ), считается заданным директивный срок dj окончания ее выполнения. Запаздывание работы tj в расписании л(р) есть Tj{%) - maх(С/я, т) - dp 0), где С/л, т) - момент завершения выполнения работы Критерий оценки расписания л(р) есть 7;пах(л) s Г(л) = max Г.- (л) - максимальное временное запаздыва-

IS/S/I

ние. Задача состоит в нахождении расписания л0Р|: Г(л00,) = тт Г(л).

v яеР

Директивный срок и запаздывание работы занимающей в расписании л(р) = (/р(|),..., /р(Я)) е Pr-е место, обозначаются 4*г) и 7^Г)(л).

Классификация методов решения. Для решения задачи выявляются возможности улучшения (относительно критерия Гц^х) некоторого известного решения - исходного расписания л(р) = (t^,..., е Р. В расписании л(р) выделяются работы с максимальным запаздыванием, th^tp(r) - первая из таких работ. Предлагаются следующие варианты действий для уменьшения значения 7},(л) = Дл): 1) работу th перенести на позицию 1<г; 2) изменить порядковый номер некоторой работы tp(k), k<r, 3) выполнить транспозицию работ tv и tw, из которых одна предшествует 4, а другая следует за ней; 4) группу работ, предшествующих выполнять после работы 4; 5) переупорядочить работы, предшествующие При построении алгоритмов могут использоваться и различные комбинации пунктов 1-5.

Варианты 1-2 формально описываются с помощью оператора Q*,/, варианты 3-5 - с помощью композиций преобразований. Поэтому задачу построения субоптимального расписания относительно критерия Тшх можно решать (как и для Стах), используя технику преобразований расписания. «Улучшение» расписания связывается с проведением эффективных преобразований и композиций. Эффективность преобразований и композиций относительно критерия Гшах определяется аналогично тому, как это было сделано для критерия Стах. Все варианты решения предусматривают исследование частичных расписаний o^v, w) = ..., t^)) расписания к(р). Частичное распи-

сание из j первых работ расписания л обозначается ол(/).

Условия эффективности преобразований. Определяется резерв времени А См работы tp^, j-\,n, в расписании п(р) - величина, на которую можно перенести во времени окончание выполнения последней операции этой работы, не нарушив условия Тр^(п) < Т(п):

АСМ = (Сцг№, m) - dm) - (СЛ)(л, да) - dptf).

Рассматривается преобразование Ог/л), 1<г и строится расписание Jii(pi) = Qr.i(n) (см- классификацию методов решения, вариант 1). Интерес представляют условия, которым должен удовлетворять параметр / преобразования С1гЛп\ чтобы выполнялось неравенство ДЛ]) < 7а(я) (параметр г известен изначально: это порядковый номер работы //, в расписании я). Сравнение запаздываний работ в расписа-. ниях я(р) и щ(р\) показывает, что щ(р{) предпочтительнее п(р), если Уу = /^:Ги0)(л1)<ГЛ(я). (12)

Следует определить условия, при которых выполняется система неравенств (12). Эти условия позволят указать значение параметра I эффективного преобразования

Показывается, что для оценивания эффективности преобразований относительно критерия Т^ можно использовать оценки, полученные в главе 1 для критерия Ста*-

Доказывается условие эффективности преобразования где

г > /, 7*г)(я) = Th(я) = 1\%)\ для того чтобы расписание Я1 = £\/(я) обладало свойством 1\щ) < Дл), необходимо, чтобы выполнялись условия

V« е 1м(о*(>-)): £ altP(j) > 0, где с Su{ajr)\

V/ > г: + ДСт > О, V« е 1м(),

V/ =17^1: АСм - а-^ > 0, Vu е Ы<*Ш .Здесь сегмент определяется в соответствии с (1), а

5"/(ок(у)) вводится для частичного расписания оп(/) по правилу (2).

Левые части неравенств в утверждении оценивают эффективность преобразований. Аналогичные утверждения доказаны для преобразова-

ний Цу(я), к<г (см. классификацию методов решения, вариант 2). В совокупности утверяедения дают необходимое условие эффективности преобразования Оуи,(л) при произвольных е {1,..., п}. Невыполнение этого условия достаточно для 1-оптимальности расписания.

Частичные расписания-потомки. Для оценки эффективности композиций относительно критерия Сю« выполнялся совместный анализ расписания я и его потомков п„ i = \,s-\ (5). В случае критерия Т^ подобный анализ проводится для частичных расписаний. Упростим систему обозначений: о(/) = а^/), о,{/) - начальная последовательность в расписании л(.

Непосредственным потомком частичного расписания о(/) при преобразовании 0*,/(я), к, I е {1,..., л}, кФ], называется частичное расписание о^) = ОрР(тс) расписания 711 = О/и(я), в котором

У, У < тт(к, I), у > тах(*, /), У,='У-1,

У+1, 1^]<к.

Понятие потомка частичного расписания вводится так же, как и для полного расписания. По аналогии с представлением ял(р^) в виде композиции (4) частичное расписание оД/Д являющееся потомком о(/), описывается композицией длины 5:

Ш=■■■ (13)

а1(/-.)=о^/)(7с), о2(/2)= едч*,). • (14)

Анализ эффективности преобразований Пц(л) для частичных расписаний о(Д У = 1,« , проводится в терминах образов путей. При этом следует учесть, что матрицы А(о{])) и А(а\Ц\)), где ОгС/]) = С^/^л), могут иметь разные размеры, в то время как определение образа пути основано на сопоставлении путей в матрицах А(п) и А(С1к!(л)) одного размера тхп. Для решения этой проблемы вводится понятие образа-потомка пути (обобщение образа пути на случай матриц разного размера).

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

условия эффективности преобразований, строится функция S",/(Tmax>0(./)) ~ аналог 5"/(я) на случай критерия Гщах. При каждом je {1,...,я} величина 5£/(Гтах, а(у')) есть оценка эффективности относительно критерия Ста* преобразования П*,/(я), которая строится относительно пути Su в матрице A(p(j)) для расписания я = а(п) или для одного из его частичных расписаний a(f):

<^0,(0*,/(я), m) ^ СЮ)(л, w)-5^(rmax, о(/)) • Оценка эффективности 5£ /(Ггаах,о(/)) не определена при у = А: (для частичного расписания а(к), которое при преобразовании й*Хя) не имеет непосредственных потомков).

Функция З^ДГтах, аО')) используется при оценивании эффективности композиции преобразований. Для композиции преобразований (4) строится множество М(я^) = {1,2,..., и}\{/?(£0), ),...,p(^-i)}, где ¡р(к0)>1рщ)т--> ~ работы, над которыми выполняется опе-

рация переноса: р{к,)-p,{kj), г-1,5-1, к0 = к. Для частичных расписаний а(/), j е {р(к0), р(к{),..., />(£s_i)}> оценка 5" w(rmax,o(y)) является неопределенной. Элементам j множества М(я5) соответствуют частичные расписания о(/), для которых оценка 5" w(rmax, 0(7')) определена относительно всех преобразований, входящих в композицию. Множество индексов М(яs,j),j е М(я.,), определяет работы, входящие в частичное расписание о(/), над которыми в композиции выполняется операция переноса. Множество М(я5) обладает свойством: оно содержит одни и те же элементы, вне зависимости от того, в каком порядке выполняется перенос работ tp(ks_x)- До-

казывается следующее утверждение.

Пусть яi(ps) - композиция (4), j € М(я,), a(j) - начальная последовательность расписания я(р), а Su(o(J)) - произвольный путь в матрице A(a(j)). Пусть, далее, при любом /е {0,1,..., s-1}, удовлетворяющем условиюр(к,) е М(яs,f), для частичного расписания о(/) и его потомков а,{/,) (13), (14) выполняется

1) р(к) е H(Su(a(j)), o(j)\ если / = О,

2) />,<*,) е Н( S'u* (а({/;)), а,{/,)), если / е {1, ...,s-\}.

Тогда для любых j е М(ят) и г е {1,..., s} существует, по крайней мере, |H(Sa(a(/)), о(/))| - \M(frag(nn r),j)\ индексов ve «}, та-

ких, что 5^(Гтах,о,0")) = 5?>й(Гтах,о(у)), I = 1,г, г = 1,5, причем между парами (v, w) и (v, w) можно установить соответствие.

В утверждении frag{п„ г) - фрагмент композиции (4), состоящий из г первых преобразований (фрагмент определяет расписание: п,(рг)= fragiя4, г)). В утверждении также использованы обозначения: S]u- (а,(/',)) - образ-потомок пути Su(a(j)) в матрице A(ax(j\)), S'u, (а,(/,)) -путь в матрице А(а,(/,)), который является образом-потомком пути S'UJ (0/-i(//-i)) в матрице Л(ам(/м)), i = 2,s. Множество H(Su(o(j)), о(/)) строится по аналогии с (7).

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

Эффективные композиции длины s. Любая композиция (расписание) ns(ps) = (0.ki 2js 2... (Пк1Л (Qм(я)))...) входит в некоторое семейство расписаний Щя) = ^ ^ ^ ^ ]|}(л). В соответствии со свойством множества М(я5), его состав не зависит от порядка проведения преобразований. В этом смысле множество М(ял) является характеристикой семейства Щя), и можно говорить, что М(л(.) = М(П5(я)).

_Теорема3. Пусть Н, |Н| = я>1, - произвольное подмножество

множества {(Ar, /) | к е {1,..., п}, I е {1,...,«}}. Для того чтобы расписание я, из семейства Щя) = -Ak-ü,-^' гДе (k,,Z) е Н,

/ = 0,5-1, обладало свойством 7Xns) < Т{п), необходимо, чтобы при любом j е М(П,(я)) для каждого и е 1м(о(/)) выполнялось либо

1) Н с Н+(5„(о(/)), о(/)) и £ Ц, т (.Т»,<*МЛ) + АСрО) > 0» либо

2) Н et n\Su(ü(j)), oQ)),

где Н+С) = {(*, /) \р(к) е Н(-) u [p(j+ l),p(j + 2), ...,р(п)}, I е {1,...,»}}.

Теорема дает признак эффективности композиций преобразований, входящих в некоторое семейство. Признак эффективности является конструктивным. На его основе строятся s-оптимальные алгоритмы.

Третья часть «Оптимизация работы систем с повторным обслуживанием» состоит из глав 6 и 7. Решается задача Fm | repeat | С11шх минимизации длительности цикла обработки. В главе 6 «Построение и анализ модели» дается постановка задачи, описываются формы представления расписаний, показывается возможность применения оператора преобразования. Определяются условия, которым должны удовлетворять матричные модели задач, чтобы при оптимизационных исследованиях можно было использовать методы глав 1-3. Разрабатываются матричные модели. В главе 7 «Оптимизация работы системы» решается задача синтеза s-оптимальных расписаний.

По сравнению с задачей Fm 11 Сшах задаче с повторным обслуживанием Fm | repeat | Cmax присущи следующие дополнительные ограничения. Каждая работа t}, j = \,n, выполняется в два этапа и состоит из т операций 0\},..., 0]mj первого этапа обработки и т операций Ofj,...,Olj второго этапа обработки. Операция О" (а= 1, 2 - номер этапа) выполняется соответствующей машиной М„ i = \,m, за время а*. Операции первого этапа обработки работы t, образуют ее первую стадию t), операции второго этапа - вторую стадию tj. Для каждой работы сначала выполняется ее первая стадия, затем вторая: t) < t]. Маршрут прохождения по машинам один для всех работ (стадий): М\, Mi,..., М„. Для каждой работы (стадии) выполнение очередной операции начинается не ранее, чем окончится выполнение предыдущей операции. Требуется построить расписание минимальной длины (С(л) -> min).

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

Дисциплины обслуживания и допустимые расписания. При исследованиях системы можно столкнуться с двумя вариантами организации ее функционирования, которым соответствуют две различные схемы обслуживания: 1) дисциплина раздельной обработки стадий (V/, к е {1,..., и}: t)< tj ) и 2) дисциплина смешанной обработки

стадий (j,ke ...,«} Ф t)< t2 ). В первом случае сначала выполняется обработка всех первых стадий работ, а затем обработка всех вторых стадий. Второй случай является общим: допустимо предшествование t2<t), если только t)<t] и t\<t\.b диссертации исследованы оба случая и показано, что если система допускает обе дисциплины обслуживания, то оптимальное расписание предполагает смешанную обработку. Показывается ММрудность задачи Fm | repeat | Cmax. Рассмотрим общий случай.

Пусть- перестановка 2и индексов ih...,i„,jh...,jm ik,jkе {1,...,л}, к - \,п, удовлетворяющих условию (ik- jk, p(l) = ik, p(r)=jk) => I <r, а Ргл - множество всех таких перестановок. Перестановка р еТы определяет единственный способ упорядочения стадий работ:

tp( 1) -< tp(2) ■< - -< *р(2п),

где 7Р(!) = t}k, если p(l) = ik, и 7р(1) = t)f> если/К/) =jr.

Доказывается, что оптимальное решение задачи Fm | repeat | Сгаах принадлежит множеству Р2 квазикомпактных перестановочных расписаний вида я(р)=(?р(1),/р(2), ..., tp(2n)), Р е Ргя. Между множествами Р2 и Р2я устанавливается взаимно однозначное соответствие.

Под допустимым понимается расписание л(р) е Р2, р е Р^; задача состоит в нахождении расписания 7topt: С(яор,) = minC(7t).

пеР2

Преобразование расписаний. Взаимно однозначное соответствие между множествами Р2 и Р& позволяет использовать оператор DVjW на множестве Р2 при определенных ограничениях на индексы v и w преобразования. Пара (v, w) является допустимой для задачи Fm | repeat | Сшах, если для реР^ выполняется QVyW(n(p)) еР2. Указывается способ построения множества D2(ji) допустимых пар индексов (v, w). При исследованиях рассматриваются допустимые операторы iiv v„ (в которых (v, м>) е Б2(л)) и допустимые композиции преобразований (состоящие из допустимых операторов).

Доказывается, что если щ(р{) еР2 и яг(рт) е Р2 - два произвольных расписания для системы заданий {t\,..., („}, то одно расписание может быть получено из другого ¿-кратным (s<.2n- 2) применением оператора Qv,w.

Матричная модель. Стадии i", а= 1, 2, работы описываются векторами AJ = [at", ..., Матрица времен выполнения стадий

работ расписания л (р) =(7р0), Тр(2), ..., 7р{2п)),р е Р2п, есть

А(л(р)) = [Apix^ApQ.), ...,Арф,)], где AP(f)=[aiJ1(rj,...,amp(i)]T- один из векторов Af, компоненты которого есть

к, если 7p(l) = /},

ai,p(l) - 1 2 У

[afj, если tp0) =tj.

Чтобы при исследованиях можно было использовать методы, разработанные в главах 1 и 2, матричная модель А2(л(р)) для задачи Fm I repeat | Cmax должна удовлетворять следующим двум условиям.

Условие 1. Матрица А\л(р)) должна состоять из 2п столбцов, описывающих длительности операций стадий работ, то есть должна быть построена на основе матрицы времен выполнения А(л(р)).

Условие 2. Пусть Ау(л(р)) - подматрица, образованная удалением из матрицы А2(л(р)) строк / + 1,..., m и столбцов j+ 1,..., 2п. Для любых i б {1,..., m},j е {1,..., 2и} сумма элементов, находящихся на критическом пути в матрице А2(п(р)), должна быть равна величине СрЦ)(л, i) (моменту завершения выполнения /-й операции стадии 7р{]) в расписании л(р)).

Ключевую роль при построении модели А2(л) и определении условий эффективности преобразований и композиций играют так называемые важные работы. Относительно любого расписания л е Р2 множество всех работ может быть разбито на две группы. Первую группу образуют «несущественные» работы. Для любой такой работы tj момент начала обработки стадии tj не зависит от момента С) (л, m) окончания обработки ее первой стадии t). Вторую группу образуют «важные» работы, моменты начала выполнения вторых стадий которых зависят от моментов окончания обработки их первых стадий.

Показывается, что в любом расписании л(р) s Р2 множество важных работ непусто. Для построения множества важных работ пред-

лагается алгоритм а6.2. Его вычислительная сложность составляет 0{п2).

Пусть множество важных работ в расписании тс(р) состоит из / элементов 1к): ^ х /Д ^ ^ ^ ^ ,2 и ^ (/ = 1,1*). Мат-

рица А2(п(р)) строится по правилу

ПАо(п(р))

А2(п(р)) =

(15)

а0.р(г) ~

А(п(р))

где Ай(п(р))=[a0iP(i),...,ао,р(2п)] - 2л-мерный вектор с компонентами о, Г g {1,2,..., 2п) \ {j\, j2,j*},

Ci, (я, те), r = ju (16)

_Cl,(n,m)-Cli_i(n,m), r = j„ /е{2, ..., /*}.

Матрица, построенная по правилам (15) и (16), удовлетворяет условиям 1 и 2, предъявленным к матричной модели.

Процесс формализации задачи (построения математической модели) завершается набором рекуррентных соотношений для расчета моментов Срц)(п, г), j = 1,2п, i~\,m, окончания выполнения операций стадий работ 7p(j) в расписании п(р).

Типы критических путей. Исследования систем с целью оптимизации их функционирования связаны с анализом критических путей и их образов в матричных моделях. В матрице А2(п) форма критического пути во многом определяется важными работами в расписании. Любой критический путь в матрице А2(п) имеет либо тип RD... (который содержит сегмент вида 0,<So„ г S 2), либо тип DR... (который содержит сегмент вида 0lS,i, i> 1). Множество всех критических путей S„ типа RD... (DR...) в матрице А2(п) обозначается Мщ^я) (&Мя)).

Если МиХя) = 0, то вектор Ао(п) не принимается в расчет, и исследования проводятся на матрице А(п), а не на модели А\п). Условие (3) и теоремы 1, 2 достаточно просто переносятся на случай задачи Fm | repeat | Cmax. Далее будем полагать Мщ}(л) Ф 0 и рассматривать пути типа RD...

Анализ преобразований. Доказывается, что если Мщ(л(р)) = 0, а г - наименьшее из чисел 2,3,..., 2я, при котором сегмент 0г£1г принадлежит критическому пути, то - вторая стадия важной работы. Пусть - сегмент, оговоренный выше.

Положим, что столбцу г матрицы А\п{р)) соответствует стадия = аг£(У^ = Тр(г)), а позиция стадии в п(р) есть

с = атё(ГЮ)=11н)- (17)

j

Тогда работа tkk - важная в расписании л(р). Из множества критических путей матрицы А2(п(р)), содержащих сегмент °%г, выберем произвольно путь Su\ 51 = „ - сегмент пути Su. Для расписаний я(р) и 7ti(p,) = Qv.Jji), (v, w) e D2(ti), верно:

С(л) = С1А(я,т)+ I a,MJ), С{%1)>С1(щ,т)+ £ (18)

где S]* - сегмент вида l,r*Smi2n в матрице А(п\), г* = arg(?^(;) =tjh).

Анализ эффективности преобразований 0„Дл(/?)) основан на сравнении правых частей выражений (18). Преобразования классифицируются по следующим признакам: 1) 7pW = t\h или 7p(v) = tjk\ 2) C\h (я, m) = Clh (щ,т); 3) S1' = Sl и M(S1') = M(S'). Каждой группе преобразований соответствуют свои значения индексов v и w. В зависимости от значений индексов v и w анализ преобразований проводится на матрицах А2(п) или А2(ол(с)), или их подматрицах А(п), А(Ок(с)), где с определяется выражением (17).

Для получения оценки эффективности преобразования (вида (2)) вместо матрицы А2(п(р)) используется ее модификация - матрица

Мп(р))~

_ Л(п(р))

где Д)(я) = [0,..., О, а0,p(r) ~ Clh (я, т), 0,..., 0] - 2и-мерный вектор-строка. Правомочность такой замены доказывается.

Для пути Su в матрице А2(п(р)) по аналогии с 5">w(7t) (2) вводится функция 5;;;£(я).

Показывается, что эффективность преобразования Q.vy,in{p)) при

А2(п(р)) = \а,],=(U.....т =

j= 1,2.....и

различных значениях индексов V и оценивается одной из величин 8",».(")> 5"^(оя(с)) или 52;Ц, (о „ (с)) . Оценки строятся от-

носительно критического пути в соответствующей матрице А(тс), Аг(%), А(ал(с)) или Л2(стя(с)). Поскольку области действия оценок не пересекаются, на их основе можно построить функцию, оценивающую эффективность преобразования при любых (у, е Б2(я). В качестве таковой вводится 5"(*)'"(о)(я) (верхние индексы и(тг), и (а) указывают на принадлежность критического пути соответствующей матрице).

С использованием функции бу^'^Ч71) доказывается достаточное условие 1-оптимальности расписания. Доказывается возможность оценивания эффективности композиции по оценкам эффективности 8"(*)'"(о)(я) преобразований, ее составляющих. Выводятся необходимые условия эффективности композиции длины 5. Необходимые условия формулируются в конструктивной форме (как обобщение теоремы 2); они указывают способ построения эффективной композиции. Даются принципы построения ¿-оптимальных алгоритмов.

Четвертая часть «Управление производственными процессами» включает главу 8. В ней рассматриваются модели реальных процессов и систем и даются рекомендации к решению конкретных задач.

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

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

Далее рассматривается более сложная с точки зрения оптимизационных исследований система - трубопрокатный цех (предприятие с многостадийным крупносерийным производством). Решается задача оптимального планирования производственного процесса. Цель планирования состоит в минимизации длительности производственного цикла и минимизации запаздывания работ относительно заданных сроков (критерии оптимизации Сщ^ и Т^ соответственно).

Дается описание технологического процесса проката трубы, кото-

рый включает более десяти стадий (этапов) обработки. В результате анализа производственного процесса по изготовлению п труб (работ, заказов) устанавливается, что для его представления можно использовать модель системы последовательной обработки, состоящей из пяти машин (стадий обработки), - матрицу А(ж) = [а,у]5х„ времен выполнения работ, где л - порядок выполнения работ (см. части I - II).

Доказано, что матрица Л(л) обладает специальным свойством: при любой перестановке столбцов она имеет единственный критический путь, причем этот путь всегда проходит по одной и той же строке (которая соответствует «основной» машине). Это свойство модели позволяет решать задачу оптимального планирования как задачу оптимального упорядочения работ относительно одной «основной» машины.

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

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

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

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

\ Р0С НАЦИОНАЛЬНАЯ 1 библиотека I

| С. Петербург I

* 0Э ЮЛ ыГг I

ОСНОВНЫЕ РЕЗУЛЬТАТЫ И ВЫВОДЫ

1. Дана новая формализация задачи Беллмана-Джонсона. Построена математическая модель системы последовательной обработки с повторным обслуживанием.

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

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

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

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

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

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

* -,

отношениями предшествования работ, с разными маршрутами.

8. Разработаны эффективные алгоритмы синтеза приближенно оптимальных расписаний («-оптимальные алгоритмы).

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

- 10. Разработано устройство для моделирования дискретной сис-

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

11. Результаты диссертационной работы имеют практическое значение. Это подтверждается их внедрением на Волжском подшипниковом заводе ОАО «ВПЗ-15» (г. Волжский Волгоградской обл., 2002 г.) и в ОАО «Волжский трубный завод» (г. Волжский Волгоградской обл., 2003 г.).

ОСНОВНЫЕ ПУБЛИКАЦИИ ПО ТЕМЕ ДИССЕРТАЦИИ

[

' 1. Мирецкий И. Ю., Щербаков М. А. Матричные модели и мето-

ды в теории расписаний: Монография. Пенза: Изд -во Пенз. гос. унта, 2003. 260 с.

2. Мирецкий И. Ю. Оптимизация работы систем последовательного типа // Известия РАН. Теория и системы управления. 2001. № 6. С.70-76.

3. Мирецкий И. Ю. Синтез оптимальных расписаний для систем

1 последовательного типа // Известия РАН. Теория и системы управ-

' ления. 2002. № 1. С. 77-85.

4. Мирецкий И. Ю. Оптимизационная модель конвейерной системы // Вестник Тамбовского гос. техн. ун-та. 2000. Т. 6. № 3. С. 459-465.

* 5. Мирецкий И. Ю. Эффективные преобразования в конвейерной

задаче теории расписаний // Вестник Тамбовского гос. техн. ун-та. 2001. Т. 7. № 1.С. 87-93.

6. Мирецкий И. Ю. Конвейерная задача: конструктивный подход

к построению оптимальных расписаний // Вестник Тамбовского гос. техн. ун-та. 2001. Т. 7. № 3. С. 440-448.

7. Мирецкий И. Ю. Конвейерная задача: алгоритмы синтеза оптимальных расписаний // Вестник Тамбовского гос. техн. ун-та. 2001. Т. 7. № 4. С. 634-640.

8. Мирецкий И. Ю. Задача М станков // Вестник Волгоградского гос. ун-та. Серия 1. Математика. Физика. 2000. Вып. 5. С. 64-74.

9. Левин В. И., Мирецкий И. Ю. Оптимальное планирование работ в конвейерных системах // Автоматика и телемеханика. 1996. № 6. С. 3-30.

10.. Levin V. I., Miretskii I. Yu. Optimal scheduling of jobs in conveyor systems // Automat. Remote Control. 1996. V. 57. № 6. Part 1. P. 773-793. (Translated from Russian)

11. Miretskii I. Yu. Optimization of Operation of Sequential Systems // J. Computer and System Sciences Intern. 2001. Vol. 40. № 6. P. 909915. (Translated from Russian).

12. Miretskii I. Yu. Synthesis of Optimal Schedules for Sequential Systems // J. Computer and System Sciences Intern. 2002. Vol. 41. № 1. P. 73-81. (Translated from Russian).

13. Мирецкий И. Ю. Оценивание возможностей повышения производительности конвейерной вычислительной системы // Вопросы радиоэлектроники. Сер. ЭВТ. 1990. Вып. 9. С. 34-39.

14. Мирецкий И. Ю. Оптимальное планирование работ при допустимости обгонов // Оптимальные методы вычислений и их применение к обработке информации: Межвуз. сб. науч. тр. Пенза: Пенз. политехи, ин-т, 1990. С. 114-120.

15. Мирецкий И. Ю. Об одном подходе к проблеме составления расписаний для конвейерных вычислительных систем // Вопросы радиоэлектроники. Сер. ЭВТ. 1989. Вып. 10. С. 21-26.

16. Левин В. И., Мирецкий И. Ю. О составлении расписаний для конвейерных систем при допустимости обгонов // Управление в сложных системах: Межвуз. сб. науч. тр. Иваново: Иванов, ун-т, 1989. С. 9-12.

17. Мирецкий И. Ю. О составлении расписаний для вычисли-

тельных систем конвейерного типа // Вопросы радиоэлектроники. Сер. ЭВТ. 1988. Вып. 10. С. 65-69.

18. Левин В. И., Мирецкий И. Ю. Об одном подходе к проблеме упорядочения работ в системе конвейерного типа // Ред. журн. «Электронное моделирование». Киев. 1988. Деп. в ВИНИТИ 23.05.88, № 3947-В88. С. 1-14.

19. Левин В. И., Мирецкий И. Ю. Об одном подходе к построению расписаний для конвейерных систем // Методы построения алгоритмических моделей сложных систем: Междуведомственный тематический науч. сб. Таганрог, 1988. Вып. 7. С. 127-130.

20. Левин В. И., Мирецкий И. Ю. Моделирование и оптимизация работы производственной системы // Механизация и автоматизация производства. 1987. № 10. С. 35-36.

21. Левин В. И., Мирецкий И. Ю. К планированию работы конвейерных систем с последовательно-параллельной структурой // Вопросы радиоэлектроники. Сер. ЭВТ. 1987. Вып. 6. С. 10-15.

22. Мирецкий И. Ю. S-оптимальные решения задачи FLOW SHOP // Дискретный анализ и исследование операций (DAOR 2002): Российская конференция: Материалы конф. Новосибирск: Изд-во Ин-та математики. 2002. С. 220.

23. Мирецкий И. Ю. Построение s-оптимальных расписаний // Математические методы и информационные технологии в экономике, социологии и образовании: Сб. материалов Международ, науч.-техн. конф. Ч. 1-2. Пенза: Приволжский Дом знаний. 2001. Ч. 1. С. 148-151.

24. Мирецкий И. Ю. Диапазоны устойчивости оптимального расписания // Математические методы в технике и технологиях -ММТТ-2000: Сб. тр. Междунар. науч. конф. В 7-и т. Санкт-Петербург: СПб. гос. технолог, ин-т. 2000. Т.2. С. 48-49.

25. Мирецкий И. Ю. Алгоритм упорядочения кластеров // Математические методы в технике и технологиях - ММТТ - 2000: Сб. тр. Междунар. науч. конф. В 7-и т. Санкт-Петербург: СПб. гос. технолог, ин-т. 2000. Т.2. С. 67.

26. Мирецкий И. Ю. Конвейерная задача с директивными сроками // Четвертый сибирский конгресс по прикладной и индустриальной математике (ИНПРИМ - 2000), посвященный памяти М. А. Лав-

рентьева (1900-1980).: Тез. докл. Новосибирск: Изд-во Ин-та математики. 2000. Ч. III. С. 157-158.

27. Мирецкий И. Ю. Метод критических путей в задачах последовательной обработки // Математические методы и информационные технологии в экономике: Сб. материалов VI Междунар. науч.-техн. конф. В 2-х ч. Пенза: Приволжский Дом знаний. 2000. Ч. 1. С. 78-80.

28. Мирецкий И. Ю. Матричные модели и методы в теории расписаний // Математические методы в технике и технологиях -ММТТ- 12: Сб. тр. Междунар. науч. конф. В 5-и т. Великий Новгород: Новгородский гос. ун-т. 1999. Т.1. С. 137-138.

29. Мирецкий И. Ю. Общая задача теории расписаний: проблема построения оптимального расписания // Математические методы и компьютеры в экономике: Материалы II Междунар. науч.-техн. конф. Пенза: Приволжский Дом знаний. 1999. С. 21-22.

30. Мирецкий И. Ю. Упорядочение кластеров в системах последовательной обработки // Математические методы и компьютеры в экономике: Материалы II Междунар. науч.-практ. конф. В 2-х ч. Пенза: Приволжский Дом знаний. 1997. Ч. 1. С. 34-35.

31. Мирецкий И. Ю. Метод преобразований при решении конвейерной задачи // Математические методы и компьютеры в экономике: Материалы Междунар. науч.-практ. конф. Пенза: Приволжский Дом знаний. 1996. С. 51-53.

32. Мирецкий И. Ю. Конвейерная задача. Об ограничениях на область поиска оптимального расписания // Проблемы теоретической кибернетики: Тез. докл. VIII Всесоюз. конф. Горький: Горьк. гос. ун-т, 1988. Ч. 2. С. 44.

33. А. с. 1522159 СССР. Мки5 G 05 В 23/02. Устройство для имитации технической системы конвейерного типа / В. И. Левин, И. Ю. Мирецкий // Открытия. Изобретения. 1989. № 42. С. 197-198.

34. А. с. 1741102 СССР. Мки5 G 05 В 23/02. Устройство для имитации технической системы конвейерного типа / И. Ю. Мирецкий // Открытия. Изобретения. 1992. № 22. С. 197-198.

Мирецкий Игорь Юрьевич

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

Специальность 05.13.01 — Системный анализ, управление и обработка информации

Редактор Т. В. Веденеева Технический редактор Н. А. Въялкова

Корректор Н. В. Степочкина Компьютерная верстка М. Б. Жучковой

ИД № 06494 от 26.12.01 Сдано в производство 23.10.03. Формат 60х84*/16. Бумага писчая. Печать офсетная. Усл. печ. л. 2,32.

_Заказ № 692. Тираж 100._

Издательство Пензенского государственного университета. 440026, Пенза, Красная, 40 Отпечатано в типографии ПГУ

2о ©м »2083*

Введение.

Часть I. Минимизация длительности производственного цикла в системах последовательной обработки

Вводные замечания.

Глава 1. Преобразование расписаний в задаче оптимизации работы сборочной линии.

1.1. Постановка задачи

1.2. Математическая модель.

1.3. Оператор преобразования Q*,/.

1.4. Субоптимальные расписания. Концепция ^-оптимальности

1.5. Образ пути при преобразовании расписания.

1.6. Оценка эффективности преобразований.

1.7. Выявление неэффективных преобразований

1.8. Условия 1-оптимальности расписания.

1.9. Условия доминирования

1.9.1 ^-разбиение множества.

1.9.2. Исследование транспозиций

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

2.1. Аналитический аппарат для синтеза 2-оптимальных расписаний.

2.1.1. Исследование композиций длины

2.1.2. Преобразование-склейка.

2.2. Алгоритмы синтеза 1-и 2-оптимальных расписаний

2.2.1. Стратегия поиска 1-оптимальных расписаний.

2.2.2. 1-оптимальные алгоритмы.

2.2.3. 2-оптимальные алгоритмы.

2.2.4. Сложность и сходимость алгоритмов

2.3. Исследование проблемы ^-оптимальности

2.3.1. Оценки эффективности преобразований, входящих в композиции.

2.3.2. Представление композиций

2.3.3. Условия эффективности композиций.

2.4. Построение ^-оптимальных расписаний.

2.4.1. ^-оптимальный алгоритм.

2.4.2. Модифицированный ^-оптимальный алгоритм.

2.4.3. Анализ алгоритмов.

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

3.1. Вводные замечания и постановка задачи.

3.2. Математическая модель

3.3. Оператор преобразования 0.и,к,и.ИЗ

3.4. Подход к решению задачи

3.5. Условия элиминации неэффективных преобразований

3.6. Оценки эффективности преобразований

3.7. 1-оптимальность и ^-оптимальность в классе G.

3.8. Определение параметров преобразований.

3.9. Синтез приближенно оптимальных расписаний класса G

3.10. Пример работы 1 -оптимального алгоритма

3.11. Обобщения конвейерной задачи.

3.11.1. Неодновременное поступление работ.

3.11.2. Оптимизация при заданных отношениях предшествования работ.

3.11.3. Задача с разными маршрутами.

Актуальность темы. Вопросам повышения эффективности функционирования систем неизменно уделяется значительное внимание. Многие задачи управления и организации производства описываются моделями теории расписаний. Теория расписаний изучает модели и методы составления расписаний, то есть распределения во времени ограниченных ресурсов (станков, машин, звеньев, обслуживающих приборов), предназначенных для выполнения различных видов работ (называемых деталями, операциями, заданиями, требованиями). Модели и методы теории расписаний активно используют для решения задач оптимизации работы дискретных систем, начиная с середины 50-х годов XX века (после опубликования результатов исследований С. Джонсона и Р. Беллмана по планированию работы сборочных линий). Исследования в теории расписаний имеют как теоретическую, так и практическую значимость. Они проводятся с целью уменьшения длительности производственного цикла, уменьшения запаздывания работ относительно установленных сроков и т. п., то есть в конечном итоге направлены на совершенствование механизмов планирования и управления.

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

Задачи теории расписаний, несмотря на простоту постановки, в большинстве своем оказываются трудно решаемыми. С практической точки зрения это можно трактовать как невозможность получения точного решения задачи с произвольными исходными данными за «разумное» время вне зависимости от того, какие вычислительные средства будут использованы (полный перебор неприемлем при решении задач большой размерности, которые, собственно, и представляют интерес). Такая ситуа-1 ция характерна для большинства комбинаторных оптимизационных задач.

Комбинаторная задача поддается эффективному алгоритмическому решению, если существует метод ее решения, число шагов которого полиномиально зависит от размерности задачи (соответствующий алгоритм также называется эффективным). Проблема эффективной разрешимости задач является одной из основных в современной математике (гипотеза Р Ф NP). Различают точный и приближенный подходы к решению задач [10, 14, 15, 77-78, 84-85, 87, 114, 138, 157, 167, 168]. Выбор подхода определяется вычислительной сложностью задачи. Прежде чем приступить к решению задачи, необходимо установить, является ли она полиномиально разрешимой (принадлежит классу Р) или MP-трудной. Точные подходы основываются на методах комбинаторного анализа [15, 17, 77, 85], ветвей и границ [13, 18, 77, 87, 136], отсечений [16, 77], динамического программи-^ рования [3, 15, 77]. Для ММрудных задач используют приближенные подходы. Наиболее распространенными приближенными подходами являются жадность, последовательное улучшение, локальный поиск, случайный поиск; приближаемой характеристикой обычно выбирается целевая функция, иногда - ограничения задачи [12,16-17,19, 77, 84,123].

Объектом диссертационного исследования являются дискретные многостадийные системы - системы последовательной обработки. В терминах теории расписаний (основного инструмента исследования) задача к минимизации длительности производственного цикла в дискретных системах последовательной обработки называется задачей Беллмана-Джонсона. Другие не менее часто встречающиеся названия есть конвейерная задача, задача выполнения п работ последовательно т машинами, задача т станков. В силу своей значимости для практики задача Беллмана-Джонсона и ее обобщения - класс задач, связанных с решением проблемы составления оптимального плана работы систем последовательного типа, - вызывают неослабевающий интерес с момента опубликования первых статей по этой проблематике (С. Джонсон [134], Р. Беллман [101]) по настоящее время. В задачах этого класса, которые являются предметом диссертационного исследования, рассматриваются различные по способу организации функционирования системы последовательной обработки (конвейер, система с разными маршрутами для разных работ, система с неодновременным поступлением работ, система с повторным обслуживанием и др.) и используются различные критерии оценки качества функционирования систем (длительность производственного цикла, запаздывание работ относительно директивных сроков и др.) [15, 22-24, 36, 80, 85-88, 96, 100, 113, 118, 128, 141, 162, 165, 168, 173-174, 183-185].

В первые годы после публикации С. Джонсона [134] исследования проводились в области точных методов, а также касались использования метода случайного поиска. Аналитические результаты получены в основном средствами комбинаторного анализа. Комбинаторные исследования проводились при рассмотрении вырожденных и частных случаев, для выявления условий элиминации и доминирования (С. Джонсон [134], И. На-бешима [149, 151], В. Бурдюк [5], Д. Гупта [125], В. Шварц [176-182], [15, 21-22, 35, 85, 97, 115, 125, 127, 132, 140, 146, 149, 151, 155, 169-172]). Выявление условий элиминации и доминирования дает определенную базу для построения эффективных алгоритмов.

Как точные методы решения задачи Беллмана-Джонсона и ее обобщений предлагались методы целочисленного программирования (А. Манне [144], [15, 38, 91-92, 103, 117, 119, 175]), динамического программирования (Р. Беллман [3, 101], М. Хелд, Р. Карп [89], Р. Якимов [94], [8, 11, 90, 150]), ветвей и границ (Е. Игнолл, JI. Шрейдж [132], 3. Ломницкий [143], Г. Кэмпбелл, Р. Дудек, М. Смит (использование декомпозиции) [109], [6-7, 9, 17, 20, 22, 87, 93,98-99,106,110,125,136-137,139,145,150, 161,171, 186].

Высокая размерность получающихся задач целочисленного программирования, большое время счета (число итераций имеет порядок возможного числа перестановок), а также неустойчивость вычислений по существующим программам делают практически непригодным использование данного метода [15, 92]. Метод динамического программирования, являющийся универсальным с теоретической точки зрения, обладает в наихудших случаях экспоненциальными оценками времени и памяти [1-2, 89] и, следовательно, с вычислительной точки зрения применим для решения задач теории расписаний сравнительно небольшой размерности.

В алгоритмах ветвей и границ используются результаты комбинаторных исследований (правила элиминации, условия доминирования), серьезное внимание уделяется способам нахождения нижней границы целевой функции [15, 85, 96, 140, 145, 180]. Алгоритмы обычно более эффективны, нежели полный перебор, но их требования в вычислительных ресурсах растут как экспоненты или полиномы высокой степени от размера задачи п. Поэтому возникающие на практике задачи точно фактически неразрешимы. Однако схемы ветвей и границ достаточно гибкие и предусматривают поиск не только точных, но и приближенных решений задачи (например, схемы без возвратов).

Метод случайного поиска (С. Брукс [105], Д. Хеллер [130], С. Ньюджент [155], [12, 15, 17, 37, 79, 81]) является приближенным. В работах [15, 17] отмечается необходимость осторожности при трактовке и обобщении результатов статистического моделирования. Достоинством метода случайного поиска является легкость получения решения (которое затем можно использовать в качестве начального, например, в алгоритмах локального поиска). Метод случайного поиска не отражает духа и стоит несколько в стороне от современных приближенных методов.

После того, как была установлена JVP-трудность задачи Беллмана-Джонсона (М. Гэри, Р. Джонсон, Сетхи Рави [118]), исследования в основном проводятся в области приближенных подходов.

Под приближенным понимается такой алгоритм Аи решения массовой оптимизационной задачи 77, который для любой индивидуальной задачи 7 е 77 находит некоторое допустимое решение ХА(7), принимаемое за приближенное [10, 84]. Таким образом, понятие «приближенно оптимальное решение» допускает широкое толкование.

Наиболее интенсивные исследования ведутся в области алгоритмов с гарантированными оценками точности и алгоритмов локального поиска. Вопрос оценки качества решения, получаемого приближенным алгоритмом, является очень тонким и зависит от подхода к решению. О качестве решения индивидуальной задачи 7 е 77 с помощью приближенного алгоритма А/7 (то есть о погрешности алгоритма) чаще всего судят по отклонению (относительному или абсолютному) значения J[XA(I)) целевой функции в «точке» ХА(1), найденной алгоритмом, от значения f{X*(I)) в «точке» оптимума Х*(1) задачи 7. При определения погрешности метода решения Y массовой задачи рассматривают отклонения в среднем (статистическая оценка поведения алгоритма) и в худшем случае [84].

Алгоритм А называется р-приближающим, если для любого 7 е 77 гарантируется выполнение неравенства J{XA(I)) l f{X*(T)) < р. Разработка р-при-ближающих алгоритмов - одно из наиболее перспективных направлений в современной дискретной оптимизации и, в частности, в теории расписаний [4, 76, 82-83, 112, 129, 166]. Предметом изучения является возможность построения р-приближающих алгоритмов; выполняется классификация за-► дач по сложности их аппроксимации. Известно, однако, что поиск хороших нижних оценок оптимума в задачах дискретной оптимизации - проблема достаточно сложная. И это является техническим препятствием к построению алгоритмов с хорошими оценками точности вида ДХА(7))/ДУ(7))<р[83].

Другим не менее бурно развивающимся и перспективным направлением исследований является локальный поиск, или поиск в локальной окрестности [95, 107-108, 120, 188]. На базе схем последовательного локального улучшения развились новые мощные средства локального поиска (метаэвристики): алгоритмы имитации отжига [111, 133, 135, 158-160], поиск с запретами (Ф. Гловер [121-124], [114, 126, 131, 152, 154, 163, 186, 189]) и генетические алгоритмы [104, 164].

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

Алгоритмы локального поиска широко применяются для решения iVP-трудных задач дискретной оптимизации. Для многих А^Р-трудных задач локальный поиск позволяет находить приближенные решения, близкие по целевой функции к глобальному оптимуму. Для некоторых метаэвристик установлена асимптотическая сходимость к оптимуму. Трудоемкость алгоритмов часто оказывается полиномиальной, прйчем степень полинома достаточно мала. Интерес к локальному поиску носит не только практический (решено огромное количество тестовых и индивидуальных примеров), но и теоретический характер: исследуются сложно-стные аспекты и асимптотическое поведение алгоритмов [19, 187, 190].

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

Для каждой задачи вопрос определения окрестности решается по-своему, индивидуально. При выборе окрестности практически всегда приходится идти на определенный компромисс: окрестность малой мощности позволяет сократить трудоемкость одного шага, в то время как более широкая окрестность приводит к лучшему локальному оптимуму. При решении задачи Беллмана-Джонсона окрестность строится обычно с использованием техники одиночной вставки, транспозиций и блочного перемещения работ [102, 154, 189]; окрестность расписания определяется возможными вставками, транспозициями и блочными перемещениями. Общего для разных задач правила выбора окрестности нет (тем не менее, не исключено, что такое правило можно сформулировать для классов задач, например, для задач, которые можно поставить на множестве перестановок).

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

Третья проблема связана с отсутствием «стратегической линии» движения к оптимуму [153]. Однако есть основания полагать, что изучение специальных свойств задач позволит перейти к более эффективным, чем переборные, схемам анализа окрестностей и указать набор «перспективных» направлений движения по множеству допустимых решений.

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

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

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

Основные задачи диссертационного исследования.

1. Построение математических моделей дискретных многостадийных систем.

2. Разработка концепции 5-оптимальности и приближенного подхода к решению задач теории расписаний.

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

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

5. Разработка эффективных алгоритмов для планирования работы систем последовательного типа.

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

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

Научная новизна работы.

1. Дана новая формализация задачи Беллмана-Джонсона. Построена математическая модель системы последовательной обработки с повторным обслуживанием.

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

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

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

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

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

6. Получены оценки эффективности преобразований, составляющих композицию, и условия согласованности оценок эффективности композиции и преобразований, входящих в ее состав. Доказаны необходимые условия эффективности композиции преобразований и предложены способы построения эффективных композиций. Разработан метод построения s-оптимальных расписаний (s > 2), основанный на проведении эффективных композиций преобразований.

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

8. Разработаны эффективные алгоритмы поиска ^-оптимальных расписаний (д > 1), определена их сложность и доказана сходимость.

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

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

Разработанные алгоритмы применимы для оптимального планирования работы различного рода систем последовательного типа, например, при планировании производственных процессов в сборочных, инструментальных цехах предприятий машиностроения и т. п. Использование алгоритмического обеспечения в АСУТП позволяет улучшить ряд показателей эффективности работы предприятий, в том числе увеличить объем производства на планируемый период, уменьшить длительность простоев оборудования по организационным причинам, снизить энергозатраты в расчете на единицу выпускаемой продукции, уменьшить штрафы, связанные с несвоевременным выполнением заказов.

Реализация и внедрение результатов. Результаты диссертационной работы в виде алгоритмов и пакетов программ внедрены в системах технологической подготовки производства Волжского подшипникового завода ОАО «ВПЗ-15», г. Волжский Волгоградской обл., и ОАО «Волжский трубный завод», г. Волжский Волгоградской обл.

Материалы диссертации используются в учебном процессе кафедры прикладной математики и информатики Волжского гуманитарного института (филиала) Волгоградского государственного университета при проведении курса «Теория расписаний».

Апробация работы. Результаты диссертационной работы докладывались и обсуждались на зональных конференциях «Математические и программные методы проектирования управляющих систем» (Пенза, 1986), «Экономичность технологических процессов и оборудования в кузнечно-пггамповочном производстве» (Пенза, 1987), «Математические и программные методы проектирования управляющих и информационных систем» (Пенза, 1988, 1990), научно-техническом семинаре «Проблемы создания интеллектуальных САПР» (Геленджик, 1988), VIII Всесоюзной конференции «Проблемы теоретической кибернетики» (Горький, 1988), I Всероссийской научной конференции «Непрерывная логика и ее применение в технике, экономике и социологии» (Пенза, 1994), Международной научно-технической конференции «Непрерывно-логические методы и модели в науке, технике и экономике» (Пенза, 1995), Международных конференциях «Математические методы и компьютеры в экономике» (Пенза, 1996, 1997, 1999), Всероссийской научно-технической конференции «Непрерывная и смежные логики в информатике, экономике и социологии» (Пенза, 1997), Международных научно-технических конференциях «Логико-математические методы в технике, экономике и социологии» (Пенза, 1998, 1999), Международной научной конференции ММТТ-12 - «Математические методы в технике и технологиях» (Великий Новгород, 1999), Международных научно-технических конференциях «Математические методы и информационные технологии в экономике» (Пенза, 2000, 2001), Международной научной конференции ММТТ-2000 - «Математические методы в технике и технологиях» (Санкт-Петербург, 2000), Четвертом си-► бирском конгрессе по прикладной и индустриальной математике

ИНПРИМ-2000 (Новосибирск, 2000), Международной научно-технической конференции «Математические методы и информационные технологии в экономике, социологии и образовании» (Пенза, 2001), Российской конференции DAOR 2002 - «Дискретный анализ и исследование операций» (Новосибирск, 2002), семинарах по прикладной дискретной математике и теории информации (Пенза, завод-ВТУЗ, 1987-1992), ежегодных конференциях профессорско-преподавательского состава Волжского гуманитарного института (филиала) Волгоградского государственного университета (1996-2003).

Публикадии. По теме диссертации опубликована 51 научная работа, включая монографию [75], 22 статьи [26, 28-33, 35, 41-43, 45, 65-67, 70-73, 142, 147-148], 26 тезисов докладов [25, 27, 39-^0, 44, 47-64, 68-69, 74] и 2 изобретения [34,46].

Структура и краткое содержание работы. Диссертация состоит из введения, четырех частей, заключения, библиографии, включающей 190 наименований, и приложений. Объем работы составляет 337 страниц основного машинописного текста и 26 страниц приложений; в диссертации 22 рисунка и 15 таблиц.

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

1. Дана новая формализация задачи Беллмана-Джонсона. Построена математическая модель системы последовательной обработки с повторным обслуживанием.

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

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

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

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

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

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

8. Разработаны эффективные алгоритмы синтеза приближенно оптимальных расписаний (^-оптимальные алгоритмы).

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

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

11. Результаты диссертационной работы имеют практическое значение. Это подтверждается их внедрением на Волжском подшипниковом заводе ОАО «ВПЗ-15» (г. Волжский Волгоградской обл., 2002 г.) и в ОАО «Волжский трубный завод» (г. Волжский Волгоградской обл., 2003 г.).

Материалы диссертации используются в учебном процессе кафедры прикладной математики и информатики Волжского гуманитарного института (филиала) Волгоградского государственного университета при проведении курса «Теория расписаний».

ЗАКЛЮЧЕНИЕ

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

2. Беленький А. С., Левнер Е. В. Применение моделей и методов теории расписаний в задачах оптимального планирования на грузовом транспорте // Автоматика и Телемеханика. 1989. № 1. С. 3-77.

3. Беллман Р., Дрейфус С. Прикладные задачи динамического программирования. М.: Наука, 1965.

4. Белов И. С., Столин Я. Н. Алгоритм в одномаршрутной задаче календарного планирования. В кн.: Математическая экономика и функциональный анализ. М.: Наука, 1974. С. 248-257.

5. Бурдюк В. Я. О задаче т станков (т > 2) // Кибернетика. 1969. № 3. С. 74-76.

6. Вагнер Г. Основы исследования операций. Т. 1, 2. М.: Мир, 1973.

7. Вахания Н. Н. Построение сокращенного дерева вариантов для общей задачи теории расписаний // Дискретная математика. 1990. Т. 2. № 3. С. 10-20.

8. Власюк Б. А. Оптимальное расписание обработки деталей на трех последовательных машинах // Изв. АН СССР. Техн. кибернетика. 1967. № 4. С. 79-84.

9. Гудман С., Хидетниеми С. Введение в разработку и анализ алгоритмов. М.: Мир, 1981.

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

11. Драхлин Е. X., Якимов Р. М. Анализ свойств оптимального варианта последовательности обработки изделий // Сб. науч. трудов. Пермь:

12. Перм. политехи, ин-т, 1966. № 21. С. 59-61.

13. Ермаков С. М. Метод Монте-Карло и смежные вопросы. М.: Наука, 1975.

14. Исследование операций. Т. 2./ Под ред. Моудера Дж., Элмаграби С. М.: Мир, 1981.

15. Ковалев М. Я., Струсевич В. А., Танаев В. С. и др. Приближенные алгоритмы в теории расписаний // Методы решения экстремальных задач. Минск, 1989. С. 5-34.

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

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

18. Кофман А. Введение в прикладную комбинаторику. М.: Наука, 1975.

19. Кофман А., Анри-Лабордер А. Методы и модели исследования операций. М.: Мир, 1977.

20. Кочетов Ю. А. Вероятностные методы локального поиска для задач дискретной оптимизации // Дискретная математика и ее приложения. Сборник лекций молодежных и научных школ по дискретной математике и ее приложениям. М.: МГУ, 2001.

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

22. Левин В. И. Оптимизация расписания обработки деталей с помощью смешанных условий оптимальности // Math. Operationsforsch. и. Statist., Ser. Optimization. 1987. V. 18. № 5. S. 697-707.

23. Левин В. И. Структурно-логические методы исследования сложных систем с применением ЭВМ. М.: Наука, 1987.

24. Левин В. И. Задача М станков при поступлении деталей в режиме реального времени // Автоматика и Телемеханика. 1989. № 1. С. 141-154.

25. Левин В. И. Оптимизация расписаний в системах с неопределенными временами обработки. I, II Н Автоматика и Телемеханика. 1995. № 2. С. 99-110. №3. С. 106-116.

26. Левин В. И., Мирецкий И. Ю. Упорядочение работ в конвейерной вычислительной системе // Математические и программные методы проектирования управляющих систем: Тез. докл. Зональн. конф. Пенза: Приволжский ДНТП. 1986. С. 41-43.

27. Левин В. И., Мирецкий И. Ю. Организация процесса обработки заданий в конвейерной вычислительной системе // Вопросы радиоэлектроники. Сер. ЭВТ. 1986. Вып. 8. С. 3-7.

28. Левин В. П., Мирецкий И. Ю. К планированию работы конвейерных технических систем // Экономичность технологических процессов и оборудования в кузнечно-штамповочном производстве: Тез. докл. Зональн. конф. Пенза: Приволжский ДНТП. 1987. С. 43-45.

29. Левин В. И., Мирецкий И. Ю. К планированию работы конвейерных систем с последовательно-параллельной структурой // Вопросы радиоэлектроники. Сер. ЭВТ. 1987. Вып. 6. С. 10-15.

30. Левин В. П., Мирецкий И. Ю. Моделирование и оптимизация работы производственной системы // Механизация и автоматизация производства. 1987. № 10. С. 35-36.

31. Левин В. И., Мирецкий И. Ю. Об одном подходе к построению расписаний для конвейерных систем // Методы построения алгоритмических моделей сложных систем: Междуведомственный тематический науч. сб. Таганрог. 1988. Вып. 7. С. 127-130.

32. Левин В. И., Мирецкий И. Ю. Об одном подходе к проблеме упорядочения работ в системе конвейерного типа // Ред. журн. «Электронное моделирование». Киев. 1988. Деп. в ВИНИТИ 23.05.88, № 3947 В88. 1-14 с.

33. Левин В. И., Мирецкий И. Ю. Об одном подходе к проблеме упорядочения работ в системе конвейерного типа // Электронное моделирование. 1988. № 5. С. 103.

34. Левин В. И., Мирецкий И. Ю. О составлении расписаний для конвейерных систем при допустимости обгонов // Управление в сложных системах: Межвуз. сб. науч. трудов. Иваново: Иванов, ун-т., 1989. С. 9-12.

35. Левин В. И., Мирецкий И. Ю. Устройство для имитации технической системы конвейерного типа / А. с. 1522159 СССР, Мки5 G 05 В 23/02 // Открытия. Изобретения. 1989. № 42. С. 197-198.

36. Левин В. И., Мирецкий И. Ю. Оптимальное планирование работ в конвейерных системах II Автоматика и телемеханика. 1996. №6. С. 3-30.

37. Левнер Е. В., Немировский А. С. Задача сетевого планирования в постановке "точно вовремя" и потоковый алгоритм ее решения // Численные методы оптимизации и анализа. Новосибирск: Сиб. энерг. ин-т, 1992. С. 18-35.

38. Лифшиц А. Л., Мальц Э. А. Статистическое моделирование систем массового обслуживания. М.: Советское радио, 1978.

39. Лурье А. Л. О некоторых задачах календарного планирования // Сб. научн. трудов. М.: Наука, 1962. Вып. 7. С. 201-208.

40. Мирецкий И. Ю. Конвейерная задача. Об ограничениях на область поиска оптимального расписания // Проблемы теоретической кибернетики: Тез. докл. VIII Всесоюзн. конф. Горький: Горьк. госуд. ун-т, 1988. Ч. 2. С. 44.

41. Мирецкий И. Ю. О влиянии порядка прохождении деталей по станкам на общее время обработки II Математические и программные методы проектирования управляющих и информационных систем: Тез. докл. Зональн. конф. Пенза: Приволжский ДНТП. 1988. С. 24-26.

42. Мирецкий И. Ю. О составлении расписаний для вычислительных систем конвейерного типа // Вопросы радиоэлектроники. Сер. ЭВТ. 1988. Вып. 10. С. 65-69.

43. Мирецкий И. Ю. Об одном подходе к проблеме составления расписаний для конвейерных вычислительных систем // Вопросы радиоэлектроники. Сер. ЭВТ. 1989. Вып. 10. С. 21-26.

44. Мирецкий И. Ю. Оптимальное планирование работ при допустимости обгонов // Оптимальные методы вычислений и их применение к обработке информации: Межвуз. сб. науч. трудов. Пенза: Пензенский политехи. ин-т. 1990. С. 114-120.

45. Мирецкий И. Ю. Оценивание возможностей повышения производительности конвейерной вычислительной системы // Вопросы радиоэлектроники. Сер. ЭВТ. 1990. Вып. 9. С. 34-39.

46. Мирецкий И. Ю. Устройство для имитации технической системы конвейерного типа / А. с. 1741102 СССР, Мки5 G 05 В 23/02 // Открытия. Изобретения. 1992. № 22. С. 197-198.

47. Мирецкий И. Ю. Методы непрерывной логики при решении конвейерной задачи // Непрерывная логика и ее применение в технике, экономике и социологии: Тез. докл. I Всероссийской науч. конф. Пенза: Приволжский ДНТП. 1994. С. 38^0.

48. Мирецкий И. Ю. Использование метода траекторий при синтезе расписаний // Непрерывно-логические методы и модели в науке, технике и экономике: Материалы Международ, науч.-техн. конф. Пенза: Приволжский ДНТП. 1995. С. 88-89.

49. Мирецкий И. Ю. Метод преобразований при решении конвейерной задачи // Математические методы и компьютеры в экономике: Материалы Международ, науч.-практ. конф. Пенза: Приволжский Дом знаний. 1996. С. 51-53.

50. Мирецкий И. Ю. Устойчивость оптимального расписания // Математические методы и компьютеры в экономике: Материалы II Международ. науч.-практ. конф. В 2-х ч. Пенза: Приволжский Дом знаний. 1997. Ч. 1.С. 32-33.

51. Мирецкий И. Ю. Упорядочение кластеров в системах последовательной обработки // Математические методы и компьютеры в экономике: Материалы II Международ, науч.-практ. конф. В 2-х ч. Пенза: Приволжский Дом знаний. 1997. Ч. 1. С. 34-35.

52. Мирецкий И. Ю. Эффективность методов решения задач дискретной оптимизации И Непрерывная и смежные логики в информатике, экономике и социологии: Материалы Всероссийской науч.-техн. конф. Пенза: Приволжский Дом знаний. 1997. С. 75-76.

53. Мирецкий И. Ю. Устойчивость оптимального расписания // Логико-математические методы в технике, экономике и социологии: Материалы Международ, науч.-техн. конф. Пенза: Приволжский Дом знаний. 1998. С. 55-56.

54. Мирецкий И. Ю. Матричные модели и методы в теории расписаний // Математические методы в технике и технологиях ММТТ - 12: Сб. трудов Международ, науч. конф. В 5-ти т. Великий Новгород: Новгородский гос. ун-т. 1999. Т.1. С. 137-138.

55. Мирецкий И. Ю. Общая задача теории расписаний: проблема построения оптимального расписания // Математические методы и компьютеры в экономике: Материалы II Международ, науч.-техн. конф. Пенза: Приволжский Дом знаний. 1999. С. 21-22.

56. Мирецкий И. Ю. Построение допустимых расписаний при решении общей задачи теории расписаний // Математические методы и компьютеры в экономике: Материалы II Международ, науч.-техн. конф. Пенза: Приволжский Дом знаний. 1999. С. 22-23.

57. Мирецкий И. Ю. Матричная модель общей задачи теории расписаний // Логико-математические методы в технике, экономике и социологии: Материалы IV Международ, науч.-практ. конф. Пенза: Приволжский Дом знаний. 1999. С. 57.

58. Мирецкий И. Ю. Конвейерная задача с директивными сроками // Логико-математические методы в технике, экономике и социологии: Материалы IV Международ, науч.-практ. конф. Пенза: Приволжский Дом знаний. 1999. С. 58.

59. Мирецкий И. Ю. Условия доминирования в задаче с директивными сроками // Математические методы и информационные технологии в экономике: Материалы V Международ, науч.-техн. конф. В 2-х ч. Пенза: Приволжский Дом знаний. 2000. Ч. 1. С. 10-12.

60. Мирецкий И. Ю. Диапазоны устойчивости оптимального расписания // Математические методы в технике и технологиях ММТТ - 2000: Сб. трудов Международ, науч. конф. В 7-и т. Санкт-Петербург: СПб. гос. технол. ин-т. 2000. Т.2. С. 48-49.

61. Мирецкий И. Ю. Алгоритм упорядочения кластеров // Математические методы в технике и технологиях ММТТ - 2000: Сб. трудов Международ. науч. конф. В 7-и т. Санкт-Петербург: СПб. гос. технол. ин-т. 2000. Т.2. С. 67.

62. Мирецкий И. Ю. Задача М станков // Вестник Волгоградского гос. унта. Серия 1. Математика. Физика. 2000. Выпуск 5. С. 64-74.

63. Мирецкий И. Ю. Оптимизационная модель конвейерной системы // Вестник Тамбовского гос. техн. ун-та. 2000. Т. 6. № 3. С. 459-465.

64. Мирецкий И. Ю. Эффективные преобразования в конвейерной задаче теории расписаний // Вестник Тамбовского гос. техн. ун-та. 2001. Т. 7. № 1. С. 87-93.

65. Мирецкий И. Ю. Построение s-оптимальных расписаний // Математические методы и информационные технологии в экономике, социологии и образовании: Сб. материалов Международ, науч.-техн. конф. Ч. 1-2. Пенза: Приволжский Дом знаний. 2001. Ч. 1. С. 148-151.

66. Мирецкий И. Ю. Оптимизация работы систем последовательного типа // Известия РАН. Теория и системы управления. 2001. № 6. С. 70-76.

67. Мирецкий И. Ю. Конвейерная задача: конструктивный подход к построению оптимальных расписаний // Вестник Тамбовского гос. техн. ун-та. 2001. Т. 7. № 3. С. 440^48.

68. Мирецкий И. Ю. Конвейерная задача: алгоритмы синтеза оптимальных расписаний // Вестник Тамбовского гос. техн. ун-та. 2001. Т. 7. № 4. С. 634-640.

69. Мирецкий И. Ю. Синтез оптимальных расписаний для систем последовательного типа // Известия РАН. Теория и системы управления.2002. № 1.С. 77-85.

70. Мирецкий И. Ю. ^-оптимальные решения задачи FLOW SHOP II Дискретный анализ и исследование операций (DAOR 2002): Российская конференция: Материалы конференции. Новосибирск: Изд-во Ин-та математики. 2002. С. 220.

71. Мирецкий И. Ю., Щербаков М. А. Матричные модели и методы в теории расписаний: Монография. Пенза: Изд.-во Пенз. гос. ун-та,2003. 260 с.

72. Михалевич В. С., Кукса А. И. Методы последовательной оптимизации (в дискретных задачах оптимального распределения ресурсов). М.: Наука, 1983.

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

74. Подчасова Т. П., Португал В. М., Татаров В. А., Шкурба В. В. Эвристические методы календарного планирования. Киев: Техника, 1980.

75. Португал В. М., Писаренко В. М. Экспериментальное исследование алгоритмов случайного поиска для задач календарного планирования // Вопросы разработки территориальных автоматизированных систем управления. Сб. науч. трудов. Кемерово, 1984. С. 8-12.

76. Протасов В. Я., Жердзинский И. Ю. Оптимизация функционирования конвейерной производственной системы // Системное моделирование. 1991. № 18. С. 135-159.

77. Реклейтис Г., Рейвиндран А., Рэгсдел К. Оптимизация в технике. Т. 1, 2. М.: Мир, 1986.

78. Севастьянов С. В. Геометрия в теории расписаний // Модели и методы оптимизации. Труды ин-та математики СО АН СССР. Новосибирск: Наука, 1988. Т. 10. С. 213-260.

79. Севастьянов С. В. Геометрические методы и эффективные алгоритмы в теории расписаний / Дисс. . д. ф.-м. н. Новосибирск: Ин-т математики им. С. JI. Соболева СО РАН, 2000.

80. Спесивцев А. В. Жадные алгоритмы распределения ресурсов. Списки и ограниченный перебор. М.: МП «Малип», 1993.

81. Танаев В. С., Шкурба В. В. Введение в теорию расписаний. М.: Наука, 1975.

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

83. Теория расписаний и вычислительные машины / Под ред. Коффма-на Э. Г. М.: Наука, 1984.

84. Тюттокин В. К. Об оптимизации календарной длительности обработки изделий при одинаковой последовательности запуска их на всех станках // Оптимальное планирование. Сб. науч. трудов. Новосибирск, 1970. Вып. 16. С. 59-70.

85. Хелд М., Карп Р. М. Применение динамического программирования к задачам упорядочения II Кибернетический сб. М.: Мир, 1964. Вып. 9. С. 202-218.

86. Хореев В. И. Итеративные алгоритмы определения расписаний в информационно-вычислительных системах // Автоматика и вычислительная техника. 1987. № 4. С. 8-14.

87. Хохлюк В. И. Задачи целочисленной оптимизации. Новосибирск: Новосибирск. ун-т, 1979.

88. Хохлюк В. И. Параллельные алгоритмы целочисленной оптимизации. М.: Радио и связь, 1987.

89. Якимов Р. М. Об одном функциональном уравнении, описывающем оптимальную последовательность обработки изделий // Межвуз. сб. науч. трудов. Пермь: Перм. политехи, ин-т, 1966. № 21. С. 62-71.

90. Aarts Е. Н. L., Van Laarhoven P. J. M., Lenstra J. К., Ulder N. L. J. A computational study of local search algorithms for job shop scheduling // ORSAJ. Сотр. 1994. V. 6. P. 118-125.

91. Ahmadi Reza H., Bagchi Uttarayan. Improved Lower Bounds for Minimizing the Sum of Completion Times of N Jobs over M Machines in a Flow Shop II Euro. J. Oper. Res. 1990. V. 44. № 3. P. 331-336.

92. Arthanari T. S., Mukhopadhyay A. C. On Some Sequencing Problems. A Note on a Paper by W. Szwarc // Nav. Res. Log. Quart. 1971. V. 18. № 1. P. 135-138.

93. Ashour Said, Quraishi M, N. Investigation of Various Procedures for Production Scheduling Problem Hint. J. Prod. Res. 1969. V. 7. № 13. P. 249-252.

94. Avi-Itzhak B. A Sequence of Service Stations with Arbitrary Input and Regular Service Times //Management Sci. 1965. V. 11. № 5. P. 553-564.

95. Baker K. P. Scheduling Groups of Jobs in the Two-Machine Flow Shop // Math. andComput. ModellA990. V. 13. № 3. P. 29-36.

96. Bellman R. Mathematical Aspects of Scheduling Theory // J. Soc. Indust. andAppl. Math. 1956. V. 4. № 3. P. 168-205.

97. Ben-Daya M., Al-Fawzan M. A tabu search approach for the flow shop scheduling problem // Euro. J. Oper. Res. 1998. V. 109. P. 88-95.

98. Bowman E. H. The Schedule-Sequencing Problem // Oper. Res. 1959. V. 7. № 5. P. 621-624.

99. Bremermann H. J., Roghson J., Salaff S. Global properties of evolutionprocesses // Natural automata and useful simulations. London: Mac-Millan.1966. P. 3-42.

100. Brooks S. H. A Discussion of Random Methods for Seeking Maxima // Oper. Res. 1958. V. 6. № 2. P. 244-253.

101. Brown A. P. G., Lomhicki Z. A. Some Applications of the "Branch-and-Bound" Algorithm to the Machine Scheduling Problem // Oper. Res. Quart.1967. V. 17. №2. P. 173-186.

102. Brucker P., Hurink J., Werner F. Improving local search heuristics for some scheduling problems // Discrete Appl. Math. 1996. V. 65. P. 87-107.

103. Brucker P, Hurink J, Werner F. Improving local search heuristics for some scheduling problems. Part II // Discrete Appl. Math. 1997. V. 72. P. 47-69.

104. Campbell Herbert G., Dudek R. A., Smith M. L. A Heuristic Algorithm for the n Job ^/-machine Sequencing Problem //Management Sci. 1970. V. 16. № 10. P. B-630-B-637.

105. Carlier J., Rebai I. Two branch and bound algorithms for the permutation flow shop problem // Euro. J. Oper. Res. 1996. V. 90. P. 238-251.

106. Cerny V. Thermodynamical approach to the traveling salesman problem: an efficient simulation algorithm // J. Opt. Theory Appl. 1985. V. 45. P. 41-51.

107. Chen В., Potts C. N., Woeginger G. J. A review of machine scheduling: complexity, algorithms and approximability // Handbook of Combinatorial Optimization. D.-Z. Du and P. M. Pardalos (Eds.). Kluwer Academic Publishers, 1998. P. 21-169.

108. Chu C. A branch and bound algorithm to minimize total tardiness with different release dates П Naval Research Logistics. 1992. V. 39, P. 265-283.

109. Dannenbring D. G. An evaluation of flow-shop sequencing heuristics // Management Sci. 1977. V. 23. P. 1174-1182.

110. Dudek R. A., Teuton O. F. J. Development of M-Stage decision Rule for Scheduling n Jobs through M Machines // Oper. Res. 1964. V. 12. № 3. P. 471-497.

111. Elmaghraby S. E. The One Machine Sequencing Problem with Delay Costs // J. Ind. Eng. 1968. V. 19. № 2. P. 105-108.

112. Frieze A. M., Yadegar J. A New Integer Programming Formulation for the Permutation Flowshop Problem // Euro. J. Oper. Res. 1989. V. 40. № 1. P. 90-98.

113. Garey M. R., Johnson R. S., Sethi Ravi. The Complexity of Flow-Shop and Job-Shop Problem IIMath. Oper. Res. 1976. № 2. P. 117-129.

114. Giglio R. J., Wagner H. M. Approximate Solutions to the Three-Machine Scheduling Problems // Oper. Res. 1964. V. 12. № 2. P. 305-324.

115. Glass C. A., Potts C. N. A comparison of local search methods for flow shop scheduling // Annals of Oper. Res. 1996. V. 63. P. 489-509.

116. Glover F. Tabu search: part I // ORSA J. Сотр. 1989. V. 1. P. 190-206.

117. Glover F. Tabu search: part II // ORSA J. Сотр. 1990. V. 2. P. 4-32.

118. Glover F., Laguna. M. Tabu search. Boston: Kluwer Acad. Publ. 1997.

119. Glover F. (Ed.) Tabu search methods for optimization // Feature Issue of Euro. J. Oper. Res. 1998. V. 106, №. 2-3.

120. Gupta J. N. D. An Improved Combinatorial Algorithm for the Flowshop Scheduling Problem // Oper. Res. 1971. V. 19. № 7. P. 1753-1758.

121. Gupta J. N. D. A functional heuristic algorithm for the flow-shop scheduling problem // Oper. Res. Quart. 1971. V. 22. P. 39^7.

122. Gupta J. N. D. Optimal Schedules for Special Structure Flowshops // Nav. Res. Log. Quart. 1975. V. 22. № 3. P. 255-269.

123. Gupta J. N. D. Flowshop Scheduling with Sequense Dependent Setup Times // J. Oper. Res. Soc. Jap. 1986. V. 29. № 3. P. 206-219.

124. Hall L. A. Approximability of flow shop scheduling // Mathematical Programming. 1988. V. 82. P. 175-190.

125. Heller J. Some Numerical Experiments for anMxJ Flow Shop and Its Decision-Theoretical Aspects // Oper. Res. 1960. V. 8. № 2. P. 178-184.

126. Hundal T. S., Rajgopal J. An extension of Palmer's heuristic for the flow-shop scheduling problem // Int. J. Prod. Res. 1988. V. 26. P. 1119-1124.

127. Ignal E., Schrage L. Application of the Branch and Bound Technique to Some Flow Shop Scheduling Problems // Oper. Res. 1965. V. 13. № 3. P. 400-412.

128. Ishibuchi Hisao, Misaki Shinta, Tanaka Hideo. Modified simulated annealing algorithms for the flow shop sequencing problem // Euro. J. Oper. Res. 1995. V. 81. P. 388-398.

129. Johnson S. M. Optimal Two- and Three-Stage Production Schedules with Setup Times Included // Nav. Res. Log. Quart. 1954. V. 1. № 1. P. 61-68.

130. Kirkpatrick S., Gelatt C. D., Vecchi M. P. Optimization by simulated annealing // Science. 1983. V. 220, P. 671-680.

131. Kohler W. H., Stieglitz K. Characterization and Theoretical Comparison of Branch-and-Bound Algorithms for Permutation Problems // J. of the ACM. 1974. V. 21. №1. P. 140-156.

132. Lawler E. L., Lenstra J. K., Rinnooy Kan A. H. G. A general bounding scheme for the permutation flow shop problem // Oper. Res. 1978. V. 26. P. 53-67.

133. Lawler E. L., Lenstra J. K., Rinnooy Kan, A. H. G., Shmoys D. B. Sequencing and scheduling: algorithms and complexity // Handbooks in Operations Research and Management Science V. 4. Amsterdam: North Holland, 1993. P. 445-522.

134. Lee C. Y., Cheng Т. С. E., Lin В. M. T. Minimizing the makespan in the 3-machine assembly-type flow shop scheduling problem // Management Sci. 1993. V. 39. P. 616-625.

135. Lenstra J. K. Sequencing By Enumerative Methods // Mathematical Centrum. Amsterdam, 1976. Ch. 12. P. 250-268.

136. Lenstra J. K., Rinnooy Kan A. H. G., P.Brucker. Complexity of machine scheduling problems // Annals of Discrete Mathematics. 1977. V. 1. P. 343-362.

137. Levin V. I., Miretskii I. Yu. Optimal scheduling of jobs in conveyor systems II Automat. Remote Control. 1996. V. 57. № 6. Part 1. P. 773-793. (Translated from Russian)

138. Lomnicki Z. A. A "Branch-Bound" Algorithm for the Exact Solution of the Three-Machine Scheduling Problem // Oper. Res. Quart. 1965. V. 16. № 1. P. 89-100.

139. Manne A. S. On the Job-Shop Scheduling Problem // Oper. Res. 1960. V. 8. №2. P. 219-223.

140. McMahon G. В., Burton P. G. Flow-Shop Scheduling with the Branch-and-BoundMethod// Oper. Res. 1967. V. 15. № 3. P. 473-481.

141. McMahon G. B. Optimal Production Schedules for Flow Shop // Canadian Operational Society J. 1969. № 7. P. 141-151.

142. Miretskii I. Yu. Optimization of Operation of Sequential Systems // J. Computer and System Sciences Intern. 2001. Vol. 40. № 6. P. 909-915. (Translated from Russian)

143. Miretskii I. Yu. Synthesis of Optimal Schedules for Sequential Systems II J. Computer and System Sciences Intern. 2002. Vol. 41. № 1. P. 73-81. (Translated from Russian)

144. Nabeshima I. The Order of n Items Processed on m Machines // J. Oper. Res. Soc. Jap. 1960. V. 2. № 3. P. 170-175; 1961. V. 3. № 4. P. 1-8.

145. Nabeshima I. One the Bound os Makespans and Its Application in M Machine Scheduling Problem // J. Oper. Res. Soc. Jap. 1967. V. 9. № 3, 4. P. 6^4.

146. Nabeshima I. Notes on the Analytical Results in Flow Shop Scheduling Problem. Pt 1, 2 // Reports of the University of Electro-Communications. 1977. № 27. P. 245-252, 253-257.

147. Nawaz M., Enscore E. E., Ham I. A heuristic algorithm of the m-machine, n-job flow-shop sequencing problem // Omega. 1983. V. 11. P. 91-95.

148. Negenman E. G. Local Search Algorithms for the Multiprocessor Flow Shop Scheduling Problem II Euro. J. Oper. Res. 2001. V.128, №1. P. 147-158.

149. Nowicki E., Smutnicki C. A fast tabu search algorithm for the permutation flow-shop problem // Euro. J. Oper. Res. 1996. V. 91. P. 160-175.

150. Nugent С. E. On Sampling Approaches to the Solution of the п-Ъу-т Static Sequencing Problem. Ph. D. thesis. Cornell University, 1964.

151. Palmer D. S. Sequencing jobs through a multi-stage process in the minimum total time a quick method of obtaining a near optimum // Oper. Res. Quart. 1965. V. 16. P. 101-107.

152. Pinedo M. Scheduling: Theory, Algorithms, and Systems. Prentice-Hall, Englewood Cliffs, New Jersey, 1995.

153. Ogbu F. A., Smith D. K. The application of the simulated annealing algorithm to the solution of the n/m/Cmax flowshop problem // Computers & Oper. Res. 1990. V. 17. № 3. P. 243-253.

154. Ogbu F. A.,Smith D. K. Simulated annealing for the permutation flowshop problem // OMEGA. 1990. V. 19. № l. p. 64-67.

155. Osman I. H., Potts C. N. Simulated annealing for permutation flow-shop scheduling// OMEGA. 1989. V. 17. № 6. P. 551-557.

156. Potts C. N. An adaptive branching rule for the permutation flow-shop problem // Euro. J. Oper. Res. 1980. V. 5. P. 19-25.

157. Proust C., Gupta J. N. D., Deschamps V. Flow shop scheduling with set-up, processing and removal times separated II Intern. J. Prod. Res. 1991. V. 29. P. 479^93.

158. Reeves C. R. Improving the efficiency of tabu search in machine sequencing problems II J. Oper. Res. Soc. 1993. V. 44. P. 375-382.

159. Reeves C. R. A genetic algorithm for flowshop sequencing // Computers & Oper. Res. 1995. V. 22. P. 5-13.

160. Rios-Mercado R. Z., Bard J. F. An Enhanced TSP-Based Heuristic for Makespan Minimization in a Flow Shop with Setup Times // J. of Heuristics. 1999. V. 5. P. 53-70.

161. Schuurman P. Approximating schedules / Eindhoven: Technische Univer-siteit Eindhoven, The Netherlands. 2000.

162. Shmoys D. В., Stein С., Wein J. Improved approximation algorithms for shop scheduling problems II SLAM J. Comput. 1994. V. 23. P. 617-632.

163. Simons Jr. J. V. Heuristics in Flow Shop Scheduling with Sequence Dependent Set-up Times // Omega. 1992. V. 20. № 2.P. 215-225.

164. Smith M. L., Panwalker S. S., Dudek R. A. Flowshop Sequencing Problem with Ordered Processing Time Matrices // Management Sci. 1975. № 21. P. 544-549.

165. Smith M. L., Panwalker S. S., Dudek R. A. Flowshop Sequencing Problem with Ordered Processing Time Matrices: A General Case // Nav. Res. Log. Quart. 1976. V. 23. № 4, p. 481-486.

166. Smith R. D., Dudek R. A. A General Algorithm for Solution of the n-Job M-Machine Sequencing Problem of the Flow-Shop // Canadian Operational Society J. 1967. № 15. P. 71-82.

167. Smith R. D., Dudek R. A. A General Algorithm for Solution of the n-Job, m-Machine Sequencing Problem of the Flow-Shop. Errata II Oper. Res. 1969. V. 17. № 4. P. 756.

168. Srikar B. N., Ghosh S. "A MILP Model for the n-Job, m-Stage Flowshop with Sequence Dependent Set-up Times // Int. J. Prod. Res. 1986. V. 24. № 6. P. 1459-1474.

169. Stafford E. F., Tseng F. T. On the Srikar-Ghosh MILP Model for the N x M SDST Flowshop Problem II Int. J. Prod. Res. 1990. V. 28. № 10. P. 18171830.

170. Story A. E., Wagner H. M. Computational Experience with Integer Programming for Job-Shop Scheduling. Englewood Cliffs, N.J.: Prentice-Hall, 1963. Ch. 14.

171. Szwarc W. Elimination Methods in the m x n Sequencing Problem // Nav. Res. Log. Quart. 1971. V. 18. № 3. P. 295-305.

172. Szwarc W. Optimal Elimination Methods in the mn Flow-Shop Scheduling Problem II Oper. Res. 1973. V. 21. № 6. P. 1250-1259.

173. Szwarc W. Mathematical Aspects of the 3 x n Job-Shop Sequencing Problem //Nov. Res. Log. Quart. 1974. V. 21. P. 145-153.

174. Szwarc W. Special Cases of the Flow-Shop Problem // Nav. Res. Log. Quart. 1977. V. 24. № 5. P. 483^92.

175. Szwarc W. Permutation Flow-Shop Theory Revizited // Nav. Res. Log. Quart. 1978. V. 25. № 3. P. 557-570.

176. Szwarc W. Dominance Conditions for the Three Machine Flow-Shop Problem // Oper. Res. 1978. V. 26. № 3. P. 203-206.

177. Szwarc W. Precedence Relations of the Flow Shop Problem // Oper. Res. 1981. V. 29. №2. P. 400-411.

178. Szwarc W., Gupta J. N. D. A Flow-shop Problem with Sequence-dependent Additive Setup Times II Nav. Res. Log. 1987. V. 34. № 5. P. 619-627.

179. Szwarc W. The Clustered Flow-Shop Problem // Z. Oper. Res. B. 1988. V. 32. №5. P. 315-322.

180. Szwarc W., Liu J. J. An Approximate Solution of the Flowshop Problem with the Sequence Dependent Setup Times // Z. Oper. Res. A. 1989. V. 33. №6. P. 439-451.

181. Taillard E. Some Efficient Heuristic Methods for the Flow Shop Sequencing Problem // Euro. J. Oper. Res. 1990. V. 47. № 1. P. 65-74.

182. Tovey C. A. Local improvement on discrete structures // Local search in combinatorial optimization. 1997. Chichester: Wiley, P. 57-90.

183. Vaessens R. J. M., Aarts E. H. L., Lenstra J. K. Job shop scheduling by local search H INFORMS J. Computing. 1996. V. 8. P. 302-317.

184. Widmer M., Hertz A. A new heuristic method for the flow shop sequencing problem II Euro. J. Oper. Res. 1989. V. 41. P. 186-193.

185. Yannakakis M. Computational complexity // Local search in combinatorial optimization. 1997. Chichester: Wiley. P. 19-55.