Work jobs in the order they were submitted within a partition key. This selects the next partition key that isn't locked. You could make it smarter to select a subset of the jobs checking for partition keys where all of the rows are still unlocked.

  SELECT
  * 
  FROM jobs 
  WHERE partition_key = (
    SELECT partition_key 
    FROM jobs 
    ORDER BY partition_key 
    LIMIT 1
    SKIP LOCKED
  )
  ORDER BY submitted_at
  FOR UPDATE SKIP LOCKED;