[Alexandroppolus]

Предполагаем, что pool организован как Map (<id> => <запрос>) c инкрементными идентификаторами.
Вводится дополнительная структура данных (Map вполне подойдет). Ключом являются имена участников, которые в настоящее время стоят в очереди. Значениями - список (Set наверно подойдет) идентификаторов запросов в очереди с этим участником.

Я бы чуть по-другому сделал:
pool - это Map, где ключём будет участник, а значением - двусвязный список задач, связанных с участником. Большой общий список всё равно не нужен. Когда приходит новая задача, она просто добавляется в списки к обоим участникам (если не может выполниться прямо сейчас, т.е. кто-то из двух занят).

Когда участников много (всего М), то оптимизация очень хорошая: если задачи распределены более-менее равномерно, то имеем дело со списками, которые меньше полного списка в М раз. Ну а если оказалось, что почти все задачи завязаны на какого-то одного участника Х, то по нему выстроится длинный список, зато все прочие будут почти всегда свободны, и нам не придется долго искать задачу в этом длинном списке.

Долгие проходы по списку будут, но в редких случаях.

Итого: довольно простая оптимизация, которая охватывает почти все кейсы.