Есть очень большое желание написать программу для составления графика выходов сотрудников на работу. Суть задачи (упрощенно) в том — что бы программа моя составляла табличку выходов сотрудника за месяц из исходных данных (количество сотрудников в отделе, тип графика (4:2; 5:2; т.е. количество рабочих:выходных дней), приоритет сотрудника (например "нехочу работать по воскресеньям" и т.д.). Результат в итоге табличка по горизонтали дни месяца, по вертикали сотрудники, на пересечении осей выходы сотрудника в этот день.... В идеале программа должна создать оптимальный график.

У меня немалый опыт в программировании задач финансового учета (с БД мне кажется я "на ты"), но таких зада не программировал ниразу. Немного подумав над этой задачей предполагаю что решение связано каким то образом с "Вышкой" т.е. с высшей математикой.... почему предполагаю потому что "вышку" эту я не учил... к сожалению и выучить, за короткий срок, достаточно настолько что бы самому определить нужный мне алгоритм. Поэтому прошу общественность "натолкнуть" меня на путь решения этой задачи. Или хоты бы объяснить принцыпы этой "комбинаторики"...

Писать хочу на C# используюя Visual Studio (это с целью изучения продукта как такового)... Ранее писал на Delphi.

Буду благодарен за любую помощь по этому вопросу!

Здравствуйте, mvg_first, Вы писали:

_>Есть очень большое желание написать программу для составления графика выходов сотрудников на работу. Суть задачи (упрощенно) в том — что бы программа моя составляла табличку выходов сотрудника за месяц из исходных данных (количество сотрудников в отделе, тип графика (4:2; 5:2; т.е. количество рабочих:выходных дней), приоритет сотрудника (например "нехочу работать по воскресеньям" и т.д.). Результат в итоге табличка по горизонтали дни месяца, по вертикали сотрудники, на пересечении осей выходы сотрудника в этот день.... В идеале программа должна создать оптимальный график.

_>У меня немалый опыт в программировании задач финансового учета (с БД мне кажется я "на ты"), но таких зада не программировал ниразу. Немного подумав над этой задачей предполагаю что решение связано каким то образом с "Вышкой" т.е. с высшей математикой.... почему предполагаю потому что "вышку" эту я не учил... к сожалению и выучить, за короткий срок, достаточно настолько что бы самому определить нужный мне алгоритм. Поэтому прошу общественность "натолкнуть" меня на путь решения этой задачи. Или хоты бы объяснить принцыпы этой "комбинаторики"...

_>Писать хочу на C# используюя Visual Studio (это с целью изучения продукта как такового)... Ранее писал на Delphi.

_>Буду благодарен за любую помощь по этому вопросу!

Вам нужна Теория Расписаний. Насколько я помню эту задачу так и не удалось полностью переложить на компьютер. Так что врят ли вам кто-то готовое решение даст.

Здравствуйте, SteMage, Вы писали:

SM>Вам нужна Теория Расписаний. Насколько я помню эту задачу так и не удалось полностью переложить на компьютер. Так что врят ли вам кто-то готовое решение даст.

Ну вообще-то готового решения я и не жду. Исчезает всякий спортивный интерес. А вот советы или направление для копания... это всегда приветствуется.

Здравствуйте, mvg_first, Вы писали:

_>Здравствуйте, SteMage, Вы писали:

SM>>Вам нужна Теория Расписаний. Насколько я помню эту задачу так и не удалось полностью переложить на компьютер. Так что врят ли вам кто-то готовое решение даст.

_>Ну вообще-то готового решения я и не жду. Исчезает всякий спортивный интерес. А вот советы или направление для копания... это всегда приветствуется.

По отрывкам из моих университетских воспоминаний (3-4 года назад). У нас на кафедре был преподователь, который занимался Теорий Расписания, довольно долго и много. Сейчас к сожалению, не вспомню где, что бы то ни было можно найти. Но капать нужно именно в сторону Теории Расписания.

Соглашусь с предыдущими постами. Если честно я сам пытался заняться этим и смотрел соответствующую теорию. Видимо IQ не хватило . Из тех систем которые я видел (например для создания школных расписаний) все работает по методу нучного тыка. Т.е. путем тупого перебора всех вариантов. Скорость как вы понимаете никакая

Уважаемый Василий.

Очевидно, Ваша задача относится к классу задач Дискретной Оптимизации. Для любой задачи оптимизации необходимо определиться как минимум с:
1. Алгоритмом (способом) построения допустимого решения (в Вашем случае — расписания)
2. Критерием оптимальности

Что касается алгоритмов решения, то их можно разделить на два класса:
1. Алгоритмы поиска точного (оптимального) решения. В случае NP-полных задач (к которым, по всей видимости, относится и Ваша /на самом деле, это ещё надо доказать/), для получения точного решения не существует (точнее, скорее всего не существует) алгоритма полиномиальной сложности. Другими словами, число возможных вариантов решения растёт экспоненциально от размерности задачи. Классическая NP-полная задача — задача коммивояжера. Другой пример – криптография (подбор ключа перебором). Увеличение длины ключа на один бит увеличивает количество вариантов на порядок (т.е. ключ длиной 2 бита -> 4 варианта, 3 -> 8 вариантов, 8 -> уже 256!).
Тем не менее, даже для NP-полных задач перебор зачастую удается сократить, используя алгоритмы неявного перебора (динамическое программирование, метод ветвей и границ). В худшем случае такие алгоритмы вырождаются в полный перебор, однако на реальных данных позволяют решать поставленные задачи за разумное время.

Вывод: полный или сокращённый перебор позволяет найти оптимальное решение при небольшой размерности задачи.

2. Алгоритмы поиска приближенного решения

2.1. Алгоритмы с гарантированной оценкой. Такие алгоритмы находят решение, приближенное к оптимальному и гарантируют, что качество такого решения (например, полученное решение будет отличаться от оптимума не более чем в 2 раза). К сожалению, далеко не для каждой задачи можно построить такой алгоритм.

2.2. Универсальные приближенные алгоритмы — генетический алгоритм, алгоритм имитации отжига и прочее. Мощное средство, но в умелых руках. Гарантированные оценки построить довольно сложно (если вообще возможно). Тем не менее, алгоритмы работают, и часто очень неплохо.

2.3. Эвристические алгоритмы. Что называется, алгоритм "на коленке". Такие методы обычно привязаны к задаче, учитывают её специфику и основаны на предыдущем опыте её решения.

Итак, приступая к решению Вашей задачи необходимо:

1. Выбрать критерий оптимальности решения
   
2. Оценить комбинаторную сложность (размерность перебора)
   
3. Разработать алгоритм построения допустимого решения (без такого алгоритма оптимизация точно не получится)
   
4. Попытаться "подогнать" задачу под какую-нибудь известную модель (что вряд ли удастся). Т.е. попытаться построить, например, графовую интерпретацию
   
5. Выбрать алгоритм оптимизации (если не удалось подогнать под стандартную модель, то выбираем из приведённых выше вариантов). Если перебор не слишком большой, то можно попробовать переборный алгоритм, особенно если можно его сократить (например методом ветвей и границ). В случае большой размерности — применяем приближённые алгоритмы. Здесь Вам поможет только эксперимент, причём на задачах малой размерности (которые всё же можно перебрать). Если приближённое решение окажется близким к оптимуму, то можно лишь надеяться, что при большей размерности решение будет столь же качественным (если Вам удалось построить гарантированную оценку, в качестве решения можно быть уверенным)

Всё вышесказанное — теория.
На мой взгляд, в Вашей задаче стоит подумать над эвристикой. Т.е. попробуйте понять, как бы её решали Вы сами. Пока Вы не сформулируете такой алгоритм, компьютер Вам не поможет. Попытайтесь понять, как люди решают Вашу задачу без компьютера и повторите этот алгоритм. Возможно, получится неплохо.

теория расписаний делится на 2 больших и слабосвязанных раздела "machine
scheduling" и "timetabling" (оба переводятся как расписание и люди
путаются). Нас естественно интересует второй.

Для решения вводится понятие ограничений. Бывают жесткие ограничения (хотя
бы одна медсестра должна дежуриь в больнице в любой момент времени и главный
хирург желает делать операции после обеда) и мягкие (молодой врач хочет
дежурить меньше 5 раз в неделю). Жесткие условия должны быть выполнены, а за
нарушения мягких начисляются штрафные очки. Цель -- ето найти допустимое
решение минимизировав функцию штрафов. Оптимальное решение найти фактически
нереально в любой более-менее сложной задаче.

Как правило используются local search heuristics (e.g. tabu search, genetic
algoritms). Единственное что может заставить задуматься так ето то что на
практике я не слышал об успешном внедрении автоматизированных систем
составления расписаний, хотя слышал о большом количестве разработок в
университетах. Всегда оказывалось, что целовек с карандашом и ластиком
создает лучшее расписание.

Здравствуйте, mvg_first, Вы писали:

_>Буду благодарен за любую помощь по этому вопросу!

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