План исследования 8 Современное состояние проблемы 9 Описание эксперимента 10 Метод текущего Парето [7] 10 Метод moga [1] 11

Вид материала

Диссертация

Содержание Способ представления возможных решений [11] Структура геномов Выделение и определение порядка групп Распределение задач среди работников Упорядочение задач

Подобный материал:

• Практических: 0 Лабораторных:, 21.53kb.
• Программа исследования, 416.21kb.
• Правила составления социологической анкеты. Опрос экспертов как метод социологического, 15.89kb.
• Методика это более узкое понятие. Например, в экспериментальном методе исследования, 21.98kb.
• 1 Метод статистического моделирования, 167.94kb.
• Темы курсовых работ по курсу «Программирование» для студентов группы биб-11-1 (2011-2012, 85.51kb.
• Методика исследования 4 Штатно-номенклатурный метод 4 Метод расчета коэффициентов насыщенности, 831.9kb.
• Расшифровка : Наука в целом (информационные технологии 004), 79.71kb.
• Урока литературы в 9 классе на тему: «Древнерусская литература и современность. Золотое, 43.48kb.
• План Экспериментальный метод в науке и его трансформация в метод познавательной деятельности, 192.2kb.

Способ представления возможных решений [11]

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

Вторым важным аргументом в пользу выбора подхода, основанного на кодах расписаний является относительная простота (как будет проиллюстрировано ниже) введения новых типов ограничений в условие задачи. Этот показатель в первую очередь важен для коммерческих приложений.

Структура геномов

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

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

• изменение ключа подзадачи
  

Эта операция полезна в том случае, когда по каким-то причинам нельзя точно верный подключ, но всегда имеется возможность найти ближайшее его верное значение.

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

k_i=l_i%K_i

l_i+1=l_i/K_i

где

k_i - i-й подключ.

l_i - “оставшаяся часть” ключа перед началом вычисления k_i.

K_i - верхний предел i-го подключа

0
c - общее количество подключей

Опишем правило составления ключа после изменения подключа. Для иллюстрации представим ключ в виде функции от его подключей для с=4:

l = ((k₃*K₂+k₂)*K₁+k₁)K₀+k₀)

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



То есть если в процессе разбора ключа сохранять два коэффициента

A_i=; заметим, что A_i+1=A_i*K_i

и

B_i=; заметим, что B_i+1=A_i*k_i+B_i*K_i

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


Задача поиска расписания подразделяется на три подзадачи:

1. выделение и определение порядка групп

2. распределение заданий среди работников

3. упорядочение заданий каждого инженера и распределение их по отрезкам рабочего времени

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

Выделение и определение порядка групп

На практике задачи часто делятся на связанные внутренними зависимостями группы размером порядка 1-10 заданий. Группа задач - результат декомпозиции более высокого уровня детализации процесса предоставления услуг. Задачи из двух разных групп не имеют зависимостей друг от друга. То есть если и , то t_i,k и t_j,l не зависят друг от друга если i не равняется j.

Первым шагом разбора генома является выделение описанных выше групп и их перестановка в соответствии с подключом перестановки.

Далее для каждой из групп последовательно выполняются два последующих шага. После чего начинается обработка следующей группы.

Распределение задач среди работников

Пусть задано множество работников W и множество задач T. А так же для каждой задачи t_i множество инженеров W_i, способных ее выполнить.

Так как каждая задача должна быть выполнена одним и только одним инженером, общее количество вариантов распределения задач будет составлять

K₁=

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

Если принимать во внимание ограничения “Одновременное начало” и “В течение”, требуется учесть следующее правило. Задачи, связанные таким ограничением необходимо назначить двум разным работникам. Уменьшить размер ключа на основе этого правила в общем случае нельзя, так как набор квалифицированных сотрудников уникален для каждой задачи группы, связанной упомянутыми ограничениями.

Введем понятие группы задач G⁽¹⁾ - подмножества задач T, в котором любые две задачи связанны цепочкой из ограничений обоих видов (в данной подзадаче эти ограничения не требуется различать)

На иллюстрации приведен набор задач, принадлежащих одной группе. Стрелками показаны зависимости “В течение”, линиями - “Одновременное начало”. Для трех задач группы выписано множество квалифицированных рабочих.

