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

• Автор: Кононова, Полина Александровна
• Шифр специальности: 05.13.18
• Научная степень: Кандидатская
• Год защиты: 2012
• Место защиты: Новосибирск
• Количество страниц: 106 с. : ил.

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

1 Вычислительная сложность потоковых задач с буфером

1.1 Сведение к ограниченной задаче

1.2 Перестановочные расписания

1.3 Сложность задачи

1.3.1 Сложность ЯЛРзадачи

1.3.2 ЯРРзадача с быстроймедленной скоростью передачи

1.3.3 Я АР задача с быстроймедлен ной скоростью передачи

2 Нижние и верхние оценки оптимума для цеховых задач потокового типа с активным буфером

2.1 Математическая модель.

2.2 Нижние оценки.
2.2.1 Оценка линейного программирования.
2.2.2 Оценка Джонсона.
2.3 Поиск с чередующимися окрестностями
2.4 Окрестности.
2.5 Численные эксперименты.
3 Нижние и верхние оценки оптимума для цеховых задач потокового типа с пассивным буфером
3.1 Постановка задачи и ее ЦЛП формулировки.
3.2 Окрестности.
3.3 Общая схема метода и ее варианты .
3.4 Построение примеров с известным оптимумом.
3.5 Численные эксперименты
Заключение
Литература


Поэтому одним из перспективных подходов является построение хороших нижних оценок и разработка методов локального поиска с выбором окрестностей, учитывающих структуру задачи. Цель данной работы состоит в разработке и исследовании методов локального поиска для решения цеховой задачи на двух машинах с цифровым буфером, в получении нижних оценок глобального оптимума и построении сложных в вычислительном отношении тестовых примеров, позволяющих указать наиболее трудные подклассы для этих методов. Методика исследований. В диссертации использованы современные методы исследования операций, включающие в себя построение математических моделей, теорию локального поиска и вычислительной сложности, а также методологию экспериментальных исследований с применением вычислительной техники и коммерческих пакетов прикладных программ для решения задач целочисленного линейного программирования. Научная новизна. Оригинальность и научная новизна полученных результатов состоит в следующем. Доказано, что в общем случае задача является ЫР-трудной в сильном смысле. Выделены полиномиально разрешимые случаи. Построены модели целочисленного линейного программирования для различных способов загрузки цифрового буфера. Найден способ корректировки исходных данных существенно улучшающий нижние оценки глобального оптимума. Разработаны итерационные методы локального поиска для решения задачи с активным и пассивным методами загрузки буфера. Практическая и теоретическая ценность. Работа носит теоретический и экспериментальный характер. Установлена вычислительная сложность цеховых задач с цифровым буфером, получены численные методы их решения. Разработанные методы реализованы в виде программ. Они показали свою эффективность и могут применяться при решении практических задач большой размерности, а также при преподавании университетских курсов «Исследование операций» и «Теория принятия решений». Апробация работы. Азиатская международная школа-семинар "Проблемы оптимизации сложных систем", Кыргызская Республика, г. Научные семинары Института математики им. C.J1. Соболева СО РАН. Личный вклад. Представленные в диссертации теоретические результаты получены соискателем лично. Разработка комплекса программ для нахождения верхних оценок методами локального поиска осуществлена самостоятельно. Представление изложенных в диссертации результатов, полученных в совместных исследованиях, с соавторами согласовано. На защиту выносятся только результаты, полученные автором лично. Публикации. По теме диссертации автором опубликовано работ, в том числе 3 статьи в журналах из списка ВАК. Объем и структура диссертации. Диссертация состоит из введения, трех глав и списка литературы ( наименований). Объем диссертации — 6 страниц. Во введении формулируются цель и задачи исследования, обосновывается актуальность выбранной темы и указываются основные методы решения поставленной задачи. Отмечена новизна полученных результатов и их практическая и теоретическая ценность. Приводятся сведения об апробации работы и публикациях. Кратко излагается содержание работы. В первой главе формулируется задача Джонсона с цифровым буфером и ее подзадачи. В диссертации рассматриваются задачи, которые возникают при создании электронно-цифровых библиотек и музеев (]. Медиа-объекты (файлы) загружаются из удаленной базы данных и затем воспроизводятся. Для каждого файла заданы время загрузки и воспроизведения. При загрузке файл поступает в буфер транслирующего устройства и покидает его сразу после завершения воспроизведения. Размер буфера ограничен. Размеры файлов известны и пропорциональны времени загрузки. Воспроизведение файла не может начаться раньше окончания его загрузки. Если файл начал загрузку или воспроизведение, то этот процесс не прерывается. Требуется, так задать порядок загрузки и воспроизведения файлов, чтобы минимизировать время окончания воспроизведения последнего файла. Рассматриваемая задача выбора порядка презентации медиа-объектов тесно связана с цеховой задачей построения расписания в системе потокового типа на двух машинах, которую принято называть задачей Джонсона []. В задаче Джонсона множество работ требуется выполнить на двух машинах.