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

• Автор: Романова, Анна Анатольевна
• Шифр специальности: 05.13.01
• Научная степень: Кандидатская
• Год защиты: 2006
• Место защиты: Омск
• Количество страниц: 113 с. : ил.

Оглавление
Введение .

1. Задачи теории расписаний и сложность их решения

1.1. Формулировки задач

1.2. Алгоритмическая сложность решения задач

2. Построение циклических расписаний для производственной линии .

2.1. Сложность и свойства задач с различными критериями

2.2. Задача минимизации времени цикла с ограничением .

2.3. Алгоритм для задачи минимизации времени цикла с ограничением .

3. Аппроксимационные схемы решения задач

3.1. Основные определения.

3.2. Аппрокснмационная схема для задачи минимизации времени цикла с ограничением.
3.3. Аппрокснмационная схема для задачи о поставках продукции с одним потребителем.
4. Задача построения расписания для производственной системы открытого типа.
4.1. Исследование структуры оптимальных решении . .
4.2. Модель целочисленного программирования и се свойства
Заключение.
Список использованной литературы


В случае кусочно-линейной целевой функции предложен точный псевдополнномиальный алгоритм, основанный на методе динамического программирования. С использованием 2-приблнженного и псевдополнномнального алгоритмов построена вполне полиномиальная аппроксимационная схема. При получении данной схемы применялся подход из [5,]. Четвертая глава посвящена исследованию задачи минимизации общего времени обслуживания в системе открытого типа. Эта задача является одной из классических задач теории расписаний [], поэтому ее исследование представляет большой научный интерес. В случае трех приборов и трех требований полностью описана структура оптимального решения, а в случае п требований сформулированы гипотезы о такой структуре. Данная техника позволяет существенно сузить множество допустимых решений, которые необходимо проверять на оптимальность. С другой стороны, исследуется возможность применения методов целочисленного программирования для решения этой задачи. Предложена модель ЦЛП, исследованы некоторые свойства ее многогранника. Основные результаты диссертации опубликованы в работах [-, ,,] и докладывались на XL Международной научной студенческой конференции ’’Студент и научно-технический прогресс” (Новосибирск. X Всероссийской конференции ’’Математическое программирование и приложения” (Екатеринбург, ), Российской конференции’’Дискретный анализ и исследование операций” (Новосибирск, , ), II Международном семинаре ’’Discrete Optimization Methods in Production and Logistics” (Омск-Иркутск, ), XVIII международной конференции по комбинаторной оптимизации Conference of the European Chapter on Combinatorial Optimization (Минск, ), a также на семинарах в Омском государственном университете, Институте математики им. С.Л. Соболева СО РАН и его Омском филиале. Автор выражает благодарность научному руководителю В. В. Сер-ваху, A. B. Еремееву н A. A. Колоколову за постоянное внимание и полезные советы. В данной главе рассматриваются постановки исследуемых в работе задач и вопросы сложности их решения. В п. Болес подробно рассматриваются задача построения расписания в обслуживающей системе открытого типа и задача построения циклического расписания для производственной линии. В п. В данном параграфе используется классификация задач построения расписания в многостадийных обслуживающих системах из []. Многие практические ситуации приводят к необходимости изучения многостадийных обслуживающих систем, то есть таких систем, в которых процесс обслуживания требования состоит из нескольких последовательных стадий. На каждой стадии требования обслуживаются тем или иным прибором. Так, изготовление детали обычно включает несколько последовательных операций, выполняющихся на некотором из имеющихся в цехе станков. Процесс подготовки книги к изданию включает такие стадии, как написание рукописи, рецензирование, редактирование, набор и т. В дальнейшем описании постановок задач, в любом случае, имеется конечное множество N = {1,2требовании (деталей, преподавателей, книг и тому подобное) и конечное множество Л/ = {1,2,. Процесс обслуживания требования j Е N включает rj стадий. При этом каждому требованию j Е N и каждой стадии г, i = 1,. Mjj Е Л/, на котором оно должно быть обслужено. Предполагается, что каждый прибор одновременно может обслуживать не более одного требования. Если rj = 7, Mij = г, j = 1,2,. В этой системе каждое требование j Е N сначала обслуживается прибором 1, затем прибором 2 и т. Такая система получила название системы с последовательными приборами и одинаковым порядком (маршрутом) их прохождения всеми требованиями. В зарубежной литературе она известна под названием flow shop. Среди систем с различными порядками (маршрутами) прохождения приборов требованиями наиболее изученными являются системы с последовательными приборами. В таких системах для каждого требования j Е N задается своя, специфическая для этого требования последовательность Mj = (Mi;, Л/2;-,. MTjj) его обслуживания приборами. Требование j сначала обслуживается прибором А/у, затем прибором Л/у и т. Mrjj.