Помощь студентам в учебе
Приближенный алгоритм решения задачи минимизации суммарного штрафа
|
ВВЕДЕНИЕ 4
ГЛАВА 1. ОБЩИЕ СВЕДЕНИЯ 7
1.1. Возникновение и этапы развития теории расписаний 7
1.2. Классификация задач теории расписаний 12
1.3. Классификация алгоритмов решения 14
1.4. Классы Р и NP 15
ГЛАВА 2. ЗАДАЧА МИНИМИЗАЦИИ СУММАРНОГО ШТРАФА 16
2.1. Постановка задачи 16
2.2. Свойства задачи 18
ГЛАВА 3. АЛГОРИТМ ПОСТРОЕНИЯ ОПТИМАЛЬНОГО РАСПИСАНИЯ 19
3.1. Алгоритмы 19
3.2. Пример построения оптимального расписания 21
ГЛАВА 4. ПРИБЛИЖЕННЫЙ АЛГОРИТМ С ВЫБОРОМ ДОПУСТИМОГО МЕСТА 24
4.1. Алгоритм 24
4.2. Пример построения расписания приближенным алгоритмом 26
ГЛАВА 5. СРАВНИТЕЛЬНЫЙ АНАЛИЗ ЭФФЕКТИВНОСТИ ПРИБЛИЖЕННОГО АЛГОРИТМА 28
ЗАКЛЮЧЕНИЕ
Литература
Приложение
ГЛАВА 1. ОБЩИЕ СВЕДЕНИЯ 7
1.1. Возникновение и этапы развития теории расписаний 7
1.2. Классификация задач теории расписаний 12
1.3. Классификация алгоритмов решения 14
1.4. Классы Р и NP 15
ГЛАВА 2. ЗАДАЧА МИНИМИЗАЦИИ СУММАРНОГО ШТРАФА 16
2.1. Постановка задачи 16
2.2. Свойства задачи 18
ГЛАВА 3. АЛГОРИТМ ПОСТРОЕНИЯ ОПТИМАЛЬНОГО РАСПИСАНИЯ 19
3.1. Алгоритмы 19
3.2. Пример построения оптимального расписания 21
ГЛАВА 4. ПРИБЛИЖЕННЫЙ АЛГОРИТМ С ВЫБОРОМ ДОПУСТИМОГО МЕСТА 24
4.1. Алгоритм 24
4.2. Пример построения расписания приближенным алгоритмом 26
ГЛАВА 5. СРАВНИТЕЛЬНЫЙ АНАЛИЗ ЭФФЕКТИВНОСТИ ПРИБЛИЖЕННОГО АЛГОРИТМА 28
ЗАКЛЮЧЕНИЕ
Литература
Приложение
Человечество на протяжении долгого времени сталкивается с проблемами составления расписаний. В обычной жизни эти проблемы решаются бессознательно. Но даже на обыденном уровне человек исполняет алгоритмы. Часто мы планируем наши действия в порядке возрастания крайних сроков исполнения работ. Для решения бытовых вопросов применение интуитивного подхода оказывается достаточно. Развивающаяся стремительными темпами автоматизация производства и неуклонно увеличивающиеся его масштабы ставят перед научным сообществом всё более и более трудные задачи разработки алгоритмов составления расписаний.
Теория расписаний является одним из разделов исследования операций. Термин "теория расписаний" предложил Р. Веллман в 1956 году. Методы и алгоритмы решения задач теории расписаний применяются для решения задач комбинаторной оптимизации.
Диссертационная работа посвящена исследованию NP-трудной задачи теории расписаний - минимизации суммарного запаздывания для одного прибора.
NP - трудность задачи минимизации суммарного запаздывания для одного прибора, в случае одновременного поступления требований, была установлена Я. Ду и Ленгом [13]. Е. Лоулером [20] для решения этой задачи в предположении, что продолжительности обслуживания pjJ = 1, п, -целые положительные числа, построены псевдополиномиальный алгоритм трудоемкости О (n4 Yj=1 Pj), основанный на идее метода динамического программирования, а также вполне полиномиальный алгоритм с оценкой сложности 0(п7/е). М.Я. Ковалеву [19] удалось на порядок понизить эти оценки. Простые методы решения задачи были предложены В. Хорном [18].
В [15,16] для решения задачи минимизации суммарного запаздывания был применен метод множителей Лагранжа.
В случае единичных продолжительностей и одновременном поступлении требований задача минимизации суммарного штрафа была сведена Е. Лоулером [21] к задаче о назначениях, которую можно решить за О (л3) операций [4]. Применению метода динамического программирования для решения задачи минимизации суммарного штрафа посвящены работы[1,8,9,11,17], а использованию методов последовательного анализа вариантов - работы [6,10,12,14,22,23]. Задача минимизации суммарного штрафа при дополнительном условии обслуживания требований без нарушения директивных сроков рассмотрена в [2,3,5].
Целью работы является разработка нового приближенного алгоритма для решения NP-трудной задачи теории расписаний - минимизации суммарного запаздывания для одного прибора, а также проведение сравнительного анализа его эффективности.
Научная новизна. Предложена новая схема нахождения приближенного решения NP-трудной задачи.
Теоретическая и практическая значимость. Предложенные подходы могут быть использованы для решения теоретических и практических задач теории расписаний, а также для задач комбинаторной оптимизации. Результаты работы могут быть полезны специалистам занимающимися проблемами дискретной оптимизации.
Диссертация состоит из введения, пяти глав, заключения, библиографического списка (23 наименования). Содержит 12 таблиц и 11 иллюстраций. Общий объем диссертации составляет 66 страниц.
Основные результаты диссертации:
1. Реализован алгоритм построения допустимого расписания для NP- трудной задачи теории расписаний - минимизации суммарного запаздывания для одного прибора, а также приближенный алгоритм, для которого приведены экспериментальные оценки его эффективности.
2. На основе алгоритма построения допустимого расписания разработан приближенный алгоритм с выбором допустимого места.
3. Проведен сравнительный анализ результатов двух алгоритмов, выявлены некоторые закономерности.
4. Ряд полученных результатов доведен до практической реализации в программном продукте "Delphi 7" и получил хорошее экспериментальное подтверждение.
Теория расписаний является одним из разделов исследования операций. Термин "теория расписаний" предложил Р. Веллман в 1956 году. Методы и алгоритмы решения задач теории расписаний применяются для решения задач комбинаторной оптимизации.
Диссертационная работа посвящена исследованию NP-трудной задачи теории расписаний - минимизации суммарного запаздывания для одного прибора.
NP - трудность задачи минимизации суммарного запаздывания для одного прибора, в случае одновременного поступления требований, была установлена Я. Ду и Ленгом [13]. Е. Лоулером [20] для решения этой задачи в предположении, что продолжительности обслуживания pjJ = 1, п, -целые положительные числа, построены псевдополиномиальный алгоритм трудоемкости О (n4 Yj=1 Pj), основанный на идее метода динамического программирования, а также вполне полиномиальный алгоритм с оценкой сложности 0(п7/е). М.Я. Ковалеву [19] удалось на порядок понизить эти оценки. Простые методы решения задачи были предложены В. Хорном [18].
В [15,16] для решения задачи минимизации суммарного запаздывания был применен метод множителей Лагранжа.
В случае единичных продолжительностей и одновременном поступлении требований задача минимизации суммарного штрафа была сведена Е. Лоулером [21] к задаче о назначениях, которую можно решить за О (л3) операций [4]. Применению метода динамического программирования для решения задачи минимизации суммарного штрафа посвящены работы[1,8,9,11,17], а использованию методов последовательного анализа вариантов - работы [6,10,12,14,22,23]. Задача минимизации суммарного штрафа при дополнительном условии обслуживания требований без нарушения директивных сроков рассмотрена в [2,3,5].
Целью работы является разработка нового приближенного алгоритма для решения NP-трудной задачи теории расписаний - минимизации суммарного запаздывания для одного прибора, а также проведение сравнительного анализа его эффективности.
Научная новизна. Предложена новая схема нахождения приближенного решения NP-трудной задачи.
Теоретическая и практическая значимость. Предложенные подходы могут быть использованы для решения теоретических и практических задач теории расписаний, а также для задач комбинаторной оптимизации. Результаты работы могут быть полезны специалистам занимающимися проблемами дискретной оптимизации.
Диссертация состоит из введения, пяти глав, заключения, библиографического списка (23 наименования). Содержит 12 таблиц и 11 иллюстраций. Общий объем диссертации составляет 66 страниц.
Основные результаты диссертации:
1. Реализован алгоритм построения допустимого расписания для NP- трудной задачи теории расписаний - минимизации суммарного запаздывания для одного прибора, а также приближенный алгоритм, для которого приведены экспериментальные оценки его эффективности.
2. На основе алгоритма построения допустимого расписания разработан приближенный алгоритм с выбором допустимого места.
3. Проведен сравнительный анализ результатов двух алгоритмов, выявлены некоторые закономерности.
4. Ряд полученных результатов доведен до практической реализации в программном продукте "Delphi 7" и получил хорошее экспериментальное подтверждение.
Задача минимизации суммарного запаздывания является одной из важнейших комбинаторных задач теории расписаний. Она тесно связана с часто встречающейся задачей теории расписаний состоящей в проверке возможности обслуживания заданного множества требований на одном приборе без прерываний и нарушений времени поступления и директивных сроков требований.
Основным результатом данного исследования является разработка алгоритма 2 для решения NP-трудной задачи. В данном исследовании применялось четыре алгоритма с разными допустимыми местами, однако прошу заметить, что количество алгоритмов может расширяться в зависимости от размерности задачи и диапазона значений. В основе алгоритма 2 лежит алгоритм 1 . Его суть в дополнительных ограничениях на допустимые места, что позволяет сократить число генерируемых ограничений и, соответственно, время работы алгоритма.
Также важным является построение самого алгоритма 1, с помощью которого удалось оценить эффективность алгоритма 2. На основе представленных экспериментов можно сделать следующие выводы:
1) При выборе первого допустимого места и при малых размерностях алгоритм 2 работает хорошо, однако при увеличении размерности теряет свою эффективность.
2) При выборе второго допустимого места алгоритма 2, увеличения и уменьшения эффективности не наблюдается. На всех размерностях дает в среднем 80% верных результатов.
3) При выборе среднего допустимого места алгоритм 2, также же, как при втором допустимом месте, работает равномерно, однако в среднем дает 75% верных результатов.
4) При выборе последнего допустимого места алгоритма 2, эффективность достигает 98% на размерностях от 35 и выше, это может быть связано с большим разбросом значений случайного расписания.
Анализ эффективности показал, что наилучшие результаты алгоритма 2 получаются при выборе первого и последнего допустимого места. Также были выявлены некоторые рекомендации при применении алгоритма 2:
1. При малых размерностях и малых диапазонах случайных расписаний, лучше применять алгоритм 2 с первым допустимым местом, это касается размерности меньше 10.
2. При больших размерностях рекомендовано использовать алгоритм 2 с последним допустимым местом.
В целом алгоритм 2, может быть, применим и на других допустимых местах, ведь как и у любого приближенного алгоритма, он имеет погрешности. Однако в ходе исследования нами доказано, что погрешность алгоритма 2 минимальна. Планируется применить данный алгоритм и для других задач комбинаторной оптимизации.
Основным результатом данного исследования является разработка алгоритма 2 для решения NP-трудной задачи. В данном исследовании применялось четыре алгоритма с разными допустимыми местами, однако прошу заметить, что количество алгоритмов может расширяться в зависимости от размерности задачи и диапазона значений. В основе алгоритма 2 лежит алгоритм 1 . Его суть в дополнительных ограничениях на допустимые места, что позволяет сократить число генерируемых ограничений и, соответственно, время работы алгоритма.
Также важным является построение самого алгоритма 1, с помощью которого удалось оценить эффективность алгоритма 2. На основе представленных экспериментов можно сделать следующие выводы:
1) При выборе первого допустимого места и при малых размерностях алгоритм 2 работает хорошо, однако при увеличении размерности теряет свою эффективность.
2) При выборе второго допустимого места алгоритма 2, увеличения и уменьшения эффективности не наблюдается. На всех размерностях дает в среднем 80% верных результатов.
3) При выборе среднего допустимого места алгоритм 2, также же, как при втором допустимом месте, работает равномерно, однако в среднем дает 75% верных результатов.
4) При выборе последнего допустимого места алгоритма 2, эффективность достигает 98% на размерностях от 35 и выше, это может быть связано с большим разбросом значений случайного расписания.
Анализ эффективности показал, что наилучшие результаты алгоритма 2 получаются при выборе первого и последнего допустимого места. Также были выявлены некоторые рекомендации при применении алгоритма 2:
1. При малых размерностях и малых диапазонах случайных расписаний, лучше применять алгоритм 2 с первым допустимым местом, это касается размерности меньше 10.
2. При больших размерностях рекомендовано использовать алгоритм 2 с последним допустимым местом.
В целом алгоритм 2, может быть, применим и на других допустимых местах, ведь как и у любого приближенного алгоритма, он имеет погрешности. Однако в ходе исследования нами доказано, что погрешность алгоритма 2 минимальна. Планируется применить данный алгоритм и для других задач комбинаторной оптимизации.