algorithmscheduling# Resource allocation algorithm

- I have a set of J jobs that need to be completed.
- All jobs take different times to complete, but the time is known.
- I have a set of R resources.
- Each recourse R may have any number from 1 to 100 instances.
- A Job may need to use any number of resources R.
- A job may need to use multiple instances of a resource R but never more than the resource R has instances (if a resource only has 2 instances, a job will never need more than 2 instances).
- Once a job completes it returns all instances of all resources it used back into the pool for other jobs to use.
- A job cannot be preempted once started.
- As long as resources allow, there is no limit to the number of jobs that can simultaneously execute.
- This is not a directed graph problem, the jobs J may execute in any order as long as they can claim their resources.

My Goal: The optimal way to schedule the jobs to minimize run time and/or maximize resource utilization.

Solution

I'm not sure how good this idea is, but you could model this as an integer linear program, as follows (not tested)

Define some constants,

```
Use[j,i] = amount of resource i used by job j
Time[j] = length of job j
Capacity[i] = amount of resource i available
```

Define some variables,

```
x[j,t] = job j starts at time t
r[i,t] = amount of resource of type i used at time t
slot[t] = is time slot t used
```

The constraints are,

```
// every job must start exactly once
(1). for every j, sum[t](x[j,t]) = 1
// a resource can only be used up to its capacity
(2). r[i,t] <= Capacity[i]
// if a job is running, it uses resources
(3). r[i,t] = sum[j | s <= t && s + Time[j] >= t] (x[j,s] * Use[j,i])
// if a job is running, then the time slot is used
(4). slot[t] >= x[j,s] iff s <= t && s + Time[j] >= t
```

The third constraint means that if a job was started recently enough that it's still running, then its resource usage is added to the currently used resources. The fourth constraint means that if a job was started recently enough that it's still running, then this time slot is used.

The objective function is the weighted sum of slots, with higher weights for later slots, so that it prefers to fill the early slots. In theory the weights must increase exponentially to ensure using a later time slot is always worse than any configuration that uses only earlier time slots, but solvers don't like that and in practice you can probably get away with using slower growing weights.

You will need enough slots such that a solution exists, but preferably not too many more than you end up needing, so I suggest you start with a greedy solution to give you a hopefully non-trivial upper bound on the number of time slots (obviously there is also the sum of the lengths of all tasks).

There are many ways to get a greedy solution, for example just schedule the jobs one by one in the earliest time slot it will go. It may work better to order them by some measure of "hardness" and put the hard ones in first, for example you could give them a score based on how badly they use a resource up (say, the sum of `Use[j,i] / Capacity[i]`

, or maybe the maximum? who knows, try some things) and then order by that score in decreasing order.

As a bonus, you may not always have to solve the full ILP problem (which is NP-hard, so sometimes it can take a while), if you solve just the linear relaxation (allowing the variables to take fractional values, not just 0 or 1) you get a lower bound, and the approximate greedy solutions give upper bounds. If they are sufficiently close, you can skip the costly integer phase and take a greedy solution. In some cases this can even prove the greedy solution optimal, if the rounded-up objective from the linear relaxation is the same as the objective of the greedy solution.

- Uniformly randomly generate a vector of k unsigned ints that sums to N
- How to calculate the midpoints of each triangle edges of an icosahedron
- Identify connected subnetworks (R-igraph)
- Mapping elementwise Tuple Using Template Function
- Find the longest prefix for a table of tokenized strings
- Kalman Filter Prediction Implementation
- My ALV Tree balance factors calculate incorrectly
- Infix to postfix left one parentheses at the end when expression is fully enclosed
- C++ quick sort algorithm
- Merge Sort Function not working when size of vector is not 2^n
- Given an array a of n integers, and q queries, for each value from index l to index r, add x to the value
- Count mountain arrays
- Get the number of all possible combinations that give a certain product
- getting TLE in leetcode question 212- word search 2 using backtrcaking even after pruning, how do i optimize it more
- Maximizing the sum of Adjacent sum in an array
- Weighted random selection from array
- If f(n) = O(g(n)), is log(f(n)) = O(log(g(n))?
- Why is KNN slow with custom metric?
- Based on a condition, how to remove an item from the processed array and move it to another array?
- The simplest algorithm for poker hand evaluation
- Find longest repetitive sequence in a string
- Check if all elements in a list are identical
- Minimize sum of products of adjacent elements of an array
- Creating dijkstras algorithm and having issues in C language
- Sliding subarray beauty working on IDE but not on leetcode
- How to insert a new element into an array in C?
- Permutations without recursive function call
- Algorithms and Data structure
- python - prefix sum algorithm
- Converting a Person's Height from feet and inches to just inches C#