Добро пожаловать в форум, Guest  >>   Войти | Регистрация | Поиск | Правила | В избранное | Подписаться
Все форумы / Программирование Новый топик    Ответить
 Составление расписания  [new]
ferzmikk
Member

Откуда:
Сообщений: 1959
Здравствуйте!

Есть такая задачка. Нужно составить расписание для небольшого обучающего клуба.
+Структура входных условных данных
Есть n предметов:
Предмет_1. 2 раза в неделю (только в будни),через день, по 1 часу
Предмет_2. 2 раза в неделю (только в будни), через 2 дня, по 1 часу
Предмет_3. 3 раза в неделю (в будни + сб.)
...
Предмет_n

Есть m залов:
Зал_1. Площадь s1 кв. м. Вместимость 30 чел.
Зал_2. Площадь s2 кв. м. Вместимость 40 чел
Зал_3. Площадь s3 кв. м. Вместимость 20 чел. Присутствует кондионер, равномерно по залу распределяет температуру.
...
Зал_m

Есть k потребителей:
Поребитель_1. Собирается ходить на Предмет_1 (раньше не ходил). Удобно в пн, ср. с 19:00 - 21:00
Поребитель_2. Собирается ходить на Предмет_1 (раньше ходил) и на Предмет_2 (раньше не ходил). Удобно в пн, ср.
Поребитель_3. Собирается ходить на Предмет_1 (раньше ходил) и на Предмет_2 (раньше не ходил). На Предмет_1 удобно в пн, ср., а на Предмет2 в вт. и чт.
Поребитель_4. Собирается ходить на Предмет_2 (раньше ходил). Удобно в пн, ср.
Поребитель_5. Собирается ходить на Предмет_3 (раньше ходил). Удобно в пн, ср. Но в пн. намного удобнее, чем в ср.
Поребитель_6. Собирается ходить на Предмет_2 (раньше не ходил). Удобно в в сб и вс.
Поребитель_7. Собирается ходить на Предмет_1 (раньше ходил) или на Предмет_2 (раньше не ходил). Удобно в будни.
...
Потребитель_k

Есть l преподователей:
Преподаватель_1. Может вести Предмет_1 и Предмет_2
Преподаватель_2. Может вести Предмет_1, так как опыт большой. И может вести Предмет_3, имеет небольшой пыт.
Преподаватель_3. Может вести Предмет_2. Только в сб.
...
Преподаватель_l
Нужно составить оптимальное расписание, чтобы удовлетворять пожелания многим клиентам. Накидал пока такую структуру данных. Можно что то добавить или убрать лишнее. Например, добавить шкалу лайкерта для потребителей по параметру в какие дни удобно, и по каждому дню такая шкала
- Смогу;
- Скорей всего смогу придти;
- И да, и нет (нейтрально, когда как)
- Скорее не смогу
- Не смогу
- Затрудняюсь ответить
Шкалу можно растянуть. Вот категория "Затрудняюсь ответить" сложно будет обрабатывать, учитывая что могут быть еще и missing values.

Скажите,
1. Правильно понимаю, что это задача решается с помощью нейронных сетей?
2. Для такой задачи какая должна быть структура данных? Что надо еще учесть? Нужна ли шкала Лайкерта?
3. Скиньте, пожалуйста, литературу, где подробно описываются алгоритмы для решения данной задачи. Или ссылки на статьи.
4. Есть ли готовые программы, библиотеки решающие такую задачу?
18 сен 19, 14:44    [21973277]     Ответить | Цитировать Сообщить модератору
 Re: Составление расписания  [new]
exp98
Member

Откуда:
Сообщений: 1846
ferzmikk,
к постановке вопроса.

Вообще-то фраза вот такая
"удовлетворять пожелания многим клиентам" -
требует формализации, коль скоро речь идёт об "оптимальности".

Удовлетворять можно по-разному: полностью, частично, .... вааще не - это по линейной шкале. Вообще в жизни всегда есть место зависти, в т.ч. и среди преподов. В условиях этого не предусмотрено, а значит в реале обшая неудовлетворённость может сильно измениться после решения, и зачем тогда мучиться и считать?

"многим клиентам" - насколько многим? а остальным? что лучше, 10 счастливых + 10 озлобившихся или 20 одинаково НЕДОудовлетворённых?..

По общей задаче "расписаний",
ну нету хорошего решения. Это как есть транспортная задача, и есть задачИ трансп-го типа, и есть на них похожие.

Конкретных рекомендаций не даю, т.к. расписаниями не занимался.
Однако, что вы все так тянетесь к нервосеткам? чтобы не прогать самому?
Конкретно сетки (если в них специально не предусмотрено иного) решают задачу ЛОКАЛЬНОЙ оптимизации. Так что имхо многие методы лок-ной опт-ции способны решать те же задачи.

Кроме того, т.н. "шкалу лайкерта" напоминает нечёткую логику, а значит и методы нечёткой логики годятся.
18 сен 19, 17:19    [21973446]     Ответить | Цитировать Сообщить модератору
 Re: Составление расписания  [new]
vas0
Member

Откуда: Таможенный союз (Россия, Казахстан)
Сообщений: 1288
ferzmikk,

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

Посмотри в эту сторону, может поможет. Правда теория не сказать что из простых.
18 сен 19, 21:19    [21973646]     Ответить | Цитировать Сообщить модератору
 Re: Составление расписания  [new]
