Как запланировать задачи

Question

Существует автомойка, которая может обслуживать только 1 клиента за раз.Цель автомойки - привлечь как можно больше довольных клиентов, заставив их ждать в очереди наименьшее количество времени.Если клиенты могут быть обслужены менее чем за 15 минут, они радуются, менее чем за час - счастливы, от 1 до 3 часов - нейтрально и от 3 до 8 часов - сердиты.(Цель состоит в том, чтобы минимизировать злых людей и максимизировать счастливых людей).Единственным предостережением к этой проблеме является то, что на каждый автомобиль уходит разное количество времени на мойку и обслуживание, поэтому мы не всегда можем обслуживать по принципу «первым пришел - первым обслужен», учитывая нашу цель - максимально повысить эффективность обслуживания клиентов.Так это может выглядеть следующим образом:

Клиентская линия :

Клиент1) Задача: 6 минут (первое прибытие)

Клиент2) Задача: 3 минуты (второе прибытие)

Клиент3) Задача: 9 минут (3-е)

Клиент4) Задача: 4 минуты (4-е)

Сервисная линия :

Обслуживающий клиент 2, Обслуживающий клиент 1, Обслуживающий клиент 4, Обслуживающий клиент 3.

Таким образом, никто не ждал в очереди более 15 минут, прежде чем его обслуживали.,Я знаю, что должен использовать некоторую форму очереди приоритетов для реализации этого, но я честно знаю, как я должен отдавать приоритет различным клиентам.Я не могу отдавать предпочтение клиентам с наименьшим объемом необходимой работы, поскольку они могут быть последним клиентом, который, например, прибыл (другие очень рассердятся), и я не могу просто сравнивать по времени, поскольку у первого парня может быть задача, которая требуетцелый день. Как бы я сравнил этих клиентов друг с другом с целью максимизации счастья?

Приветствия

Answer 1

Это похоже на заказ звонков в колл-центр.Это становится более интересным, когда у вас есть покупатели золота и серебра.В любом случае:

У каждого автомобиля есть readyTime (самое раннее время, которое можно помыть, поэтому время прибытия - которое может быть разным для каждого автомобиля) и dueTime (в тот момент, когда клиент злится, поэтому3 часа после readyTime).

Затем используйте решатель ограничений (например, OptaPlanner ), чтобы определить порядок машин (*).Заказ автомобилей (который является подлинной переменной планирования) подразумевает startWashingTime каждого автомобиля (который является теневой переменной), потому что в вашем примере, если клиент 1 заказан после клиента 2 и если мы начнем в 08:00, мы можем сделать вывод, что startWashingTime клиента 1 равен 08: 03.

Тогда endWashingTime равно startWashingTime + washingDuration.

Тогда нужно просто добавить 2 ограничения и позволить решателюsolve() it:

• endWashingTime должно быть меньше, чем dueTime, это жесткое ограничение.Это не должно иметь злых клиентов.
• endWashingTime должно быть меньше, чем startTime плюс 15 минут, это мягкое ограничение.Это сделано для максимального удовлетворения клиентов.

(*) Эта проблема является NP-полной или NP-сложной, потому что вы можете решить ее как проблему с рюкзаком.На практике это означает: вы не можете написать алгоритм для него, который масштабируется и находит оптимальное решение в разумные сроки.Но решатель ограничений может приблизить вас.