What algorithms are there for scheduling tasks

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?

What you can do is to add another parameter to your tasks, something that I would call dynamic priority delta. Or what is equivalent, you can implement some mechanism to increase or decrease the priority of each task on top of multilevel priority queues.

The basic idea is simple. "A process that waits too long in a lower-priority queue may be moved to a higher-priority queue. This form of aging prevents starvation.", reads section 5.3.6 of Operating Systems Concepts, seventh edition. For an extreme simple example, you can just increase priority level by one if a task has waited for an hour. Here is more excerpt from that book.

In general, a multilevel feedback-queue scheduler is defined by the following parameters:

• The number of queues
• The scheduling algorithm for each queue
• The method used to determine when to upgrade a process to a higher- priority queue
• The method used to determine when to demote a process to a lower- priority queue
• The method used to determine which queue a process will enter when that process needs service

The definition of a multilevel feedback-queue scheduler makes it the most general CPU-scheduling algorithm. It can be configured to match a specific system under design. Unfortunately, it is also the most complex algorithm, since defining the best scheduler requires some means by which to select values for all the parameters.