📄Работа №54466
Тема: Приближенный алгоритм решения задачи минимизации суммарного штрафа
Характеристики работы
Тип работы
Магистерская диссертация
Предмет
Информатика и вычислительная техника
Объем:
78 листов
Год:
2017
Просмотров:
403
4920
руб.
🛒 Купить работу
Не подходит эта работа?
Закажите новую по вашим требованиям
Узнать цену на написание
Закажите новую по вашим требованиям
Представленный материал является образцом учебного исследования, примером структуры и содержания учебного исследования по заявленной теме. Размещён исключительно в информационных и ознакомительных целях.
Workspay.ru оказывает информационные услуги по сбору, обработке и структурированию материалов в соответствии с требованиями заказчика.
Размещение материала не означает публикацию произведения впервые и не предполагает передачу исключительных авторских прав третьим лицам.
Материал не предназначен для дословной сдачи в образовательные организации и требует самостоятельной переработки с соблюдением законодательства Российской Федерации об авторском праве и принципов академической добросовестности.
Авторские права на исходные материалы принадлежат их законным правообладателям. В случае возникновения вопросов, связанных с размещённым материалом, просим направить обращение через форму обратной связи.
Настоящий учебно-методический информационный материал размещён в ознакомительных и исследовательских целях и представляет собой пример учебного исследования. Не является готовым научным трудом и требует самостоятельной переработки.
📋 Содержание
Введение
ГЛАВА 1. ОБЩИЕ СВЕДЕНИЯ 7
1.1. Возникновение и этапы развития теории расписаний 7
1.2 Способы представления расписаний 12
1.2. Классификация задач теории расписаний 13
1.3. Классификация алгоритмов решения 15
1.4. Классы P и NP 16
ГЛАВА 2. ЗАДАЧА МИНИМИЗАЦИИ СУММАРНОГО ШТРАФА 17
2.1. Постановка задачи 17
2.2. Свойства задачи минимизации суммарного штрафа 19
ГЛАВА 3. АЛГОРИТМ ПОСТРОЕНИЯ ОПТИМАЛЬНОГО РАСПИСАНИЯ 20
3.1. Алгоритмы 20
3.2. Построения оптимального расписания 22
ГЛАВА 4. ПРИБЛИЖЕННЫЙ АЛГОРИТМ С ВЫБОРОМ ДОПУСТИМОГО МЕСТА 24
4.1. Алгоритм 24
4.2. Построения расписания приближенным алгоритмом 29
ГЛАВА 5. АНАЛИЗ ЭФФЕКТИВНОСТИ ПРИБЛИЖЕННОГО АЛГОРИТМА 31
ЗАКЛЮЧЕНИЕ 37
БИБЛИОГРАФИЧЕСКИЙ СПИСОК 39
ПРИЛОЖЕНИЕ 41
ГЛАВА 1. ОБЩИЕ СВЕДЕНИЯ 7
1.1. Возникновение и этапы развития теории расписаний 7
1.2 Способы представления расписаний 12
1.2. Классификация задач теории расписаний 13
1.3. Классификация алгоритмов решения 15
1.4. Классы P и NP 16
ГЛАВА 2. ЗАДАЧА МИНИМИЗАЦИИ СУММАРНОГО ШТРАФА 17
2.1. Постановка задачи 17
2.2. Свойства задачи минимизации суммарного штрафа 19
ГЛАВА 3. АЛГОРИТМ ПОСТРОЕНИЯ ОПТИМАЛЬНОГО РАСПИСАНИЯ 20
3.1. Алгоритмы 20
3.2. Построения оптимального расписания 22
ГЛАВА 4. ПРИБЛИЖЕННЫЙ АЛГОРИТМ С ВЫБОРОМ ДОПУСТИМОГО МЕСТА 24
4.1. Алгоритм 24
4.2. Построения расписания приближенным алгоритмом 29
ГЛАВА 5. АНАЛИЗ ЭФФЕКТИВНОСТИ ПРИБЛИЖЕННОГО АЛГОРИТМА 31
ЗАКЛЮЧЕНИЕ 37
БИБЛИОГРАФИЧЕСКИЙ СПИСОК 39
ПРИЛОЖЕНИЕ 41
📖 Введение
На протяжении всего существования общество сталкивается с различными рода расписаниями. Чаще всего такие проблемы решатся автоматически. Однако и на примитивном уровне человек использует алгоритмы. Планирование строится на основании возрастания крайних сроков выполнения работ. Для решения ежедневных вопросов оказывается достаточно интуитивного подхода. Автоматизация производства, которая развивается довольно стремительно и нарастающий ставят все более трудоемкие задачи разработки алгоритмов составления расписаний.
Одним из разделов исследования операций является теория расписаний. Р. Беллман в 1956 году предложил термин «Теория расписаний». Для того, чтобы решить задачу комбинаторной оптимизации используются алгоритмы и методы решения задач теории расписаний.
Данная диссертационная работа проводит анализ ИР-трудной задачи теории расписаний - минимизации суммарного запаздывания для одного прибора.
NP- сложность задачи минимизации суммарного запаздывания для одного прибора, при условии одновременного поступления требований, была установлена Я.Ду и Ленгом[13]. Е. Лоулером [20] для решения этой задачи в теории, что продолжительности обслуживания pj,j = 1,п, -целые положительные числа, были построены псевдополиномиальный алгоритм трудоемкости О (п4Yj=iPj), который основан на методе динамического программирования, а также полиномиальный алгоритм с оценкой сложности 0(п7/Е). М.Я. Ковалеву [19]смог на порядок понизить эти оценки. В. Хорном были предложены более простые методы решения задачи. Для решения задачи минимизации суммарного запаздывания в [15,16] был применен Метод множителей Лагранжа был применен для решения задачи минимизации суммарного запаздывания.
Задача минимизации суммарного штрафа была сведена Е. Лоулером [21] к задаче о назначениях в случае единичных продолжительностей и одновременном поступлении требований, которую можно решить за 0(п3) операций [4]. Использованию метода динамического программирования для решения задачи минимизации суммарного штрафа также были посвящены работы[1,8,9,11,17], а использованию методов последовательного анализа вариантов - работы [6,10,12,14,22,23]. При дополнительном условии обслуживания требований задача минимизации суммарного штрафа без нарушения директивных сроков рассмотрена в [2,3,5].
Целью данной работы является разработка нового приближенного алгоритма для решения NP-трудной задачи теории расписаний- минимизации суммарного запаздывания для одного прибора, а также проведение сравнительного анализа его эффективности.
Научная новизна. Предложен новый метод нахождения приближенного решения NP-трудной задачи.
Теоретическая и практическая значимость. Приложенные методы могут быть полезны для решения теоретических и практических задач теории расписаний, а также для задач комбинаторной оптимизации. Результаты работы могут быть использованы специалистам, которые занимаются проблемами дискретной математики.
Магистерская диссертация состоит из введения, пяти глав, заключения, библиографического списка (24наименования). Содержит 12 таблиц и 13 иллюстраций. Комплексный объем диссертации составляет 78 страниц.
Результаты диссертации:
1. Реализован алгоритм построения допустимого расписания для NP- трудной задачи теории расписаний - минимизации суммарного запаздывания для одного прибора, а также приближенный алгоритм, для которого приведены экспериментальные оценки его эффективности.
2. На основе алгоритма построения допустимого расписания был реализован приближенный алгоритм с выбором допустимого места.
3. Проведен анализ результатов двух алгоритмов, в результате которого были выявлены некоторые соответствия.
4. Точный и приближенный алгоритмы реализованы в программном продукте "IntellijIDEA" и получил хорошее экспериментальное подтверждение.
Одним из разделов исследования операций является теория расписаний. Р. Беллман в 1956 году предложил термин «Теория расписаний». Для того, чтобы решить задачу комбинаторной оптимизации используются алгоритмы и методы решения задач теории расписаний.
Данная диссертационная работа проводит анализ ИР-трудной задачи теории расписаний - минимизации суммарного запаздывания для одного прибора.
NP- сложность задачи минимизации суммарного запаздывания для одного прибора, при условии одновременного поступления требований, была установлена Я.Ду и Ленгом[13]. Е. Лоулером [20] для решения этой задачи в теории, что продолжительности обслуживания pj,j = 1,п, -целые положительные числа, были построены псевдополиномиальный алгоритм трудоемкости О (п4Yj=iPj), который основан на методе динамического программирования, а также полиномиальный алгоритм с оценкой сложности 0(п7/Е). М.Я. Ковалеву [19]смог на порядок понизить эти оценки. В. Хорном были предложены более простые методы решения задачи. Для решения задачи минимизации суммарного запаздывания в [15,16] был применен Метод множителей Лагранжа был применен для решения задачи минимизации суммарного запаздывания.
Задача минимизации суммарного штрафа была сведена Е. Лоулером [21] к задаче о назначениях в случае единичных продолжительностей и одновременном поступлении требований, которую можно решить за 0(п3) операций [4]. Использованию метода динамического программирования для решения задачи минимизации суммарного штрафа также были посвящены работы[1,8,9,11,17], а использованию методов последовательного анализа вариантов - работы [6,10,12,14,22,23]. При дополнительном условии обслуживания требований задача минимизации суммарного штрафа без нарушения директивных сроков рассмотрена в [2,3,5].
Целью данной работы является разработка нового приближенного алгоритма для решения NP-трудной задачи теории расписаний- минимизации суммарного запаздывания для одного прибора, а также проведение сравнительного анализа его эффективности.
Научная новизна. Предложен новый метод нахождения приближенного решения NP-трудной задачи.
Теоретическая и практическая значимость. Приложенные методы могут быть полезны для решения теоретических и практических задач теории расписаний, а также для задач комбинаторной оптимизации. Результаты работы могут быть использованы специалистам, которые занимаются проблемами дискретной математики.
Магистерская диссертация состоит из введения, пяти глав, заключения, библиографического списка (24наименования). Содержит 12 таблиц и 13 иллюстраций. Комплексный объем диссертации составляет 78 страниц.
Результаты диссертации:
1. Реализован алгоритм построения допустимого расписания для NP- трудной задачи теории расписаний - минимизации суммарного запаздывания для одного прибора, а также приближенный алгоритм, для которого приведены экспериментальные оценки его эффективности.
2. На основе алгоритма построения допустимого расписания был реализован приближенный алгоритм с выбором допустимого места.
3. Проведен анализ результатов двух алгоритмов, в результате которого были выявлены некоторые соответствия.
4. Точный и приближенный алгоритмы реализованы в программном продукте "IntellijIDEA" и получил хорошее экспериментальное подтверждение.
✅ Заключение
Нахождение решения для задачи минимизации суммарного запаздывания является одной из приоритетных задач для комбинаторных задач теории расписаний. Она имеет связь с часто встречающейся задачей теории расписаний, смысл которой состоит в возможности проверить обслуживания заданного множества требований на одном приборе без прерываний и нарушений времени прихода и директивных сроков требований.
Главным результатом данной диссертационной работы является разработка приближенного алгоритма для решения NP-трудной задачи. В данном исследовании применялось четыре алгоритма с разными допустимыми местами, но количество алгоритмов может расширяться исходя из размерности и диапазона значений. В основе приближенного алгоритма лежит точный. Его суть состоит в том, чтобы ограничить выбор допустимого места, что позволяет уменьшить число ограничений, а также время работы алгоритма.
Одним из важных результатов работы является сравнительный анализ приближенного и точного алгоритмов. Можно сделать такие выводы:
1) Выбор первого места при малых размерностях показывает эффективность приближенного алгоритма, но, когда размерности увеличиваются, эффективность уменьшается.
2) Когда выбрано 2 допустимое место каких-либо изменений эффективности не наблюдается в 80% случаев.
3) Аналогично работает алгоритм при выборе среднего места в 75% случаев.
4) Когда выбирается последнее место при работе приближенного алгоритма алгоритм показывает эффективность в 60%.
Анализ эффективности показал, что наилучшие результаты приближенного алгоритма отображаются при выборе первого допустимого места.
Резюмируя, приближенный алгоритм может иметь применение и в других местах, однако, прошу заметить, что, как и у любого алгоритма, он имеет погрешности. Планируется применить данный алгоритм и для других задач комбинаторной оптимизации.
Главным результатом данной диссертационной работы является разработка приближенного алгоритма для решения NP-трудной задачи. В данном исследовании применялось четыре алгоритма с разными допустимыми местами, но количество алгоритмов может расширяться исходя из размерности и диапазона значений. В основе приближенного алгоритма лежит точный. Его суть состоит в том, чтобы ограничить выбор допустимого места, что позволяет уменьшить число ограничений, а также время работы алгоритма.
Одним из важных результатов работы является сравнительный анализ приближенного и точного алгоритмов. Можно сделать такие выводы:
1) Выбор первого места при малых размерностях показывает эффективность приближенного алгоритма, но, когда размерности увеличиваются, эффективность уменьшается.
2) Когда выбрано 2 допустимое место каких-либо изменений эффективности не наблюдается в 80% случаев.
3) Аналогично работает алгоритм при выборе среднего места в 75% случаев.
4) Когда выбирается последнее место при работе приближенного алгоритма алгоритм показывает эффективность в 60%.
Анализ эффективности показал, что наилучшие результаты приближенного алгоритма отображаются при выборе первого допустимого места.
Резюмируя, приближенный алгоритм может иметь применение и в других местах, однако, прошу заметить, что, как и у любого алгоритма, он имеет погрешности. Планируется применить данный алгоритм и для других задач комбинаторной оптимизации.
ИЛИ
Поиск аналога
📕 Список литературы
🛒 Оформить заказ
⚡ Работу высылаем в течении 5 минут после оплаты.
🔍 ПОХОЖИЕ РАБОТЫ ПО ТЕМЕ
Математика
Информатика и вычислительная техника
Информатика и вычислительная техника
Информатика и вычислительная техника
Информатика и вычислительная техника
Информатика и вычислительная техника
Информационные системы
Информатика и вычислительная техника
Информатика и вычислительная техника
Информатика и вычислительная техника
📎 МАГИСТЕРСКАЯ ДИССЕРТАЦИЯ ПО ПРЕДМЕТУ «ИНФОРМАТИКА И ВЫЧИСЛИТЕЛЬНАЯ ТЕХНИКА»
Информатика и вычислительная техника
Информатика и вычислительная техника
Информатика и вычислительная техника
Информатика и вычислительная техника
Информатика и вычислительная техника
Информатика и вычислительная техника
Информатика и вычислительная техника
Информатика и вычислительная техника
Информатика и вычислительная техника
Информатика и вычислительная техника
Информатика и вычислительная техника
Информатика и вычислительная техника
Информатика и вычислительная техника
Информатика и вычислительная техника
Информатика и вычислительная техника