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

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

Автор: Балашева, Светлана Юрьевна

Шифр специальности: 05.13.18

Научная степень: Кандидатская

Год защиты: 2005

Место защиты: Воронеж

Количество страниц: 193 с. ил.

Артикул: 2830699

Автор: Балашева, Светлана Юрьевна

Стоимость: 250 руб.

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

Содержание
Введение.
Глава 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], где также выведены неравенства, являющиеся достаточными условиями того, что одно требование предшествует другому. Е.Н.

Рекомендуемые диссертации данного раздела

28.06.2016

+ 100 бесплатных диссертаций

Дорогие друзья, в раздел "Бесплатные диссертации" добавлено 100 новых диссертаций. Желаем новых научных ...

15.02.2015

Добавлено 41611 диссертаций РГБ

В каталог сайта http://new-disser.ru добавлено новые диссертации РГБ 2013-2014 года. Желаем новых научных ...


Все новости

Время генерации: 0.469, запросов: 244