1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
//! 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 time
//! * `p` - process time
//! * `q` - 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:
//! 1. First being that jobs ona a single machine cannot have their processing time shared simultaneously between processes.
//! 2. The readying time and quitting time can overlap.
//! 3. 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:
//!
//! <div align="center">
//!
//! |$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 |
//!
//! </div>
//!
//!
//! $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
//!
// cargo doc dark theme background color: #353535