Как описать алгоритм для работы с очередями?

Question

[hinie]

есть несколько клиентов с разными затратами времени на обслуживание и несколько касс.

К примеру, время затраченное на покупки для трёх клиентов [ 10, 11, 12 ] и одна касса — значит, они потратят 10 + 11 + 12 = 33 минуты.

Если касс будет две для тех же трёх клиентов [ 10, 11, 12 ] то 10 + 11 для первой и 12 для второй. То есть в общем 21 минута (порядок не менять).

Как описать функцию, способную рассчитать затраченное время для любого количества касс и покупателей?

Comments

[Антон Шаманов]

почему 12? по твоей логике - 21-23 мин.

[dollar]

Если предположить, что каждый клиент - эгоист и выбирает наиболее короткую очередь, то всё просто. Правда, тогда стоит уточнить понятие "короткая" (по времени или по количеству человек, ибо другие клиенты могут не знать, сколько времени займёт обслуживание остальных).

[Антон Шаманов]

dollar, судя по тому, что время известно у него скорее что-то вроде записи по талонам(макдак, сбер и т.д.) т.ч. очередь не сменишь.

[mayton2019]

Непонятно что хочет автор. Расчет времени?

Мне кажется - тут нужно имитационное моделирование. Это - проще чем искать формулу.

[Wataru]

hinie,  что значит "порядок не менять"? Внутри кадой очереди пользователи идут в исходном порядке? Но по очередям можно распихивать как угодно? Например, первого и третьего в одну кассу, а второго и четвертого - во вторую?

[Сергей Соколов]

Не понятно, как должны клиенты распределяться по кассам. Это устанавливается каким-то правилом, или ищется оптимальный вариант?

В пример [10, 11, 12] в две кассы — почему именно первые 2 идут в первую, а 1 во вторую? А если были бы [ 100, 100, 1 ] – всё равно 200 в первую и 1 во вторую?

Answer 1

[Wataru]

Если вам надо минимизировать общее время обработки всех клиентов (максимальное время работы какой-то из касс), то это NP-полная задача. Даже упращенная версия лишь с двумя кассами, если числа в задаче могут быть очень большими - не решается без полного перебора или каких-то вырвиглазных мозгодробительных методов оптимизации типа метода отжига.

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

Answer 2

[Антон Шаманов]

находим среднее время обслуживания клиента: 10 + ((12-10) / 2) = 11мин. (min - 10, max - 12)
находим среднее кол-во человек в очереди: делим число клиентов на кол-во касс и получаем 3/2 = 2чел.(округляем до целого т.к. люди это не колбаса - их по полам не разрежешь).
перемножаем значения и получаем среднее время обслуживания очереди: 22мин.