📄Работа №132220
Тема: Жадные алгоритмы составления многопроцессорных расписаний
Тип работы
Бакалаврская работа
Предмет
Математика
Объем:
49 листов
Год:
2016
Просмотров:
72
4700
руб.
🛒 Купить работу
Не подходит эта работа?
Закажите новую по вашим требованиям
Узнать цену на написание
Закажите новую по вашим требованиям
Представленный материал является образцом учебного исследования, примером структуры и содержания учебного исследования по заявленной теме. Размещён исключительно в информационных и ознакомительных целях.
Workspay.ru оказывает информационные услуги по сбору, обработке и структурированию материалов в соответствии с требованиями заказчика.
Размещение материала не означает публикацию произведения впервые и не предполагает передачу исключительных авторских прав третьим лицам.
Материал не предназначен для дословной сдачи в образовательные организации и требует самостоятельной переработки с соблюдением законодательства Российской Федерации об авторском праве и принципов академической добросовестности.
Авторские права на исходные материалы принадлежат их законным правообладателям. В случае возникновения вопросов, связанных с размещённым материалом, просим направить обращение через форму обратной связи.
Настоящий учебно-методический информационный материал размещён в ознакомительных и исследовательских целях и представляет собой пример учебного исследования. Не является готовым научным трудом и требует самостоятельной переработки.
📋 Содержание
1. Введение 4
2. Обзор 5
2.1. Реферат статьи авторов Peter Brucker, M.R.Garey, D.S.Johnson 6
2.2. Реферат статьи авторов M.Y.Kovalyov, Jia Xu 10
2.2.1. Ветвление 12
2.2.2. Нижняя граница 16
2.3. Реферат статьи авторов F.Yalaoui, C.Chu 18
2.3.1. Теоретическая основа 18
2.3.2. Алгоритм метода ветвей и границ 22
3. Постановка задачи. 24
4. Алгоритмы. 26
5. Результаты вычислительных экспериментов. 30
Заключение. 33
Список литературы 34
6. Приложение 36
2. Обзор 5
2.1. Реферат статьи авторов Peter Brucker, M.R.Garey, D.S.Johnson 6
2.2. Реферат статьи авторов M.Y.Kovalyov, Jia Xu 10
2.2.1. Ветвление 12
2.2.2. Нижняя граница 16
2.3. Реферат статьи авторов F.Yalaoui, C.Chu 18
2.3.1. Теоретическая основа 18
2.3.2. Алгоритм метода ветвей и границ 22
3. Постановка задачи. 24
4. Алгоритмы. 26
5. Результаты вычислительных экспериментов. 30
Заключение. 33
Список литературы 34
6. Приложение 36
📖 Введение
Задачи упорядочения носят самый общий характер. Они возникают повсюду, где существует возможность выбора той или иной очередности работ: при распределении работ на производстве, составлении расписания приземления самолетов, обслуживании клиентов в банках, формировании очередности выполнения программ вычислительным центром и организации отдыха в праздничные дни. Наша цель — изучить то общее, что характеризует такие задачи независимо от их конкретного содержания.[12]
В терминах теории расписаний можно сформулировать задачу коммивояжера, задачу о разбиении, задачу о раскрое. Идеи и методы, предложенные в теории расписаний, могут быть полезны в других областях дискретной оптимизации. Для решения NP-полных задач часто используются эвристические алгоритмы.
Иногда упорядочение осуществляется случайно, более часто работы выполняются в том порядке, в котором они возникают. Мы не задумываемся о результативности дисциплины ’’первый пришел — первый обслужен”, поскольку она отвечает присущему нам чувству естественного порядка. Однако такая дисциплина, может быть, и приемлема при покупке билетов в театральных кассах, но совсем не обязательна для выполнения работ на предприятии.[12]
В приложениях основная трудность упорядочения заключается в том, что возникающие задачи не могут быть расчленены на самостоятельные, не связанные друг с другом части. Более того, они, как правило, увязаны с рядом других проблем, требующих одновременного решения. [12]
Работа состоит из двух частей. Первая часть — реферативная, и содержит теоретическую основу исследования, основанную на статьях П.Брюкера, М.Р.Гэри, Д.С. Джонсона, М.Ю. Ковалева и Дзиа Сю, и Ф. Ялаои и С.Чу. Вторая часть представляет собой исследование жадных алгоритмов: их реализации и тестирование на языке Delphi, результаты экспериментов и выводы.
В терминах теории расписаний можно сформулировать задачу коммивояжера, задачу о разбиении, задачу о раскрое. Идеи и методы, предложенные в теории расписаний, могут быть полезны в других областях дискретной оптимизации. Для решения NP-полных задач часто используются эвристические алгоритмы.
Иногда упорядочение осуществляется случайно, более часто работы выполняются в том порядке, в котором они возникают. Мы не задумываемся о результативности дисциплины ’’первый пришел — первый обслужен”, поскольку она отвечает присущему нам чувству естественного порядка. Однако такая дисциплина, может быть, и приемлема при покупке билетов в театральных кассах, но совсем не обязательна для выполнения работ на предприятии.[12]
В приложениях основная трудность упорядочения заключается в том, что возникающие задачи не могут быть расчленены на самостоятельные, не связанные друг с другом части. Более того, они, как правило, увязаны с рядом других проблем, требующих одновременного решения. [12]
Работа состоит из двух частей. Первая часть — реферативная, и содержит теоретическую основу исследования, основанную на статьях П.Брюкера, М.Р.Гэри, Д.С. Джонсона, М.Ю. Ковалева и Дзиа Сю, и Ф. Ялаои и С.Чу. Вторая часть представляет собой исследование жадных алгоритмов: их реализации и тестирование на языке Delphi, результаты экспериментов и выводы.
✅ Заключение
В этой работе мы рассматривали задачу составления расписания (Рlj |Lmax).
В первой части работы были рассмотрены расчеты и алгоритмы, представленные в работах П.Брюкера, М.Р.Гэри, Д.С. Джонсона(1977 года), а также М.Ю. Ковалева и Дзиа Сю, и Ф. Ялаои и С.Чу(около 2000 года). Перевод и реферат работ предложен во втором разделе ’’обзор”.
Во второй части работы проводились вычислительные эксперименты для проверки эффективности ’жадного” алгоритма. Для оценки качества решения примем среднее отношения значения решения к нижней границе максимального запаздывания LB. Для демонстрации эффективности мы проверили задачи, сгенерированные случайно, размерностью до 300 заданий. Все они были решены не более чем за 60 секунд.
Оптимальные решения были получены для 63% случаев, полученных ’жадным” методом. Среднее процентное отклонение от нижней границы изменялось в пределах 0.5 — 6.1%.
В первой части работы были рассмотрены расчеты и алгоритмы, представленные в работах П.Брюкера, М.Р.Гэри, Д.С. Джонсона(1977 года), а также М.Ю. Ковалева и Дзиа Сю, и Ф. Ялаои и С.Чу(около 2000 года). Перевод и реферат работ предложен во втором разделе ’’обзор”.
Во второй части работы проводились вычислительные эксперименты для проверки эффективности ’жадного” алгоритма. Для оценки качества решения примем среднее отношения значения решения к нижней границе максимального запаздывания LB. Для демонстрации эффективности мы проверили задачи, сгенерированные случайно, размерностью до 300 заданий. Все они были решены не более чем за 60 секунд.
Оптимальные решения были получены для 63% случаев, полученных ’жадным” методом. Среднее процентное отклонение от нижней границы изменялось в пределах 0.5 — 6.1%.
ИЛИ
Поиск аналога
📕 Список литературы
🖼 Скриншоты
🛒 Оформить заказ
⚡ Работу высылаем в течении 5 минут после оплаты.