Dima T
Member

Откуда:
Сообщений: 14096
Задача составления расписания
19 сен 19, 07:16    [21973796]     Ответить | Цитировать Сообщить модератору
 Re: Составление расписания  [new]
Dimitry Sibiryakov
Member

Откуда:
Сообщений: 48641
vas0
По моему задача расписания подходит для решения симплекс методом. Правда ХЗ почему этого так не делают.

Потому что симплекс-метод работает только с плоской целевой функцией и линейными ограничениями. В таких условиях решение всегда лежит в углу, то бишь на пересечении целевой функции и одного-двух ограничений. У расписания целевая функция дискретна, как и ограничения. Так что нормально там способен работать разве что полный перебор.
19 сен 19, 13:42    [21974227]     Ответить | Цитировать Сообщить модератору
 Re: Составление расписания  [new]
ferzmikk
Member

Откуда:
Сообщений: 1959
exp98
к постановке вопроса.

Вообще-то фраза вот такая
"удовлетворять пожелания многим клиентам" -
требует формализации, коль скоро речь идёт об "оптимальности".
Имеется ввиду составить такое расписание, чтобы как можно по возможности посещали наибольшее количество клиентов учитывая их пожелания (например, по времени)
Удовлетворять можно по-разному: полностью, частично, .... вааще не - это по линейной шкале. Вообще в жизни всегда есть место зависти, в т.ч. и среди преподов. В условиях этого не предусмотрено, а значит в реале обшая неудовлетворённость может сильно измениться после решения, и зачем тогда мучиться и считать?
"многим клиентам" - насколько многим? а остальным? что лучше, 10 счастливых + 10 озлобившихся или 20 одинаково НЕДОудовлетворённых?..
Какой то малый процент недовольных составленному расписанию останется. Поэтому надо стремится, чтобы расписание составлялось так, чтобы количество клиентов, которые не попадают составленному расписанию, стремилось к нулю.
По общей задаче "расписаний",
ну нету хорошего решения. Это как есть транспортная задача, и есть задачИ трансп-го типа, и есть на них похожие.
Получается, вариант 1 - это использовать транспортную задачу. Транспортная задача учитывает всю заданную структуру данных?
Конкретных рекомендаций не даю, т.к. расписаниями не занимался.
Однако, что вы все так тянетесь к нервосеткам?
Сейчас нейронные сети решают многие задачи.
чтобы не прогать самому?
Если используешь нейронные сети, то пишешь не мало кода, кроме случаев, когда используешь готовые библиотеки.
Конкретно сетки (если в них специально не предусмотрено иного) решают задачу ЛОКАЛЬНОЙ оптимизации. Так что имхо многие методы лок-ной опт-ции способны решать те же задачи.

Кроме того, т.н. "шкалу лайкерта" напоминает нечёткую логику, а значит и методы нечёткой логики годятся.
19 сен 19, 16:56    [21974484]     Ответить | Цитировать Сообщить модератору
 Re: Составление расписания  [new]
wst
Member

Откуда:
Сообщений: 206
Тут скорее не нейронками, а MCTS или отжигом/генетическим алгоритмом проще решать. Или взять питоний scipy.optimize (или питоний же hyperopt), определить пространство решений, функцию оценки на нем и перебрать готовые алгоритмы.
19 сен 19, 18:54    [21974633]     Ответить | Цитировать Сообщить модератору
 Re: Составление расписания  [new]
ferzmikk
Member

Откуда:
Сообщений: 1959
wst
MCTS
Это Метод Монте-Карло?
19 сен 19, 19:24    [21974652]     Ответить | Цитировать Сообщить модератору
 Re: Составление расписания  [new]
wst
Member

Откуда:
Сообщений: 206
ferzmikk
wst
MCTS
Это Метод Монте-Карло?
Он самый.
19 сен 19, 19:37    [21974666]     Ответить | Цитировать Сообщить модератору
 Re: Составление расписания  [new]
Dimitry Sibiryakov
Member

Откуда:
Сообщений: 48641
wst
Он самый.

Подходит для приближенных вычислений, но не для составления расписания. Прочие методы случайного поиска (или как нынче модно их называть "генетические алгоритмы") требуют гладкую целевую функцию, с дискретными - облом.
20 сен 19, 13:41    [21975267]     Ответить | Цитировать Сообщить модератору
 Re: Составление расписания  [new]
exp98
Member

Откуда:
Сообщений: 1846
ferzmikk, составь сперва ф-цию, к-рую оптимизировать, потом ограничения.
Коль скоро выбран путь задачи оптимизации, она может оказаться решаемой теоретически, хотя бы и очень кропотливо. Однажды давно у меня именно так и вышло.

Вопрос устойчивости обычно никого не волнует (из разработчиков). Однако не стоит надеяться, что немножко пошевелив входные данные или условия, получите похожий ответ. Тем более в дискретном случае. В реале это приведёт к ненужности расписания, поскольку (напрмер уволился препод) потом будут перекраивать по типу пасьянса - и это далеко от теоретической оптимальности, в итоге всё сведётся к методу проб и ошибок и последующих аналогий. Иначе бы в МГУ давно расписания считали бы на компах.
Впочем, для тренировки - в добрый путь.
20 сен 19, 18:54    [21975678]     Ответить | Цитировать Сообщить модератору
Все форумы / Программирование Ответить