Алгоритм поиска наилучшего возможного времени

Question

Вот мой сценарий,

Я управляю массажным местом, которое предлагает различные виды массажа. Скажем, 30-минутный массаж, 45-минутный массаж, 1-часовой массаж и т. Д. У меня есть 50 комнат, 100 сотрудников и 30 единиц оборудования. Когда клиент записывается на сеанс массажа, на прием требуется 1 комната, 1 сотрудник и 1 единица оборудования. быть доступным.

Какой хороший алгоритм поиска доступных ресурсов для 10 гостей на данный день

Ресурсы

Номер - 50

Персонал - 100

Оборудование - 30

Рабочее время: с 9:00 до 18:00.

Часы работы персонала: с 9:00 до 18:00.

Количество гостей: 10

Услуга

5 гостей (1 час массажа)

3 гостя - (45 минут массажа)

2 гостя - (1 час массажа).

Они приходят в одно и то же время. Предположим, что в этот день нет другой встречи

Какой лучший способ получить ::

• 10 лучших результатов - Самый быстрый поиск, который удовлетворяет всем условиям, получает 10 лучших результатов. Первая десятка определяется самым ранним доступным временем. 9 - 11 утра - лучший результат. 9 - 5 вечера не очень хорошо.

• Исчерпывающий поиск (Найти все комбинации) - все наборы - Каждая возможная комбинация

• Первое доступное выполнено (возвращает только первое совпадение) - остановка после выполнения одного из условий

Буду признателен за вашу помощь.

Спасибо Ник

Answer 1

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

Если проблема начинает увеличиваться, ищите более специализированное программное обеспечение. Нужно искать «оптимизацию на основе ограничений» и «программирование на основе ограничений».

например. инструмент ECLIPSe - это среда программирования ограничений с открытым исходным кодом. Вы можете найти несколько примеров на http://eclipseclp.org/examples/index.html. Один хороший пример, который вы можете найти, это проблема SEND + MORE = MONEY. В этой задаче у вас есть следующее уравнение:

    S E N D
+   M O R E
-----------
= M O N E Y

Замените каждую букву цифрой, чтобы сумма была правильной. Это также показывает, что, хотя вы можете решить эту грубую силу, существуют более разумные способы решения этой проблемы (см. http://eclipseclp.org/examples/sendmore.pl.txt).

Answer 2

Просто идея найти решение:

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

Существует несколько приемов для повышения производительности CSP, таких как прямая проверка, создание DAG, а затем топологическая сортировка и т. Д. *

Просто дайте мне знать, если вам нужна дополнительная информация о CSP:)

Answer 3

Во-первых, кажется, что количество сотрудников, помещений и оборудования не имеет значения.Похоже, вас волнует только то, какое из них является наименьшим.Это ваш инвентарь.Таким образом, в вашем случае инвентарь = 30.

Далее, похоже, что вы можете одновременно обслуживать всех 10 человек в течение первого часа работы.Фактически, вы можете одновременно обслуживать 30 человек.

Таким образом, для этого не требуется никакого алгоритма, это статическое решение.Если вы прислушаетесь к совету @Mario The Spoon и взвесите различные сеансы массажа с соответствующей прибылью, тогда вы можете начать оптимизацию, если у вас одновременно более 30 клиентов.