Sunday, May 31, 2009

Задача о минимуме максимальной загрузки

Задача о минимуме максимальной загрузки (ЗММЗ) содержит семейство векторов, которые требуется разместить таким образом на ограниченной с трех сторон плоскости, чтобы максимум суммы по всем координатам x был минимален. Без потери общности предположим, что каждый вектор может занимать некоторую одну координатуу y. Эти векторы мы можем двигать вправо и влево по занимаемой ими координате. Эта задача напоминает мне полиомино (одним из видов которого является тетрис) и различные задачи упаковки. При этом ЗММЗ несколько от них отличается.

Saturday, May 30, 2009

Нас пригласили в Омск

Я получил email с приглашением нас с моим научным руководителем в Омск на конференцию "Проблемы оптимизации и экономические приложения". Теперь можно начинать готовиться, складывать чемоданы (шутка, что касается чемоданов).

Процесс работы над статьёй

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

N.B. Желательно все прогоны алгоритмов делать заранее.

Thursday, May 28, 2009

Задача о расписании с критерием равномерной нагрузки

Занялся написанием статьи. Рассматриваю в статье задачу равномерного распределения учебной нагрузки для студента. Критерий $\min\max$, т.е. требуется минимизировать максимальную нагрузку за неделю. Представление для хромосом этой задачи. Декартово произведение $n$ множеств $X_i$, где элементом каждого множества является номер позиции в расписании, которую может занять первое занятие данного учебного предмета с номером $i$.

Friday, May 22, 2009

Два экзамена сданы

Английский и философия сданы (оба на пять).

Tuesday, May 19, 2009

Задача составления расписания для ВУЗа как задача теории расписаний

Аудиторное время:одновременно не более &xi студентов
Преподавательское время:одновременно не более одной аудитории
Студенческое время:одновременно не более одной аудитории
Дано множества аудиторий, студентов и преподавателей. Пускай аудитории и преподаватели будут машинами, а студенты работами.
Для выполнения любой работы требуется два ресурса: преподаватель и аудитория.
Кроме того, мы можем рассмотреть студентов также в качестве машин, поскольку одним из ограничений является равномерная загрузка студентов дисциплинами (предметами). Тогда предметы будут рассматриваться как работы, т.е. дополнительно определяется множество дисциплин (предметов), а занятия по данному предмету будут операциями данной работы.
Исходя из этого каждой операции данной работы ставится в соответствие множество подмножеств множества машин, на которых допустимо выполнение этой операции.
Таким образом задача составления расписания для ВУЗа представлена как задача теории расписаний.
Особенностями данной задачи являетя то, что все операции длятся одинаковое время и имеют заранее известное множество возможных времён их начала; одно множество машин может одновременно выполнять одну операцию; поскольку длина расписания задана условием, то критерием может быть распределение операций в расписании, отвечающее определённым требованиям, например равномерная загрузка машин работами; традиционно операции в таком расписании повторяются с заранее заданной периодичностью, например одно занятие в две недели.

Monday, May 18, 2009

Алгоритм Сторера, Ву, Ваккари

Работаю над реализацией названного в заголовке алгоритма. Он является обобщением алгоритмов Гиффлера-Томпсона, которые используются для генерации активных(active) и плотных(non-delay) расписаний для задачи Job Shop.

Wednesday, May 6, 2009

Публикации Александра Бондаренко




Материалы конференций



Статьи в журналах и сборниках


  • Козин И.В., Бондаренко А.С., Полюга С.И.
    Об оценке шарового покрытия пространства перестановок
    // Вісник Запорізького національного університету: Збірник наукових статей. Фізико-математичні науки. - 2009. - № 1. - С. 134-138.
  • Bondarenko O.S., Kozin I.V.
    Evolutionary fragmentary algorithm for permutation flow shop problem
    // Таврический вестник информатики и математики. - 2009. - №2. - С. 47-51.
  • Бондаренко А.С., Козин И.В.
    Эволюционный и фрагментарный подходы к задаче о равномерной нагрузке
    // Искусственный интеллект. - 2009. - № 4. - С. 248-253.

Monday, May 4, 2009

Репродуктивный план Де Джонга R1

Во второй и третьей главах рассматрвается упомянутый в заголовке план R1 (так в те времена называли генетические алгоритмы). В начале четвёртой главы на стр.96 говорится, что для выбора плана из класса планов R1, требуется указать следующие четыре параметра: размер популяции, уровень мутации, уровень кроссовера и разрыв между поколениями (generation gap). Под разрывом между поколениями понимается доля следующего поколения, порождаемая генетическими операторами (стр. 78).

PhD Thesis Де Джонга

Хочу разобраться каким является стандартный набор параметров для генетического алгоритма в PhD Thesis Де Джонга, как выразились Деб и Голдберг в своей статье об обманчивых бинарных функциях.

Задача Job Shop

Занялся написанием кода для данной данной задачи. Выбрал кодировку для своего эволюционного алгоритма, в аглоязычной литературе она называется "operation-based". Автор на которого обычно ссылаются при её использовании Christian Bierwirth (вторая статья в списке). Выражается кодировка в том, что каждый ген представлен номером работы, который повторяется столько раз, сколько данная данная работа имеет операций в задаче, обычно число операций равняется числу машин. Хромосома в результате имеет длину n× m, где n-число работ в задаче, и m-число машин.
Есть ещё такой алгоритм Гиффлера-Томпсона (первая статья), который считается наиболее эффективным для генерации активных расписаний для данной задачи.