Expand description
This crate provides job/process scheduling optimization algorithms.
§A job or a process
A job or a process is described using three values:
r
- ready timep
- process timeq
- cooldown/quit time
r
- Time it takes for this process to become available form time 0
. For example after turning on a machine it may take some time for some of its features to become available due to a certain constraints. A trivial example is that of cooking, a grill or any other device that allows thermal treatment for given food needs to achieve a certain temperature otherwise it will not be effective.
p
- Time taken by the process itself. It is the time taken by the modeled mechanism itself to perform a given function. Following the cooking example it can be modeled as the actual time that a given food has to be cooked for on the grill.
q
- Time that it takes for the machine to clean-up/cooldown/quit after executing a given process. Again, following the cooking example it can be described as the time needed to clean-up after serving the cooked food.
C
- The final time when the machine finishes dealing with any part of the process/job.
§Scheduling problems
There exist two types of job scheduling problems. The first one being single-machine problem and the second being multi-machine problem. Each of them agrees with these assumptions:
- First being that jobs ona a single machine cannot have their processing time shared simultaneously between processes.
- The readying time and quitting time can overlap.
- The whole of the machines process end when the last job finishes.
An example set of jobs and their natural (from the 1 to $j$’th) arrangement:
$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 |
$C_{max}$ - being the maximum time out of all of the finishing times for all the jobs. It is therefore also the time at which the whole machine finishes work.
Here we can see the actual optimal arrangement for the same jobs, where the $C_{max}$ is minimized down to $50$:
§Single-machine problem
Meta-heuristic algorithms (giving fast but approximate answer):
- Schrage algorithm -
schrage
- Part Time Schrage (TBD)
Heuristic algorithms (giving slower but optimal answer):
- Carlier (TBD)
§Multi-machine problem
TBD