proc_opt/
jobs.rs

1//! Implements Job structs used for processing data by scheduling algorithms.
2//!
3//!
4//!
5//!
6//!
7//!
8//!
9//!
10//!
11//!
12//!
13//!
14//!
15use std::collections::HashMap;
16use std::{fmt, vec};
17
18#[derive(Copy, Clone, Debug)]
19pub struct Job {
20    pub delivery_time: u32,   // r
21    pub processing_time: u32, // p
22    pub cooldown_time: u32,   // q
23}
24
25impl Job {
26    pub fn new(delivery_time: u32, processing_time: u32, cooldown_time: u32) -> Job {
27        Job {
28            delivery_time,
29            processing_time,
30            cooldown_time,
31        }
32    }
33
34    #[allow(dead_code)]
35    pub fn total_time(&self) -> u32 {
36        self.delivery_time + self.processing_time + self.cooldown_time
37    }
38}
39
40impl fmt::Display for Job {
41    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
42        write!(
43            f,
44            "({}, {}, {})",
45            self.delivery_time, self.processing_time, self.cooldown_time
46        )
47    }
48}
49
50impl PartialEq for Job {
51    fn eq(&self, other: &Self) -> bool {
52        self.delivery_time == other.delivery_time
53            && self.processing_time == other.processing_time
54            && self.cooldown_time == other.cooldown_time
55    }
56}
57
58#[derive(Debug, Clone)]
59pub struct JobList {
60    pub jobs: Vec<Job>,
61}
62
63impl fmt::Display for JobList {
64    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
65        for i in &self.jobs {
66            writeln!(f, "{}", i)?;
67        }
68        Ok(())
69    }
70}
71
72impl JobList {
73    /// Creates a new [`JobList`].
74    pub fn new(jobs: Vec<Job>) -> JobList {
75        JobList { jobs }
76    }
77
78    /// Returns the Job List sorted by delivery time of this [`JobList`].
79    #[allow(dead_code)]
80    pub fn sorted_by_delivery_time(&self) -> Vec<Job> {
81        let mut by_delivery_time = self.jobs.clone();
82        by_delivery_time.sort_by_key(|a| a.delivery_time);
83        by_delivery_time
84    }
85
86    /// Returns the Job List sorted by processing time of this [`JobList`].
87    #[allow(dead_code)]
88    pub fn sorted_by_processing_time(&self) -> Vec<Job> {
89        let mut by_processing_time = self.jobs.clone();
90        by_processing_time.sort_by_key(|a| a.processing_time);
91        by_processing_time
92    }
93
94    /// Returns the Job List sorted by cooldown time of this [`JobList`].
95    #[allow(dead_code)]
96    pub fn sorted_by_cooldown_time(&self) -> Vec<Job> {
97        let mut by_cooldown_time = self.jobs.clone();
98        by_cooldown_time.sort_by_key(|a| a.cooldown_time);
99        by_cooldown_time
100    }
101}
102
103impl PartialEq for JobList {
104    fn eq(&self, other: &Self) -> bool {
105        if self.jobs.len() != other.jobs.len() {
106            return false;
107        }
108        for (i, j) in self.jobs.iter().enumerate() {
109            if j != &other.jobs[i] {
110                return false;
111            }
112        }
113        true
114    }
115}
116
117pub struct SchrageJobTable {
118    pub job_list: JobList,
119}
120
121impl SchrageJobTable {
122    pub fn new(job_list: JobList) -> SchrageJobTable {
123        SchrageJobTable { job_list }
124    }
125
126    /// Returns the c max of this [`SchrageJobTable`].
127    ///
128    /// # Panics
129    ///
130    /// Panics if the job list is empty.
131    pub fn c_max(&self) -> u32 {
132        let mut end_times = vec![0; self.job_list.jobs.len()];
133        let mut s = 0;
134        let mut sums = vec![0; self.job_list.jobs.len()];
135
136        for (i, job) in self.job_list.jobs.iter().enumerate() {
137            if job.delivery_time > s {
138                s = job.delivery_time + job.processing_time;
139            } else {
140                s += job.processing_time;
141            }
142            end_times[i] = s;
143        }
144
145        for (i, job) in self.job_list.jobs.iter().enumerate() {
146            sums[i] = job.cooldown_time + end_times[i];
147        }
148        *sums.iter().max().unwrap()
149    }
150}
151
152pub struct PartTimeSchrageJobTable {
153    pub job_list: JobList,
154    pub time_table: HashMap<u32, u32>,
155}
156
157impl PartTimeSchrageJobTable {
158    pub fn c_max_wip(&self) -> u32 {
159        let mut end_times = vec![0; self.job_list.jobs.len()];
160        let mut s = 0;
161        let mut sums = vec![0; self.job_list.jobs.len()];
162
163        for (i, job) in self.job_list.jobs.iter().enumerate() {
164            if job.delivery_time > s {
165                s = job.delivery_time + job.processing_time;
166            } else {
167                s += job.processing_time;
168            }
169            end_times[i] = s;
170        }
171
172        for (i, job) in self.job_list.jobs.iter().enumerate() {
173            sums[i] = job.cooldown_time + end_times[i];
174        }
175        *sums.iter().max().unwrap()
176    }
177}
178
179#[cfg(test)]
180mod tests {
181
182    use super::*;
183
184    #[test]
185    fn test_c_max_ex1() {
186        let js = SchrageJobTable::new(JobList {
187            jobs: vec![
188                Job::new(10, 5, 7),  // 1
189                Job::new(13, 6, 26), // 2
190                Job::new(11, 7, 24), // 3
191                Job::new(20, 4, 21), // 4
192                Job::new(30, 3, 8),  // 5
193                Job::new(0, 6, 17),  // 6
194                Job::new(30, 2, 0),  // 7
195            ],
196        });
197        let result = js.c_max();
198        assert_eq!(result, 58);
199    }
200
201    #[test]
202    fn test_c_max_ex2() {
203        let js = SchrageJobTable::new(JobList {
204            jobs: vec![
205                Job::new(0, 6, 17),  // 6
206                Job::new(10, 5, 7),  // 1
207                Job::new(13, 6, 26), // 2
208                Job::new(11, 7, 24), // 3
209                Job::new(20, 4, 21), // 4
210                Job::new(30, 3, 8),  // 5
211                Job::new(30, 2, 0),  // 7
212            ],
213        });
214        let result = js.c_max();
215        assert_eq!(result, 53);
216    }
217
218    #[test]
219    fn test_c_max_ex3() {
220        let js = SchrageJobTable::new(JobList {
221            jobs: vec![
222                Job::new(0, 6, 17),  // 6
223                Job::new(11, 7, 24), // 3
224                Job::new(13, 6, 26), // 2
225                Job::new(20, 4, 21), // 4
226                Job::new(10, 5, 7),  // 1
227                Job::new(30, 3, 8),  // 5
228                Job::new(30, 2, 0),  // 7
229            ],
230        });
231        let result = js.c_max();
232        assert_eq!(result, 50);
233    }
234
235    #[test]
236    fn test_c_max_ex4() {
237        let js = SchrageJobTable::new(JobList {
238            jobs: vec![
239                Job::new(2, 20, 88),   // 8
240                Job::new(5, 14, 125),  // 4
241                Job::new(8, 16, 114),  // 5
242                Job::new(9, 28, 94),   // 10
243                Job::new(70, 4, 93),   // 2
244                Job::new(71, 7, 71),   // 6
245                Job::new(52, 1, 56),   // 1
246                Job::new(52, 20, 56),  // 9
247                Job::new(112, 22, 79), // 3
248                Job::new(90, 2, 13),   // 7
249            ],
250        });
251        let result = js.c_max();
252        assert_eq!(result, 213);
253    }
254
255    #[test]
256    fn test_c_max_ex5() {
257        let js = SchrageJobTable::new(JobList {
258            jobs: vec![
259                Job::new(15, 86, 700),  // 5
260                Job::new(51, 52, 403),  // 7
261                Job::new(144, 73, 536), // 6
262                Job::new(183, 17, 641), // 9
263                Job::new(226, 5, 629),  // 15
264                Job::new(162, 80, 575), // 16
265                Job::new(103, 68, 470), // 2
266                Job::new(394, 34, 400), // 4
267                Job::new(35, 37, 386),  // 13
268                Job::new(39, 38, 340),  // 3
269                Job::new(162, 52, 241), // 1
270                Job::new(556, 23, 79),  // 18
271                Job::new(567, 71, 618), // 14
272                Job::new(588, 45, 632), // 17
273                Job::new(598, 45, 200), // 20
274                Job::new(728, 18, 640), // 10
275                Job::new(715, 8, 93),   // 19
276                Job::new(667, 80, 92),  // 11
277                Job::new(57, 21, 76),   // 12
278                Job::new(233, 68, 23),  // 8
279            ],
280        });
281        let result = js.c_max();
282        assert_eq!(result, 1399);
283    }
284}
proc_opt/jobs.rs

proc_opt/
jobs.rs
