Scale to maximise hardware utilisation with a fixed number of nodes

[skycaptain]

I'm stuck trying to find a solution for an issue and would appreciate any suggestions or guidance.

Let's say I have a system that puts jobs into three queues, where each queue defines different resource request limits to process the job (i.e., small, medium, large jobs). I have workers running on a Kubernetes cluster. For each queue I'm setting up one worker Deployment, where I'm defining the resource request limits.

The number of nodes is fixed in my cluster (8 nodes), so I want optimize the replica count of each of the three Deployments to maximize hardware utilization. I need to find a trigger metric for KEDA to scale the three ScaledObjects based on available hardware resources, number of jobs in the queue, and (for fairness) the waiting time in the queue.

ScaledJobs are not suitable for this use case since the worker bootup time is substantial. However, once a worker is running, it can process multiple jobs sequentially.

This problem reminds me of the bin packing or knapsack problem, but I haven't found a solution yet.

I appreciate any hints in the right direction.