powered by simpleCommunicator - 2.0.49     © 2025 Programmizd 02
Форумы / Программирование [игнор отключен] [закрыт для гостей] / Составление расписания
11 сообщений из 11, страница 1 из 1
Составление расписания
    #39863343
ferzmikk
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Здравствуйте!

Есть такая задачка. Нужно составить расписание для небольшого обучающего клуба.
Структура входных условных данныхЕсть 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. Есть ли готовые программы, библиотеки решающие такую задачу?
...
Рейтинг: 0 / 0
Составление расписания
    #39863460
exp98
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
ferzmikk,
к постановке вопроса.

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

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

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

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

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

Кроме того, т.н. "шкалу лайкерта" напоминает нечёткую логику, а значит и методы нечёткой логики годятся.
...
Рейтинг: 0 / 0
Составление расписания
    #39863591
vas0
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
ferzmikk,

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

Посмотри в эту сторону, может поможет. Правда теория не сказать что из простых.
...
Рейтинг: 0 / 0
Составление расписания
    #39863661
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
...
Рейтинг: 0 / 0
Составление расписания
    #39863945
Dimitry Sibiryakov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
vas0По моему задача расписания подходит для решения симплекс методом. Правда ХЗ почему этого так не делают.
Потому что симплекс-метод работает только с плоской целевой функцией и линейными ограничениями. В таких условиях решение всегда лежит в углу, то бишь на пересечении целевой функции и одного-двух ограничений. У расписания целевая функция дискретна, как и ограничения. Так что нормально там способен работать разве что полный перебор.
...
Рейтинг: 0 / 0
Составление расписания
    #39864085
ferzmikk
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
exp98к постановке вопроса.

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

Кроме того, т.н. "шкалу лайкерта" напоминает нечёткую логику, а значит и методы нечёткой логики годятся.
...
Рейтинг: 0 / 0
Составление расписания
    #39864174
wst
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Тут скорее не нейронками, а MCTS или отжигом/генетическим алгоритмом проще решать. Или взять питоний scipy.optimize (или питоний же hyperopt), определить пространство решений, функцию оценки на нем и перебрать готовые алгоритмы.
...
Рейтинг: 0 / 0
Составление расписания
    #39864184
ferzmikk
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
wstMCTSЭто Метод Монте-Карло?
...
Рейтинг: 0 / 0
Составление расписания
    #39864195
wst
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
ferzmikkwstMCTSЭто Метод Монте-Карло?Он самый.
...
Рейтинг: 0 / 0
Составление расписания
    #39864602
Dimitry Sibiryakov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
wstОн самый.
Подходит для приближенных вычислений, но не для составления расписания. Прочие методы случайного поиска (или как нынче модно их называть "генетические алгоритмы") требуют гладкую целевую функцию, с дискретными - облом.
...
Рейтинг: 0 / 0
Составление расписания
    #39864822
exp98
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
ferzmikk, составь сперва ф-цию, к-рую оптимизировать, потом ограничения.
Коль скоро выбран путь задачи оптимизации, она может оказаться решаемой теоретически, хотя бы и очень кропотливо. Однажды давно у меня именно так и вышло.

Вопрос устойчивости обычно никого не волнует (из разработчиков). Однако не стоит надеяться, что немножко пошевелив входные данные или условия, получите похожий ответ. Тем более в дискретном случае. В реале это приведёт к ненужности расписания, поскольку (напрмер уволился препод) потом будут перекраивать по типу пасьянса - и это далеко от теоретической оптимальности, в итоге всё сведётся к методу проб и ошибок и последующих аналогий. Иначе бы в МГУ давно расписания считали бы на компах.
Впочем, для тренировки - в добрый путь.
...
Рейтинг: 0 / 0
11 сообщений из 11, страница 1 из 1
Форумы / Программирование [игнор отключен] [закрыт для гостей] / Составление расписания
Целевая тема:
Создать новую тему:
Автор:
Закрыть
Цитировать
Найденые пользователи ...
Разблокировать пользователей ...
Читали форум (0):
Пользователи онлайн (0):
x
x
Закрыть


Просмотр
0 / 0
Close
Debug Console [Select Text]