Рабочие R(ID_R IDENTITY) выполняют заявки на обслуживание Z(ID_Z IDENTITY, ID_K, ID_R), поступающие от клиентов K(ID_K).
Кажется, так: R<->>Z<<->K.

Необходимо распределить заявки Z между рабочими R, так чтобы все заявки каждого клиента K выполнял только один рабочий и количество заявок у каждого рабочего оказалась бы максимально одинаковым.

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

А почему эту задачу надо решать именно на SQL? 

Речь идёт о больших массивах данных. Немало информации ждёт обработки уже сейчас. У меня прямой перебор для такой задачи не пошёл: тормозит очень.
А "нужно" или "не нужно" - жду предложений по реализации.

Ну давай изобретать "кривой перебор". Само собой, раз нужна скорость, то оптимум не гарантируем.

У нас есть (в таблицах, и с соотв. индексами): 
список работников и текущее количество работ у каждого из них
список клиентов и количество заявок от каждого из них

Считается, что нет клиентов, часть заявок которых уже распределена - иначе нераспределённые заявки клиента распределяем тому, у кого уже есть заявки от этого клиента.

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

PS. Реализация этого барахла в рамках SQL мне кажется не очень разумной. Я бы вытащил это всё на клиента, обработал и в ходе обработки клал результаты расчёта во временную таблицу, которую использовал бы для апдейта основной одним запросом. Единственный минус при этом - начальный трафик.

Это сообщение отредактировал(а) Akina - 31.3.2010, 18:01

Такой вариант возможен. Единственное что смущает, - изначальное исключение рабочих, у которых заявок выше крыши (к примеру, у одного 1 заявка, а у другого - 1e6, а средняя температура по больнице - 36,6 гр. Ц.). Пусть бы уж поделились с кем-то своим счастьем, а то по этому алгоритму при очередном выяснении "оптимума" этот "оптимум" стремится к нулю и каждый последующий рабочий не может получить заявок больше, чем предыдущий. Ещё в задаче смущают случаи, когда у одного клиента может быть всего одна заявка, а у другого - 1e6... Вобщем, пока к окончательному решению не пришёл.

Это сообщение отредактировал(а) tishaishii - 3.4.2010, 10:22

Извини, задачи перераспределения ранее распределённых заявок не ставилось.

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

Задача любопытная, но


Как между собой вяжутся эти две вещи?

А такая, что такое тоже может быть.

tishaishii, моя логика пасует тут :(
10 заявок в день, 1е6 это 100к дней. Мы столько не живем.

Более того, как собирается обеспечивать "максимальную равность", если один клиент может иметь более половины заявок в системе?

Да даже одна заявка к десяти (кому охота делать в 10 раз больше).
Дело в равном распределении заявок.

Независимо ни отчего поиск наиболее справедливого распределения (вернее его точного решения) мне представляется задачей полного перебора... а потому уход от него всегда даёт вероятность нахождения неоптимального решения. В этом случае обычный жадный алгоритм вполне подойдёт.

Да, Akina, пока я пришёл к тому, что согласен с твоим алгоритмом.