Дипломная Работа




НазваниеДипломная Работа
страница8/13
Дата публикации29.07.2013
Размер0.52 Mb.
ТипДиплом
lit-yaz.ru > Информатика > Диплом
1   ...   5   6   7   8   9   10   11   12   13
^

6.3Описание основного алгоритма


Основная идея разработанного алгоритма заключается в сочетании жадных стратегий с алгоритмом ограниченного перебора. Жадные стратегии составляют основу разработанного алгоритма и используются для быстрого построения расписания с условием выполнения требований корректности расписания. Алгоритм ограниченного перебора используется в случае невозможности нахождения решения на очередной итерации (невозможность разместить очередную работу) и представлен в виде процедуры «отката», которая перераспределяет ранее размещенные работы с целью разместить данную работу. На каждой итерации алгоритм размещает одну работу с учетом критериев оптимальности, каждый раз получая корректное расписание. Общую схему работы алгоритма можно представить следующим образом:

  1. Сформировать список работ на основе исходных данных.

  2. Выбрать очередную работу из списка.

  3. Выбрать время, аудиторию и преподавателя для данной работы.

  4. Если выбранную работу разместить невозможно, то попытаться разместить ее при помощи процедуры корректировки расписания.

  5. Удалить работу из списка.

  6. Если список работ не пуст, то перейти к п.2, иначе завершить работу.

Реализовано три различных варианта алгоритма, различающихся сложностью и качеством полученного расписания (как с точки зрения значения штрафной функции, так и с точки зрения количества размещенных работ). Различия в работе этих алгоритмов заключается в способе выбора из списка очередной размещаемой работы.

Алгоритм 1:

  1. Формирование списка работ, списка размещенных и неразмещенных занятий, гиперкубов.

  2. Список неразмещенных занятий сортируется по количеству групп |lnsi.Job.Groups|

  3. Находим первое возможное время размещения для первого неразмещенного занятия: Count (1,1)

  4. Размещаем занятие на выбранное время: Schedule (1, resWeek, resDay, resPair)

  5. В соответствии с добавленным занятием корректируем списки и гиперкубы: Insert (n)

  6. Если |LessonsNotShed|  0 (еще не все работы размещены), то переход к п.3

Алгоритм 2:

  1. Формирование списка работ, списка размещенных и неразмещенных занятий, гиперкубов.

  2. Список неразмещенных занятий разбивается на классы по количеству групп |lnsi.Job.Groups|.

  3. Количество возможных размещений: num = 2*MaxDays*MaxPairs

  4. Занятие, которое будет размещено на очередном шаге: lessNum = 0

  5. Рассматриваемое в данный момент занятие: i=1

  6. Считаем количество возможных размещений: Count (i,0)

  7. Для занятия с минимальным количеством возможных размещений запоминаем оптимальное по значению штрафной функции место в расписании: c num num = c; lessNum = i; Week = resWeek; Day = resDay; Pair = resPair

  8. Если i<|LessonNotShed1| (кол-во занятий из 1-го класса)  i=i+1; переход к п.7

  9. Размещаем занятие с минимальным количеством возможных размещений на запомненное место в расписании: Schedule (lessNum, Week, Day, Pair)

  10. В соответствии с добавленным занятием корректируем списки и гиперкубы: Insert (lessNum)

  11. Если |LessonsNotShed| 0, то переход к п.5 (поскольку операция Insert удаляет занятие из списка LessonsNotShed, то когда первый класс становится пустым, следующий класс становится первым)

Алгоритм 3:

  1. Формирование списка работ, списка размещенных и неразмещенных занятий, гиперкубов.

  2. Количество возможных размещений: num = 2*MaxDays*MaxPairs

  3. Занятие, которое будет размещено на очередном шаге: lessNum = 0

  4. Рассматриваемое в данный момент занятие: i=1

  5. Считаем количество возможных размещений: Count (i,0)

  6. Для занятия с минимальным количеством возможных размещений запоминаем оптимальное по значению штрафной функции место в расписании: c num num = c; lessNum = i; Week = resWeek; Day = resDay; Pair = resPair

  7. i<|LessonNotShed| i=i+1; переход к п.6

  8. Размещаем занятие с минимальным количеством возможных размещений на запомненное место в расписании: Schedule (lessNum, Week, Day, Pair)

  9. В соответствии с добавленным занятием корректируем списки и гиперкубы: Insert (lessNum)

  10. Если |LessonsNotShed| 0, то переход к п.3
1   ...   5   6   7   8   9   10   11   12   13

Похожие:

Дипломная Работа iconНазвание организации
Заголовок «Дипломная работа» или «Курсовая работа»: Times New Roman, 14 (вопреки П. 113), по центру. Затем – 2 пустые строки

Дипломная Работа iconДипломная работа
Степень удовлетворенности пользователей в документах по музыкальному искусству 25

Дипломная Работа iconДипломная работа
Состояние, тенденции и проблемы развития народного образования в Новом Уренгое

Дипломная Работа iconДипломная работа
Разработка анализатора системы обнаружения атак, основанного на методах кластерного анализа”

Дипломная Работа iconДипломная работа
Удостоверение подлинности участников интернет-голосований на основе анализа сетевых сессий

Дипломная Работа iconДипломная работа
Удостоверение подлинности участников интернет-голосований на основе анализа сетевых объектов

Дипломная Работа iconДипломная работа
Удостоверение подлинности участников интернет-голосований на основе анализа сетевых объектов

Дипломная Работа iconДипломная работа
Удостоверение подлинности участников интернет-голосований на основе анализа сетевых объектов

Дипломная Работа iconДипломная работа
Повышение качества результатов анонимного интернет-голосования методом анализа сетевых объектов

Дипломная Работа iconДипломная работа
Использование средств olap-технологий для построения системы Бизнес Интеллекта факультета



Образовательный материал



При копировании материала укажите ссылку © 2013
контакты
lit-yaz.ru
главная страница