Составление графика вахтования

[worm2]

У одного из моих знакомых жизненная задача всплыла:

Нужно составить годовой график вахтования сотрудников. Нам дают места в самолете, который летает с определённой периодичностью в 4 города, туда и обратно (каждый сотрудник, разумеется, летает в свой город), и нужно людей рассадить так, чтобы:
1) Вахты были примерно месяц на месяц.
2) Люди были на каждом объекте, т.е. чтоб не было так что на каком-то объекте нет людей (каждый привязан к какому-то объекту).
3) Чтоб в общаге мест хватало (т.к. некоторые живут в общаге на одних и тех же местах).

Я затруднился отнести эту задачу к какому-то известному мне классу. Конечно, это похоже на составление расписаний в учебных заведениях, но и своя специфика, безусловно имеется.
Задача мне показалась очень сложной, полный перебор не проходит никак. К тому же осложняется нечёткостью. Если решения не существует в формальной постановке, желательно получить "меньшее из зол", т.е. решение, формально не удовлетворяющее условиям, но оставляющее минимальные негативные последствия.

Не знаком ли кто-нибудь с такой (или похожей) постановкой задачи, методами решения либо с программными продуктами для её решения?

[maxal]

Похоже, что задачу можно легко формализовать в терминах целочисленного (а точнее даже булева) программирования, если ввести (как обычно в подобных задачах) булевы переменные $x_{ij}=0$ или $1$ в зависимости от присутствия человека номер $i$ на вахте номер $j$ (под "вахтой" я понимаю пару: объект и период времени).
Тогда постоянное присутствие кого-то на определенном объекте в определенный период будет задаваться требованием неравенства нулю суммы $x_{ij}$ по всем $i$ для каждого фиксированного $j$. Впрочем и достаточность мест в общаге будет задаваться похожим условием, разве что вместо $x_{ij}$ возможно надо будет суммировать $(1-x_{ij})$ и т.д. и т.п.

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

[worm2]

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

[dmd]

Вот здесь ставят такие задачи и пытаются решать

[worm2]

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