Введение
Глава 1. Задачи теории расписаний для систем конвейерного типа 9
1.1. Основные понятия теории расписаний 9
1.2. Критерии оценки качества расписаний 12
1.3. Постановка задачи Беллмана - Джонсона.
NP-трудность задач теории расписаний 14
1.4. Обзор основных методов решения 17
1.5. Выводы, постановка цели и задач исследования 40
Глава 2. Модификации задачи Беллмана - Джонсона. Математические модели 42
2.1. Математическая модель для классической постановки 42
2.2. Задачи с неодновременным поступлением требований в систему . 46
2.3. Задачи с неодновременным поступлением требований и обязательными задержками между стадиями 50
2.4. Задача с директивными сроками завершения обслуживания 53
2.5. Задачи с ограничением времени обслуживания 58
2.6. Задачи с непрерывным технологическим циклом 60
2.7. Задачи с запретом простоев приборов 62
2.8. Динамическая задача теории расписаний 65
2.9. Задача для системы с циклическим производством 71
Глава 3. Алгоритмы в задачах теории расписаний для конвейерных систем 77
3.1. Применение метода к задаче
с неодновременным поступлением требований в систему 78
3.1.1. Построение функции Лагранжа 78
3.1.2. Минимизация функции Лагранжа
при фиксированных двойственных переменных 81
3.1.3. Вычисление субградиента 83
3.1.4. Правила останова 86
3.1.5. Пересчет двойственных переменных 87
3.1.6. Нижняя оценка длины расписания 88
3.1.7. Формальный алгоритм 89
3.1.8. Различные подходы к оцениванию верхних границ простоев приборов и задержек требований 93
3.2. Применение метода к другим задачам 98
3.2.1. Задача с обязательными задержками между стадиями 99
3.2.2. Задача с непрерывным технологическим циклом 100
3.2.3. Задача с непрерывной работой приборов 102
3.2.4. Задача с директивными сроками завершения обслуживания 104
3.2.5. Задачи с ограничением времени обслуживания 104
3.2.6. Задача минимизации суммы моментов завершения обслуживания требований в системе с различными моментами поступления ; ..,.107
3.2.7. Вычисление нижней оценки суммы моментов завершения обслуживания требований 109
3.2.8. Задача для системы с циклическим производством 113
Глава 4. Расчет календарного плана выпуска деталей вОАО«ВЭКС» 125
4.1. Постановка задачи 125
4.2. Модель задачи и метод решения 131
4.3. Расчет календарного плана. Результаты 146
Заключение 154
Литература
