The scenario is something like this
- I have tasks that get requested, with a category and a priority
- For simplicity let's assume that rate of incoming tasks and completion is about the same, with some existing backlog of tasks
- Each category of tasks can only be completed at some certain rate
- Completion of tasks is handled out of the system, so we can assume that deciding to take on a certain task is equivalent to completing it
So I want some way of deciding which tasks to complete at a given time, given the existing tasks and their priorities, and the limits on completion within a certain category
One greedy algorithm would be to just organize each category by priority, and then at each decision point take in as many tasks as is allowed by that category's rate, but the problem with this is that if a lot of high priority tasks come in low priority tasks will just sit in the backlog, potentially forever.
I've looked at some scheduling concepts like round robin scheduling and multilevel priority queues, but they don't seem to fit what I want - tasks can't be paused/rescheduled as in round robin, and multi priority queues seems like it'd still have the problem of getting to low priority tasks (could just make the priorities more stratified, but then it's just back to the original problem with deciding how many tasks to take from each queue)
Any advice on what I should look into? Maybe it's a sort of "repeated knapsack" thing?