Оптимизация процессов обработки заданий в дискретных многостадийных системах тема диссертации и автореферата по ВАК РФ 05.13.01, доктор технических наук Мирецкий, Игорь Юрьевич

• Мирецкий, Игорь Юрьевич
• доктор технических наук
• 2003

Оглавление диссертации доктор технических наук Мирецкий, Игорь Юрьевич

Введение.

Часть 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 г.).

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

ЗАКЛЮЧЕНИЕ

Список литературы диссертационного исследования доктор технических наук Мирецкий, Игорь Юрьевич, 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.