I think you are describing a situation where you have two "priority queues" - one for the jobs and one for the workers. The naive approach is to take the top priority job and the top priority worker and try to pair them. But of course this fails when the worker is unable to execute the job.
To fix this I'd suggest first taking the top priority job and then iterating over all the workers in order of descending priority until you find one that can process that job. If none of the workers can process the job then take the second highest priority job, and so on. So effectively you have nested loops, something like this:
def getNextWorkerAndJobPair():
for job in sorted(jobs, key=priority, reverse=True):
for worker in sorted(workers, key=priority, reverse=True):
if worker.can_process(job):
return (worker, job)
The above example sorts the data unnecessarily many times though. To avoid this it would be best to store the data already in sorted order. As for what data structures to use, I'm not really sure what the best is. Ideally you would want O(log n) inserts and removals and to be able to iterate over the collection in sorted order in O(n) time. I think PriorityQueue meets the first of those requirements but not the second. I imagine that sortedlist from the blist package would work, but I haven't tried it myself and the webpage isn't specific about the performance guarantees that this class offers.
The way I have suggested to iterate over the jobs first and then over the workers in the inner loop is not the only approach you could take. You could also reverse the order of the loops so that you choose the highest priority worker first and then try to find a job for it. Or you could find the valid (job, worker) pair that has the maximum value of f(priority_job, priority_worker) for some function f (for example just add the priorities).