proc_opt/schrage/
mod.rs

1//! Implements Schrage and Part Time Schrage algorithms.
2//!
3//! The Schrage algorithm is a meta-heuristic algorithm that tries to optimize
4//! scheduling of different processes. Using the Graham's notation the problem
5//! can be written as:
6//! $$ 1|r_{j}, q_{j}|C_{max} $$
7//!
8//! It tried to optimize a set of jobs using the greedy-algorithm method by
9//! 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`).
10//!
11//! <div align="center">
12//!
13//! |$j$  |1    |2    |3    |4    |5    |6    |7    |
14//! |:---:|:---:|:---:|:---:|:---:|:---:|:---:|:---:|
15//! |$r_j$|10   |13   |11   |20   |30   |0    |30   |
16//! |$p_j$|5    |6    |7    |4    |3    |6    |2    |
17//! |$q_j$|7    |26   |24   |21   |8    |17   |0    |
18//!
19//! </div>
20//!
21//! Natural arrangement of jobs:
22//!
23#![doc=include_str!("../../img/schrage_natural.svg")]
24//!
25//! Schrage sub-optimized arrangement gives the value of $53$ for the $C_{max}$ value:
26//!
27#![doc=include_str!("../../img/Schrage.svg")]
28//!
29//! Compared to the $50$ which is the optimal solution to this particular set of jobs:
30//!
31#![doc=include_str!("../../img/optimal.svg")]
32//!
33//!
34//!
35//!
36//!
37//!
38
39use crate::jobs::{Job, JobList, SchrageJobTable};
40use std::{cmp, vec};
41
42/// Schrage algorithm.
43///
44/// # Arguments
45///
46/// * `jobs`: A vector of jobs.
47///
48/// returns: JobList
49/// Returns a JobList that is sorted in the sub-optimized arrangement.
50///
51/// # Examples
52///
53/// ```rust
54/// use proc_opt::jobs::{JobList, Job, SchrageJobTable};
55/// use proc_opt::schrage::schrage;
56/// let expected_result = SchrageJobTable::new(JobList {
57///     jobs: vec![
58///         Job::new(0, 6, 17),  // 6
59///         Job::new(10, 5, 7),  // 1
60///         Job::new(13, 6, 26), // 2
61///         Job::new(11, 7, 24), // 3
62///         Job::new(20, 4, 21), // 4
63///         Job::new(30, 3, 8),  // 5
64///         Job::new(30, 2, 0),  // 7
65///     ],
66/// });
67/// let js = SchrageJobTable::new(JobList {
68///     jobs: vec![
69///         Job::new(10, 5, 7),  // 1
70///         Job::new(13, 6, 26), // 2
71///         Job::new(11, 7, 24), // 3
72///         Job::new(20, 4, 21), // 4
73///         Job::new(30, 3, 8),  // 5
74///         Job::new(0, 6, 17),  // 6
75///         Job::new(30, 2, 0),  // 7
76///     ],
77/// });
78/// let result = schrage(&js.job_list);
79/// assert_eq!(result.job_list, expected_result.job_list);
80/// assert_eq!(result.c_max(), 53);
81/// ```
82pub fn schrage(jobs: &JobList) -> SchrageJobTable {
83    // N
84    // A list of jobs to be completed
85    let mut shortest_delivery_jobs = JobList::new(jobs.sorted_by_delivery_time());
86    // G
87    // A list of jobs that in a current moment are ready to run
88    let mut ready_to_run = JobList::new(Vec::new());
89    // Time tracking variable
90    let mut t: u32 = 0;
91    // The final sequence in which the jobs should be run
92    let mut pi: JobList = JobList::new(Vec::new());
93
94    // Iterate over all of the jobs until we ran out of them
95    while !shortest_delivery_jobs.jobs.is_empty() || !ready_to_run.jobs.is_empty() {
96        // Find all jobs that are available
97        while !shortest_delivery_jobs.jobs.is_empty()
98            && shortest_delivery_jobs.jobs[0].delivery_time <= t
99        {
100            ready_to_run
101                .jobs
102                .append(&mut vec![shortest_delivery_jobs.jobs[0]]);
103            shortest_delivery_jobs.jobs.remove(0);
104        }
105        // If there are jobs that are ready to run schedule them
106        if !ready_to_run.jobs.is_empty() {
107            let vec_by_processing_time = JobList {
108                jobs: ready_to_run.sorted_by_processing_time(),
109            };
110            let reversed: JobList = JobList {
111                jobs: vec_by_processing_time.jobs.into_iter().rev().collect(),
112            };
113            let cooldown_times: Vec<Job> = reversed.sorted_by_cooldown_time();
114
115            let max_cooldown_time = cooldown_times.last().unwrap();
116            let position = ready_to_run
117                .jobs
118                .iter()
119                .position(|&n| &n == max_cooldown_time)
120                .unwrap();
121            ready_to_run.jobs.remove(position);
122            // Add a job to the final sequence
123            pi.jobs.push(*max_cooldown_time);
124            t += max_cooldown_time.processing_time;
125        } else {
126            // If there aren't any jobs that can be run,
127            // skip to when the nearest job is available
128            t = shortest_delivery_jobs.jobs[0].delivery_time;
129        }
130    }
131    SchrageJobTable { job_list: pi }
132}
133
134/// Part time Schrage algorithm.
135///
136/// # Panics
137///
138/// Panics if empty job list.
139///
140/// # Example
141///
142/// ```
143/// use proc_opt::jobs::{JobList, Job, SchrageJobTable};
144/// use proc_opt::schrage::part_time_schrage;
145/// let js = JobList::new(vec![
146///     Job::new(0, 27, 78),
147///     Job::new(140, 7, 67),
148///     Job::new(14, 36, 54),
149///     Job::new(133, 76, 5),
150/// ]);
151/// let result = part_time_schrage(&js);
152/// assert_eq!(result, 221)
153/// ```
154pub fn part_time_schrage(jobs: &JobList) -> u32 {
155    // N
156    let mut shortest_delivery_jobs = JobList::new(jobs.sorted_by_delivery_time());
157    // G
158    let mut ready_to_run = JobList::new(Vec::new());
159    let mut current_job = Job::new(0, 0, 0);
160    let mut t: u32 = 0;
161    let mut c_max: u32 = 0;
162    let mut pi: JobList = JobList { jobs: Vec::new() };
163
164    while !shortest_delivery_jobs.jobs.is_empty() || !ready_to_run.jobs.is_empty() {
165        while !shortest_delivery_jobs.jobs.is_empty()
166            && shortest_delivery_jobs.jobs[0].delivery_time <= t
167        {
168            ready_to_run
169                .jobs
170                .append(&mut vec![shortest_delivery_jobs.jobs[0]]);
171            let next_job = shortest_delivery_jobs.jobs.remove(0);
172
173            if next_job.cooldown_time > current_job.cooldown_time {
174                current_job.processing_time = t - next_job.delivery_time;
175                t = next_job.delivery_time;
176
177                if current_job.processing_time > 0 {
178                    ready_to_run.jobs.append(&mut vec![current_job]);
179                    ready_to_run.jobs = ready_to_run.sorted_by_delivery_time().clone();
180                }
181            }
182        }
183
184        if !ready_to_run.jobs.is_empty() {
185            let cooldown_times = ready_to_run.sorted_by_cooldown_time();
186            let max_cooldown_time = cooldown_times.last().unwrap();
187            let position = ready_to_run
188                .jobs
189                .iter()
190                .position(|&n| n.cooldown_time == max_cooldown_time.cooldown_time)
191                .unwrap();
192            current_job = ready_to_run.jobs.remove(position);
193
194            // Add a job to the final sequence
195            pi.jobs.push(*max_cooldown_time);
196            t += max_cooldown_time.processing_time;
197            c_max = cmp::max(t + max_cooldown_time.cooldown_time, c_max)
198        } else {
199            t = shortest_delivery_jobs.jobs[0].delivery_time;
200        }
201    }
202    c_max
203}
204
205#[cfg(test)]
206mod tests {
207    use crate::jobs::{Job, JobList};
208
209    use super::*;
210
211    #[test]
212    fn test_schrage_ex1() {
213        let expected_result = SchrageJobTable::new(JobList {
214            jobs: vec![
215                Job::new(0, 6, 17),  // 6
216                Job::new(10, 5, 7),  // 1
217                Job::new(13, 6, 26), // 2
218                Job::new(11, 7, 24), // 3
219                Job::new(20, 4, 21), // 4
220                Job::new(30, 3, 8),  // 5
221                Job::new(30, 2, 0),  // 7
222            ],
223        });
224        let js = SchrageJobTable::new(JobList {
225            jobs: vec![
226                Job::new(10, 5, 7),  // 1
227                Job::new(13, 6, 26), // 2
228                Job::new(11, 7, 24), // 3
229                Job::new(20, 4, 21), // 4
230                Job::new(30, 3, 8),  // 5
231                Job::new(0, 6, 17),  // 6
232                Job::new(30, 2, 0),  // 7
233            ],
234        });
235        let result = schrage(&js.job_list);
236        assert_eq!(result.job_list, expected_result.job_list);
237        assert_eq!(result.c_max(), 53);
238    }
239
240    #[test]
241    fn test_schrage_ex2() {
242        let expected_result = SchrageJobTable::new(JobList {
243            jobs: vec![
244                Job::new(1, 5, 9), // 1
245                Job::new(3, 6, 8), // 5
246                Job::new(1, 4, 6), // 3
247                Job::new(4, 5, 4), // 2
248                Job::new(7, 3, 3), // 4
249                Job::new(4, 7, 1), // 6
250            ],
251        });
252        let js = SchrageJobTable::new(JobList {
253            jobs: vec![
254                Job::new(1, 5, 9), // 1
255                Job::new(4, 5, 4), // 2
256                Job::new(1, 4, 6), // 3
257                Job::new(7, 3, 3), // 4
258                Job::new(3, 6, 8), // 5
259                Job::new(4, 7, 1), // 6
260            ],
261        });
262        let result = schrage(&js.job_list);
263        assert_eq!(result.job_list, expected_result.job_list);
264        assert_eq!(result.c_max(), 32);
265    }
266
267    #[test]
268    fn test_schrage_ex3() {
269        let expected_result = SchrageJobTable::new(JobList {
270            jobs: vec![
271                Job::new(15, 86, 700),  // 5
272                Job::new(51, 52, 403),  // 7
273                Job::new(144, 73, 536), // 6
274                Job::new(183, 17, 641), // 9
275                Job::new(226, 5, 629),  // 15
276                Job::new(162, 80, 575), // 16
277                Job::new(103, 68, 470), // 2
278                Job::new(394, 34, 400), // 4
279                Job::new(35, 37, 386),  // 13
280                Job::new(39, 38, 340),  // 3
281                Job::new(162, 52, 241), // 1
282                Job::new(556, 23, 79),  // 18
283                Job::new(567, 71, 618), // 14
284                Job::new(588, 45, 632), // 17
285                Job::new(598, 45, 200), // 20
286                Job::new(728, 18, 640), // 10
287                Job::new(715, 8, 93),   // 19
288                Job::new(667, 80, 92),  // 11
289                Job::new(57, 21, 76),   // 12
290                Job::new(233, 68, 23),  // 8
291            ],
292        });
293        let js = SchrageJobTable::new(JobList {
294            jobs: vec![
295                Job::new(162, 52, 241), // 1
296                Job::new(103, 68, 470), // 2
297                Job::new(39, 38, 340),  // 3
298                Job::new(394, 34, 400), // 4
299                Job::new(15, 86, 700),  // 5
300                Job::new(144, 73, 536), // 6
301                Job::new(51, 52, 403),  // 7
302                Job::new(233, 68, 23),  // 8
303                Job::new(183, 17, 641), // 9
304                Job::new(728, 18, 640), // 10
305                Job::new(667, 80, 92),  // 11
306                Job::new(57, 21, 76),   // 12
307                Job::new(35, 37, 386),  // 13
308                Job::new(567, 71, 618), // 14
309                Job::new(226, 5, 629),  // 15
310                Job::new(162, 80, 575), // 16
311                Job::new(588, 45, 632), // 17
312                Job::new(556, 23, 79),  // 18
313                Job::new(715, 8, 93),   // 19
314                Job::new(598, 45, 200), // 20
315            ],
316        });
317        let result = schrage(&js.job_list);
318        assert_eq!(result.job_list, expected_result.job_list);
319        assert_eq!(result.c_max(), 1399);
320    }
321
322    #[test]
323    fn test_schrage_ex4() {
324        let expected_result = SchrageJobTable::new(JobList {
325            jobs: vec![
326                Job::new(2, 20, 88),   // 8
327                Job::new(5, 14, 125),  // 4
328                Job::new(8, 16, 114),  // 5
329                Job::new(9, 28, 94),   // 10
330                Job::new(70, 4, 93),   // 2
331                Job::new(71, 7, 71),   // 6
332                Job::new(52, 1, 56),   // 1
333                Job::new(52, 20, 56),  // 9
334                Job::new(112, 22, 79), // 3
335                Job::new(90, 2, 13),   // 7
336            ],
337        });
338        let js = SchrageJobTable::new(JobList {
339            jobs: vec![
340                Job::new(52, 1, 56),   // 1
341                Job::new(70, 4, 93),   // 2
342                Job::new(112, 22, 79), // 3
343                Job::new(5, 14, 125),  // 4
344                Job::new(8, 16, 114),  // 5
345                Job::new(71, 7, 71),   // 6
346                Job::new(90, 2, 13),   // 7
347                Job::new(2, 20, 88),   // 8
348                Job::new(52, 20, 56),  // 9
349                Job::new(9, 28, 94),   // 10
350            ],
351        });
352        let result = schrage(&js.job_list);
353        assert_eq!(result.job_list, expected_result.job_list);
354        assert_eq!(result.c_max(), 213);
355    }
356
357    #[test]
358    fn test_sort() {
359        let js = JobList {
360            jobs: vec![
361                Job::new(0, 6, 17),  // 6
362                Job::new(10, 5, 7),  // 1
363                Job::new(13, 6, 26), // 2
364                Job::new(11, 7, 24), // 3
365                Job::new(20, 4, 21), // 4
366                Job::new(30, 3, 8),  // 5
367                Job::new(30, 2, 0),  // 7
368            ],
369        };
370        println!("Before sort: {}", js);
371        println!(
372            "After sort: {}",
373            JobList {
374                jobs: js.sorted_by_cooldown_time()
375            }
376        );
377        assert_eq!(true, true);
378    }
379
380    #[test]
381    fn test_part_time_schrage1() {
382        let js = JobList::new(vec![
383            Job::new(0, 27, 78),
384            Job::new(140, 7, 67),
385            Job::new(14, 36, 54),
386            Job::new(133, 76, 5),
387        ]);
388        let result = part_time_schrage(&js);
389        assert_eq!(result, 221)
390    }
391
392    #[test]
393    fn test_part_time_schrage2() {
394        let js = JobList::new(vec![
395            Job::new(8, 68, 984),
396            Job::new(747, 60, 1241),
397            Job::new(811, 78, 56),
398            Job::new(1760, 58, 1558),
399            Job::new(860, 16, 319),
400            Job::new(1549, 28, 927),
401            Job::new(1010, 96, 749),
402            Job::new(738, 37, 844),
403            Job::new(599, 20, 1170),
404            Job::new(446, 53, 1509),
405            Job::new(1363, 36, 19),
406            Job::new(1277, 14, 685),
407            Job::new(1574, 98, 1472),
408            Job::new(1886, 3, 1571),
409            Job::new(591, 21, 1587),
410            Job::new(714, 25, 1490),
411            Job::new(1881, 43, 1647),
412            Job::new(983, 62, 514),
413            Job::new(858, 8, 1215),
414            Job::new(634, 7, 587),
415            Job::new(784, 14, 1897),
416            Job::new(1893, 22, 1878),
417            Job::new(308, 89, 1039),
418            Job::new(1892, 91, 1815),
419            Job::new(1024, 75, 1602),
420            Job::new(1467, 59, 378),
421            Job::new(1830, 3, 1173),
422            Job::new(167, 25, 702),
423            Job::new(357, 3, 416),
424            Job::new(1739, 68, 71),
425            Job::new(1810, 58, 1220),
426            Job::new(453, 62, 393),
427            Job::new(462, 60, 22),
428            Job::new(332, 25, 1512),
429            Job::new(845, 96, 1176),
430            Job::new(522, 80, 513),
431            Job::new(1110, 61, 1854),
432            Job::new(484, 32, 570),
433            Job::new(545, 91, 274),
434            Job::new(64, 67, 74),
435            Job::new(90, 9, 1423),
436            Job::new(1013, 67, 1567),
437            Job::new(1509, 86, 878),
438            Job::new(238, 12, 285),
439            Job::new(1226, 23, 1767),
440            Job::new(83, 35, 22),
441            Job::new(626, 97, 63),
442            Job::new(6, 24, 707),
443            Job::new(507, 31, 1294),
444            Job::new(638, 98, 1528),
445        ]);
446        let result = part_time_schrage(&js);
447        assert_eq!(result, 3820);
448    }
449
450    #[test]
451    fn test_part_time_schrage3() {
452        let js = JobList::new(vec![
453            Job::new(162, 52, 241),
454            Job::new(103, 68, 470),
455            Job::new(39, 38, 340),
456            Job::new(394, 34, 400),
457            Job::new(15, 86, 700),
458            Job::new(144, 73, 536),
459            Job::new(51, 52, 403),
460            Job::new(233, 68, 23),
461            Job::new(183, 17, 641),
462            Job::new(728, 18, 640),
463            Job::new(667, 80, 92),
464            Job::new(57, 21, 76),
465            Job::new(35, 37, 386),
466            Job::new(567, 71, 618),
467            Job::new(226, 5, 629),
468            Job::new(162, 80, 575),
469            Job::new(588, 45, 632),
470            Job::new(556, 23, 79),
471            Job::new(715, 8, 93),
472            Job::new(598, 45, 200),
473        ]);
474        let result = part_time_schrage(&js);
475        assert_eq!(result, 1386);
476    }
477
478    #[test]
479    fn test_part_time_schrage4() {
480        let js = JobList::new(vec![
481            Job::new(219, 5, 276),
482            Job::new(84, 13, 103),
483            Job::new(336, 35, 146),
484            Job::new(271, 62, 264),
485            Job::new(120, 33, 303),
486            Job::new(299, 14, 328),
487            Job::new(106, 46, 91),
488            Job::new(181, 93, 97),
489            Job::new(263, 13, 168),
490            Job::new(79, 60, 235),
491        ]);
492        let result = part_time_schrage(&js);
493        assert_eq!(result, 641);
494    }
495}
proc_opt/schrage/mod.rs

proc_opt/schrage/
mod.rs
