Содержание к диссертации
ВВЕДЕНИЕ 5
I. ЗАДАЧИ КАЛЕНДАРНОГО ПЛАНИРОВАНИЯ, ПОСТАНОВКА И РЕШЕНИЕ ЗАДАЧИ ОДНООПЕРАТОРНОЙ ЛИНИИ
1.1. Анализ моделей и методов решения задач календарного планирования 12
1.2. Классификация задач организации оптимального управления однорядными поточными линиями
1.3. Организация оптимального обслуживания поточной
линии при фиксированно заданных временах обработки
1.3.1. Некоторые утверждения об организации обслуживания поточной линии 22
1.3.2. Построение расписания методом последовательного конструирования 25
1.3.3. Алгоритм построения расписания методом последовательного конструирования
1.3.4. Утверждение о точности алгоритма 52
1.4. Задача оптимального обслуживания поточной линии при интервально заданных временах обработки
1.4.1. Описание технологического процесса 35
1.4.2. Постановка задачи 36
1.4.3. Анализ подходов к решению задачи
1.4.4. Алгоритмы метода Монте-Карло и алгоритмы с использованием ЛПТ- последовательностей
1.5. Построение расписания методом последовательного конструирования с вариацией допусков /2
1.5.1. Анализ возможностей учета допусков V2
1.5.2. Алгоритм построения расписания кб
1.6. Области эффективности развитых методов 49
Выводы
2. ОРГАНИЗАЦИЯ ОБСЛУЖИВАНИЯ ПОТОЧНОЙ ЛИНИИ С УСЛОЖНЕННОЙ СТРУКТУРОЙ 58
2.1. Оптимальное обслуживание поточной линии при наличии параллельных позиций 59
2.2. Задача построения расписания для линии с изменяющейся структурой
2.2.1. Подход к решению задачи 74
2.2.2. Алгоритм и результаты численного эксперимента
2.3. Построение расписания для многооператорной линии при не совмещенных концах обслуживания 77
2.4. Построение расписания для многооператорной линии при совмещенных концах обслуживания S5
2.5. Обобщенный алгоритм построения расписания для поточной линии 13
Выводы ВЦ
3. ОПТИМИЗАЦИЯ ПРОЦЕССА ОБРАБОТКИ ПОДВЕСОК РАЗНЫХ НОМЕНКЛАТУР 96
3.1. Стыковка двух циклических расписаний б
3.2. Алгоритм стыковки двух циклограмм на многооператорной линии
3.3. Поиск оптимальной очередности запуска номенклатур на автооператорную линию 10?
3.4. Поиск очередности запуска различных номенклатур на автооператорную линию в вероятностной постановке
3.5. Поиск оптимальной очередности запуска разных номенклатур на автооператорную линию в условиях неопределенности 115
Выводы 121
ЗАКЛКНЕНИЕ /22
ЛИТЕРАТУРА М
ПРИЛОЖЕНИЕ I. Результаты работы алгоритмов построения расписаний управления автооператорными линиями
П. I. Результаты работы алгоритма PR построения рас писания для автооператорных линий /57
П. 2. Результаты работы алгоритма RSС стыковки расписаний разных номенклатур на многооператорной линии
П.З. Результаты работы алгоритма RSSE поиска очередности запуска разных номенклатур на поточную линию 151
ПРИЛОЖЕНИЕ 2. Внедрения 1
Введение к работе
Постановка и актуальность проблемы. В материалах XX7I съезда КПСС и, в частности, в "Основных направлениях экономического и социального развития народного хозяйства в XI пятилетке" отмечалось, что одним из основных направлений увеличения эффективности социалистического производства является совершенствование методов планирования и управления производством. В решениях ХХУТ съезда КПСС определено начало нового этапа автоматизации производства - переход к массовому созданию автоматизированных участков, цехов и заводов. Наша промышленность наладила выпуск станков с числовым программным управлением, микропроцессоров и автооператорных линий, на базе которых возможно создание встроенных систем управления. Но вместе с тем проблема создания автоматизированных участков и цехов еще далека от своего окончательного решения в плане создания соответствующего программного обеспечения управляющих вычислительных комплексов. Опыт эксплуатации автоматизированных систем управления технологическими процессами (АСУ ТП) показал, что они весьма эффективны в отраслях с непрерывным характером производства, существенно повышают производитель- . ность труда.
В принятом постановлении ЦК КПСС "О мерах по увеличению производства и широкому применению автоматических манипуляторов в отраслях народного хозяйства в свете указаний ХШ съезда КПСС" указывается, что одним из возможных направлений в работе по повышению производительности труда и ускорению научно-технического прогресса в отраслях народного хозяйства является комплексная механизация и автоматизация производства на основе широкого применения промышленных роботов, что будет способствовать решению проблемы трудовых ресурсов.
Развитие информационно-вычислительной техники открыло новые возможности на пути создания роботов-манипуляторов для автоматизации ручных и вспомогательных работ. Роботы-манипуляторы относятся к особому классу автоматических систем. Своеобразие их конструкции заключается в том, что они снабжены как механическими "руками" - манипуляторами, так и "органами" перемещения. Для управления роботом на современном этапе используются вычислительная машина, представляющая собой как бы его "мозг" [ij. Т.к. управление ведется во времени, то в этой ситуации на передний план выходят задачи календарного планирования (КП).
Цель работы и методы исследования. Целью диссертационной работы является исследование класса задач теории расписаний, возникающих при управлении однорядными автооператорными линиями.
Основными задачами являются:
- разработка методов решения задач построения расписаний работы однооператорных, многооператорных поточных линий;
- анализ данных технологического процесса и выделение областей эффективности развитых методов;
- разработка методов построения расписания работы многономенклатурной поточной линии;
- разработка методов поиска очередности запуска различных номенклатур на поточную линию в вероятностной постановке и в условиях неопределенности;
- применение полученных результатов для оптимального управления автооператорными линиями, действующими в составе АСУ ТП гальванического участка.
Для решения поставленных задач используются эвристичес 7
кие методы, метод последовательного конструирования, метод Монте-Карло, метод ЛП-поиска, методы математического, стохастического программирования и теории игр.
Научная новизна. Исследования возможности решения задач КП ведутся в настоящее время по двум направлениям: поиска возможностей решения задачи ЮІ с помощью аппарата математического программирования, поиск решения задачи КП с помощью эвристических методов.
Абстрактные модели небольшой размерности удается решать с помощью методов математического программирования, а при решении реальных задач из-за большой размерности применение методов математического программирования часто затруднено. Решение задач с помощью методов эвристического поиска позволяет получить ряд реально работающих расписаний, используемых на производстве.
В работе автооператорная линия рассматривается как система, которая может иметь различную структуру. Вводится понятие поточной линии с простой структурой. Предложен точный метод последовательного конструирования порядка обслуживания для решения задачи построения расписания работы поточной линии при жестко заданных временах обработки с меньшей трудоемкостью, чем в известных методах.
Разработан эвристический метод последовательного конструирования расписания с вариацией допусков для задачи построения расписания работы поточной линии с простой структурой при интервально заданных временах обработки изделий. Предлагается два варианта решения задачи с помощью метода Монте-Карло. Приводятся алгоритмы конструирования расписания с помощью ЛП последовательностей. Вводится классификация исходной информации по специально разработанным критериям. Для каждого класса исходных данных прогнозируется качество, решения. Строятся области эффективности разработанных методов. Результаты подтверждаются данными численного эксперимента при большом числе опытов.
Вводится понятие условной эквивалентности двух задач построения расписания работы поточной линии с различными структурами. Получены условия сведения задачи построения расписания работы поточной линии с более сложной структурой к задаче построения расписания работы поточной линии с простой структурой.
Рассматривается задача построения расписания для поточной линии с изменяющейся структурой.
Предложен метод построения расписания для многономенклатурной поточной линии. Рассматриваются задачи составления расписания для многономенклатурной поточной линии в вероятностной постановке и в условиях неопределенности.
Практическая ценность. Работа выполнена в соответствии с планом научно-исследовательских работ Казанского химико-технологического института. Для практической реализации результата исследования составлен комплекс программ, позволяющий по определенным критериям оптимально управлять работой многономенклатурной многооператорной линии, действующей в составе АСУ ТП гальванического участка.
Практически программы показали свою работоспособность, приспособленность к промышленным размерностям рассматриваемых процессов и эффективность их применения. Вся система управления обладает большой маневренностью и адаптивностью в условиях изменяющейся информации.
Структура и содержание работы. В первой главе проводится анализ методов, применяемых при решении различных постановок задач КП с литературным обзором. Вводится понятие поточной линии с определенной структурой. Приводится перечень задач, возникающих при организации оптимального обслуживания поточных линий с литературным обзором ранее рассмотренных методов их решения. Предложен точный метод последовательного конструирования расписания для решений задачи построения расписания работы поточной линии с простой структурой при жестко заданных временах обработки. Приводится доказательство точности решения по предложенному алгоритму.
Выделены две области поиска решения задачи построения расписания работы поточной линии с простой структурой при ин-тервально заданных временах обработки. Для этих областей предлагаются разные варианты организации поиска решения с помощью метода Монте-Карло, а также два варианта конструирования решения с помощью метода ЛП-поиска.
Разработан эвристический метод последовательного конструирования порядка обслуживания с вариацией допусков при ин-тервально заданных временах обработки. Приводится алгоритм построения расписания.
Вводится классификация исходной информации по специально разработанным критериям. Для каждого класса исходных данных прогнозируется качество решения. Строятся области эффективности разработанных методов. Приводятся результаты численного эксперимента.
Во второй главе рассматриваются задачи построения расписания работы поточной линии с усложненной и с изменяющейся структурой. Вводится понятие условной эквивалентности двух задач построения расписания работы поточной линии с различными структурами. Разработаны условия, при выполнении которых поиск решения задачи построения расписания работы поточной линий с усложненной структурой можно представить как комбинацию одного или нескольких решений задачи построения расписания работы поточной линии с простой структурой.
Приводится обобщенный алгоритм построения расписания работы поточной линии, позволяющий строить расписания для поточных линий с различной структурой.
В третьей главе рассматриваются задачи построения расписания работы многономенклатурной поточной линии в случае, когда подвески одной номенклатуры поступают на линию партией. Разработаны алгоритмы стыковки расписаний двух различных номенклатур на одной поточной линии. Предложены методы поиска оптимальной очередности запуска на поточную линию разных номенклатур в детерминированной, в вероятностной и-в условиях неопределенности постановках.
Основные результаты, выносимые на защиту. На защиту выносятся следующие результаты:
- методы решения задач построения расписания работы поточной линии с простой структурой при фиксированно и интервально заданных временах обработки;
- метод классификации технологических процессов в зависимости от численных данных процесса и построение областей эффективности для различных методов;
- методы решения задач построения расписания работы поточной линии с усложненной и изменяющейся структурой;
- методы решения задач построения расписания работы многономенклатурной поточной линии для различных структур;
- методы поиска очередности запуска различных номенклатур на поточную линию в вероятностной постановке и в условиях неопределенности ;
- результаты применения разработанных методов для оптимального управления работой автоматизированных автооператорных линий, действующих в составе АСУ ТП гальванического участка.
