Waiting time is a kind of rank

Give every queued item a position, and let that position improve the longer the item sits. Someone who has been waiting all afternoon should not lose their place to a newcomer simply because the newcomer claimed a louder label.

This is the whole idea behind aging, and it needs no special infrastructure. Recompute the ordering when an item is taken, using how long it has waited as part of the comparison.

def position(item, now):
    waited = now - item["arrived"]
    return item["label"] + waited * item["gain_per_second"]

The gain per second is a written policy. It states how much waiting buys how much preference, and it should be reviewed rather than adjusted until the queue looks calm.

With a gain set properly, the guarantee becomes simple enough to state to a customer: work in the quiet lane still finishes, however busy the loud lane becomes.