Отчёт по практике: Разработка и реализация эвристики для решения задачи теории расписаний

Оглавление

Введение. 3

1.Постановка задачи. 4

1.1.Содержательное описание проблемы.. 4

1.2.Мат. модель. 4

1.3.Постановка задачи. 4

2.Подходы к решению задачи. 5

2.1.Обзор существующих методов. 5

2.2.Описание решения методом полного перебора. 5

2.3.Описание решения эвристическим методом.. 5

2.4.Применение алгоритма. 5

3.Программная система. 8

3.1.Функциональные возможности программы.. 8

3.2.Формат исходных данных. 8

3.3.Вывод результата. 8

3.4.Планирование эксперимента. 9

3.5.Выводы по результатам эксперимента: 9

Заключение. 10

Список литературы.. 11

Приложение 1. Код основных модулей. 12

Приложение 2. Результаты эксперимента. 18

Введение

Теория расписаний –

Задачи упорядочения -

Задачи одного прибора -

Я считаю, что изучение данной темы является актуальным, задачи о теории расписаний остаются актуальными в самых разных областях.

Целью моей работы является:

1. Изучение основных понятий, связанных с теорией расписаний.

2. Рассмотреть задачу расписаний в системе с одним обслуживающим прибором и методы нахождения оптимальных и «хороших» решений.

3. Разработать и реализовать собственную эвристику.

4. Провести эксперименты.

5. Сделать вывод.

Задача теории расписаний является NP-полной задачей.

• 1. Постановка задачи

  1. Содержательное описание проблемы

Пусть работы множества N = {1, 2, ..., n} обслуживается одним прибором. Каждая работа i, iÎN характеризуется моментом поступления d_i, длительностью обслуживания t_i , директивным сроком D_i , коэффициентом штрафа f_i за каждый такт нарушения директивного срока.

В каждый момент времени прибор обслуживает не более одного требования. Порядок обслуживания требований произвольный. Прерывания в обслуживании каждого отдельного требования не допускаются.

1. Мат. модель

Исходные параметры:

Пусть N = {1, 2, ..., n} – множество работ подлежащих выполнению,

= (t₁, t₂,…, t_n) – вектор длительностей выполнений работ,

= (d₁, d₂,…, d_n) – вектор моментов поступлений работ,

= (D₁, D₂,…, D_n) – вектор директивных сроков,

= (f₁, f₂,…, f_n) – вектор коэффициентов штрафов.

Варьируемые параметры:

= (x₁, x_2, …, x_n) – вектор моментов начала выполнения.

= (y₁, y₂, …, y_n) – вектор моментов окончания выполнения.

Ограничения:

1. y_i=x_i+t_i , iÎN – выполнение работы на машине производится без прерываний;

2. x_j ³ x_i+ t_i или x_i ³ x_j+ t_j , i,jÎN – на машине одновременно может выполняться только одна работа;

3. x_i³d_i , iÎN – выполнение работы не может начаться раньше начального срока;

1. Постановка задачи

Решается задача минимизация стоимости нарушений директивных сроков.

Критерий:

F= → min

минимизация длительности нарушений директивных сроков, где

Алгоритмическая сложность решения задачи O(n!).