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

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

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

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

Когда выполнился запрос с участниками X-Y, мы должны искать по X и по Y запросы, которые могут быть выполнены.
По X находим X-P, по Y находим Y-Q.
Какой взять на выполнение?
Если всегда брать по первому имени, не получится так, что много запросов ?-Y и запросы с Y-? , будут слишком долго сидеть в этом пуле?
Допустим решили взять X-P. Его надо удалить из списка X.
Но список P тоже надо просмотреть и удалить именно этот запрос

Оба. Потому что обе эти задачи просто ждали, когда освободятся участники.

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

По X находим P-X, по Y находим Y-P.
Запрос Y-P пришел раньше. Y что то передает P, потом запрос P что то передает Х Они и исполняться должны сначала Y-P, потом P-X. Оба взять не получится и там и там P.

Значит Р-Х пока что в пролёте, ищем дальше по списку для Х, с учётом того, что Р теперь занят.

А если бы вместо Y-P был Y-Х, то дальнейшего поиска по списку Х вообще не надо.

Но я так понял со слов автора топика, очередность выполнения действий для конкретного участника не особо важна. Иначе все получается даже проще:

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

- по завершении задачи А-В смотрим только начала списков для А и В. Там видим, например, А-С и В-Д, которые запускаем, только если С и Д свободны, а оные задачи находятся в голове списков для С и Д.

В этой схеме всё отстреливает за наше любимое О(1)

Всякие ситуации могут быть.
Завершился запрос А - Б.
В очереди у А: С-А (С свободно), у Б: Б-С и Б-Д (Д свободно)
Мы берем С-А, (Б-С уже нельзя взять) (а почему именно С-А, а не Б-С? может Б-С пришел раньше, но вынужден ждать), а Б-Д не возьмем, т.к весь список Б мы не просматриваем

Вообще, Очередь на 10_000 элементов просматривается (с выяснением свободны ли элементы ища их в Set) за 3-4мс.
Мое мнение, что если очередь сильно больше, то дело не во времени просмотра очереди. Значит запросов сильно больше, чем время их обработки, И оптимизировать надо не очередь, а обработку.

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

Согласен. Это так, на всякий случай - если вдруг возникнет очередь, чтобы не пришлось с ней возиться слишком долго.

Т.е при освобождении А и Б мы должны не только их очереди просматривать, но и какие то другие?