Expand description
Implements Schrage and Part Time Schrage algorithms.
The Schrage algorithm is a meta-heuristic algorithm that tries to optimize scheduling of different processes. Using the Graham’s notation the problem can be written as: $$ 1|r_{j}, q_{j}|C_{max} $$
It tried to optimize a set of jobs using the greedy-algorithm method by
iterating over the jobs and time and first choosing jobs that are available at the moment given their readiness time (r) and choosing the one with the highest value of cooldown time (q).
| $j$ | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
|---|---|---|---|---|---|---|---|
| $r_j$ | 10 | 13 | 11 | 20 | 30 | 0 | 30 |
| $p_j$ | 5 | 6 | 7 | 4 | 3 | 6 | 2 |
| $q_j$ | 7 | 26 | 24 | 21 | 8 | 17 | 0 |
Natural arrangement of jobs:
Schrage sub-optimized arrangement gives the value of $53$ for the $C_{max}$ value:
Compared to the $50$ which is the optimal solution to this particular set of jobs:
Functions§
- part_
time_ schrage - Part time Schrage algorithm.
- schrage
- Schrage algorithm.