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

• Автор: Балашева, Светлана Юрьевна
• Шифр специальности: 05.13.18
• Научная степень: Кандидатская
• Год защиты: 2005
• Место защиты: Воронеж
• Количество страниц: 193 с. : ил.

Содержание
Введение.

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

1.1. Основные понятия теории расписаний.

1.2. Критерии оценки качества расписаний .

1.3. Постановка задачи Веллмана Джонсона.

ЫРтрудность задач теории расписаний .

1.4. Обзор основных методов решения.

1.5. Выводы, постановка цели и задач исследования.

Глава 2. Модификации задачи Беллглана Джонсона.

Математические модели

2.1. Математическая модель для классической постановки
2.2. Задачи с неодновременным поступлением требований в систему. .
2.3. Задачи с неодновременным поступлением требований
и обязательными задержками между стадиями.
2.4. Задача с директивными сроками завершения обслуживания .
2.5. Задачи с ограничением времени обслуживания
2.6. Задачи с непрерывным технологическим циклом
2.7. Задачи с запретом простоев приборов
2.8. Динамическая задача теории расписаний .
2.9. Задача для системы с циклическим производством.
Глава 3. Алгоритмы в задачах теории расписаний
для конвейерных систем.
3.1. Применение метода к задаче
с неодновременным поступлением требований в систему.
3.1.1. Построение функции Лагранжа
3.1.2. Минимизация функции Лагранжа
при фиксированных двойственных переменных.
3.1.3. Вычисление субградиеита
3.1.4. Правила останова.
3.1.5. Пересчет двойственных переменных.
3.1.6. Нижняя оценка длины расписания.
3.1.7. Формальный алгоритм .
3.1.8. Различные подходы к оцениванию верхних границ
простоев приборов и задержек требований.
3.2. Применение метода к другим задачам
3.2.1. Задача с обязательными задержками между стадиями
3.2.2. Задача с непрерывным технологическим циклом .
3.2.3. Задача с непрерывной работой приборов
3.2.4. Задача с директивными сроками завершения обслуживания .
3.2.5. Задачи с ограничением времени обслуживания.
3.2.6. Задача минимизации суммы моментов завершения обслуживания требований в системе с различными моментами поступления
3.2.7. Вычисление нижней оценки суммы моментов
завершения обслуживания требований
3.2.8. Задача для системы с циклическим производством
Глава 4. Расчет календарного плана выпуска деталей
в ОАО ВЭКС.
4.1. Постановка задачи.
4.2. Модель задачи и метод решения.
4.3. Расчет календарного плана. Результаты.
Заключение .
Литература


Задача Беллмана - Джонсона и большинство ее модификаций предполагают детерминированными значения длительностей обработки, переналадки и транспортировки. При недетерминированном подходе для этих величин задаются либо функции распределения, либо интервальные оценки []. Определенный интерес представляет задача с дополнительным условием, что каждый прибор должен функционировать без промежуточных простоев [, ]. Если т=2, то соблюдение этого условия не приводит к увеличению общего времени обслуживания. Во многих публикациях исследуется задача с запретом задержек в процессе обслуживания требований. H.A. Лепешкинский [, ] и другие авторы сводят ее к задаче о коммивояжере. В [-] рассматривается ситуация, когда для каждого требования порядок прохождения приборов задается последовательностью 1, 2,. В.Г. Тимковский [, ] исследовал сложность задачи построения расписаний для таких систем и предложил приближенные методы ее решения. Практически все исследования сводятся к минимизации производственного цикла, то есть направлены на построение расписаний минимальной длины (минимизирующих общее время выполнения системой всех работ). Реже рассматриваются задачи упорядочения по критерию минимизации (взвешенной) суммы моментов завершения обслуживания и задачи построения расписаний, обеспечивающих соблюдение директивных сроков [3, 5, ]. Среди задач теории расписаний можно выделить полиномиально разрешимые и NP-трудные. Для каждой полиномиально разрешимой задачи известен по крайней мере один эффективный алгоритм ее решения, то есть алгоритм, время работы и память которого растут не быстрее, чем степенные функции при увеличении размерности задачи. Большинство задач теории расписаний относятся к классу МР-трудных [, ] (по некоторым оценкам их доля составляет около % от общего числа задач). Их решение связано со значительными вычислительными трудностями, причины возникновения которых заложены в самой комбинаторной природе этих задач. Вопрос о возможности (точного) решения произвольной переборной задачи без полного перебора всех возможных вариантов составляет не решенную к настоящему времени “проблему элиминации полного перебора”. По-видимому, первый результат, из которого следует NP-трудность задачи построения оптимального по быстродействию расписания при т>3, был получен Э. М. Лившицем и В. И. Рублинецким []. При m'Z3 NP-трудными являются также задачи с запретами промежуточных простоев приборов и задачи с запретами задержек в процессе обслуживания требований. ЧР-трудность задачи минимизации максимального временного смещения установлена для т>2 как в случае, когда допускаются прерывания, так и в случае, когда прерывания запрещены. Задача построения расписания, при котором суммарное время обслуживания требований минимально, МР-трудна при т >2 [9]. ЫР-трудность задачи Веллмана - Джонсона при т>3 диктует поиск и разработку приближенных алгоритмов решения. Даже при поиске оптимального перестановочного расписания точное решение может быть найдено только в частных случаях. В статье В. И. Левина и И. Ю. Мирецкого [] дается обзор методов оптимизации, применяемых к решению задач теории расписаний по упорядочению работ в конвейерных системах. Для решения задачи Веллмана - Джонсона используются в основном следующие подходы: комбинаторный анализ, математическое программирование и направленный перебор по методу ветвей и границ [8]. Комбинаторный подход в данном случае сводится к целенаправленной взаимной перестановке групп работ в некоторой исходной последовательности, пока не будет получено оптимальное (приближенно оптимальное) решение. Основополагающей работой по теории расписаний является работа С. Джонсона [], положившая начало исследованиям в области конвейерных систем. В ней, а также в [1, 2], был предложен полиномиальный алгоритм минимизации длины расписания в конвейерной системе с двумя приборами, основанный на взаимной перестановке требований, и доказана его оптимальность. Этот алгоритм приведен в [3, 9], где также выведены неравенства, являющиеся достаточными условиями того, что одно требование предшествует другому. Е.Н.