Actually most of the prioritization could be implemented through additional DB. With SQS in most cases you need persistent reflection of job to keep its status, process times, results. You can put to queue only few items that are highest priority to guarantee that workers are busy next 10-30 minutes.
Was hoping to avoid having "side car" infrastructure for this, but I don't think I can escape it :)