Не исключено пересечение наборов сотрудников для разных задач группы. В этом случае уменьшение набора доступных рабочих вследствие назначения первой задачи группы какому-либо из них приведет к изменению верхнего предела ключа для последующих задач. До того, как первая задача будет назначена сказать, для каких именно задач изменится верхний предел нельзя. Например, если для задачи t1 будет выбран работник w1, изменится верхний предел подключа t2. Если же будет выбран w2 - предел подключа t3. Поэтому необходимо учитывать изменившийся верхний предел при выборе следующего подключа.

Очевидно, сложность выполнения этой подзадачи пропорциональна количеству задач.

Упорядочение задач

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

Пусть работнику w_i выделено T_i ∈ T задач. T_i при этом принадлежит обрабатываемой в данной момент группе. Введем дополнительно булево свойство каждой из этих задач - является ли она завершающей в своем отрезке времени. Даже если в этот отрезок помещается следующая в перестановке задача

Размер ключа для упорядочения будет ограничен значением

K₂ =

При известных T_i из ключа 022 последовательным делением с остатком выделяется подключ перестановки задач и флаг завершения отрезка рабочего времени для каждой задачи. Флаг вводится для того, чтобы не исключать из рассмотрения те варианты, когда следующая задача может быть начата в i-м отрезке, но будет начата в i+1-м. Кодирование пропуска отрезка рабочего времени не рассматривается, так как на практике такой пропуск не имеет смысла. Если у инженера выходной, отрезок вермени будет удален. Если инженер присутствует на рабочем месте, отказаться от его привлечения полностью всегда менее эффективно, чем назначение ему хотя бы одной задачи.

Зависимость “Начало к концу” необходимо учитывать при перестановке задач каждого инженера. Пусть t₁ зависит от t₂. Очевидно, что если они обе назначены одному и тому же сотруднику, 50% возможных без учета этой зависимости перестановок будут заведомо неверны.

Введем новый тип групп задач - G⁽²⁾ - групп задач, связанных зависимостью “начало к концу” внутри множества заданий, назначенных каждому сотруднику.

На приведенной иллюстрации можно выделить две группы типа G⁽²⁾. Линиями показаны зависимости “Начало к концу” между задачами (без указания направления зависимости). Первая группа состоит из задач t6 и t9. Вторая - из задач t5,t7 и t8. t2 и t3 не входят во вторую группу, так как принадлежат другому работнику. Если бы имела место цепная зависимость t3 -> t7 -> t2, прямая зависимость “начало к концу” t3->t2 была бы вычислена на этапе инициализации.

Разбиение на группы типа G⁽²⁾ позволяет рассматривать не все упорядочения наборов T_i, а только те из них, в которых члены групп упорядочены с учетом зависимостей. То есть размер подключа для i-го инженера будет равен



где - группы типа G⁽²⁾ для i-го инженера.



kg(i,j) - предел подключа группы

size(i,j) - размер группы

Такие группы могут объединять задачи, связанные графами зависимостей. На приведенной иллюстрации возможно несколько вариантов упорядочения задач, отличающихся порядком следования t2, t3, t4 и t5. Если бы группа не включала t5, можно было бы выделить подгруппу задач (t2,t3), внутри которой любой порядок задач давал бы верную перестановку. В последнем случае размер подключа группы был бы равен двум. В общем случае разбиение группы типа G⁽²⁾ на подгруппы может быть произведено не всегда. Но для каждой из задач в любом случае известен номер минимальной и максимальной позиции в группе. Так как на практике группы типа G⁽²⁾ имеют относительно небольшие размеры (максимум порядка четырех-пяти задач в группе), можно ввести ключ перестановки внутри подгруппы как произведение номеров позиций каждой задачи среди доступных ей позиций. Если при расшифровке улюча указанная позиция будет занята, выбирается первая доступная. С помощью предложенного способа коррекции ключей можно избежать дубликатов при генерации решений.

Вычислительная сложность этой подзадачи в худшем случае оценивается как , где T – среднее число задач, присвоенных работнику, I – среднее ычисло задач в группе.ы