problemreductions/models/misc/
job_shop_scheduling.rs

1//! Job Shop Scheduling problem implementation.
2//!
3//! Given `m` processors and a set of jobs, each job consisting of an ordered
4//! sequence of processor-length tasks, find a schedule that minimizes the
5//! makespan (completion time of the last task) while respecting both within-job
6//! precedence and single-processor capacity constraints.
7
8use crate::registry::{FieldInfo, ProblemSchemaEntry};
9use crate::traits::Problem;
10use crate::types::Min;
11use serde::{Deserialize, Serialize};
12use std::collections::VecDeque;
13
14inventory::submit! {
15    ProblemSchemaEntry {
16        name: "JobShopScheduling",
17        display_name: "Job-Shop Scheduling",
18        aliases: &[],
19        dimensions: &[],
20        module_path: module_path!(),
21        description: "Minimize the makespan of a job-shop schedule",
22        fields: &[
23            FieldInfo { name: "num_processors", type_name: "usize", description: "Number of processors m" },
24            FieldInfo { name: "jobs", type_name: "Vec<Vec<(usize, u64)>>", description: "jobs[j][k] = (processor, length) for the k-th task of job j" },
25        ],
26    }
27}
28
29#[derive(Debug, Clone, Serialize, Deserialize)]
30pub struct JobShopScheduling {
31    num_processors: usize,
32    jobs: Vec<Vec<(usize, u64)>>,
33}
34
35struct FlattenedTasks {
36    job_task_ids: Vec<Vec<usize>>,
37    machine_task_ids: Vec<Vec<usize>>,
38    lengths: Vec<u64>,
39}
40
41impl JobShopScheduling {
42    pub fn new(num_processors: usize, jobs: Vec<Vec<(usize, u64)>>) -> Self {
43        let num_tasks: usize = jobs.iter().map(Vec::len).sum();
44        if num_tasks > 0 {
45            assert!(
46                num_processors > 0,
47                "num_processors must be positive when tasks are present"
48            );
49        }
50
51        for (job_index, job) in jobs.iter().enumerate() {
52            for (task_index, &(processor, _length)) in job.iter().enumerate() {
53                assert!(
54                    processor < num_processors,
55                    "job {job_index} task {task_index} uses processor {processor}, but num_processors = {num_processors}"
56                );
57            }
58
59            for (task_index, pair) in job.windows(2).enumerate() {
60                assert_ne!(
61                    pair[0].0,
62                    pair[1].0,
63                    "job {job_index} tasks {task_index} and {} must use different processors",
64                    task_index + 1
65                );
66            }
67        }
68
69        Self {
70            num_processors,
71            jobs,
72        }
73    }
74
75    pub fn num_processors(&self) -> usize {
76        self.num_processors
77    }
78
79    pub fn jobs(&self) -> &[Vec<(usize, u64)>] {
80        &self.jobs
81    }
82
83    pub fn num_jobs(&self) -> usize {
84        self.jobs.len()
85    }
86
87    pub fn num_tasks(&self) -> usize {
88        self.jobs.iter().map(Vec::len).sum()
89    }
90
91    fn flatten_tasks(&self) -> FlattenedTasks {
92        let mut job_task_ids = Vec::with_capacity(self.jobs.len());
93        let mut machine_task_ids = vec![Vec::new(); self.num_processors];
94        let mut lengths = Vec::with_capacity(self.num_tasks());
95        let mut task_id = 0usize;
96
97        for job in &self.jobs {
98            let mut ids = Vec::with_capacity(job.len());
99            for &(processor, length) in job {
100                ids.push(task_id);
101                machine_task_ids[processor].push(task_id);
102                lengths.push(length);
103                task_id += 1;
104            }
105            job_task_ids.push(ids);
106        }
107
108        FlattenedTasks {
109            job_task_ids,
110            machine_task_ids,
111            lengths,
112        }
113    }
114
115    fn decode_machine_orders(
116        &self,
117        config: &[usize],
118        flattened: &FlattenedTasks,
119    ) -> Option<Vec<Vec<usize>>> {
120        if config.len() != flattened.lengths.len() {
121            return None;
122        }
123
124        let mut offset = 0usize;
125        let mut orders = Vec::with_capacity(flattened.machine_task_ids.len());
126
127        for machine_tasks in &flattened.machine_task_ids {
128            let k = machine_tasks.len();
129            let perm = super::decode_lehmer(&config[offset..offset + k], k)?;
130            orders.push(perm.into_iter().map(|i| machine_tasks[i]).collect());
131            offset += k;
132        }
133
134        Some(orders)
135    }
136
137    /// Compute start times from a Lehmer-code config. Returns `None` if the
138    /// config is invalid or induces a cycle in the precedence DAG.
139    pub fn schedule_from_config(&self, config: &[usize]) -> Option<Vec<u64>> {
140        self.schedule_from_config_inner(config, &self.flatten_tasks())
141    }
142
143    fn schedule_from_config_inner(
144        &self,
145        config: &[usize],
146        flattened: &FlattenedTasks,
147    ) -> Option<Vec<u64>> {
148        let machine_orders = self.decode_machine_orders(config, flattened)?;
149        let num_tasks = flattened.lengths.len();
150
151        if num_tasks == 0 {
152            return Some(Vec::new());
153        }
154
155        let mut adjacency = vec![Vec::<usize>::new(); num_tasks];
156        let mut indegree = vec![0usize; num_tasks];
157
158        for job_ids in &flattened.job_task_ids {
159            for pair in job_ids.windows(2) {
160                adjacency[pair[0]].push(pair[1]);
161                indegree[pair[1]] += 1;
162            }
163        }
164
165        for machine_order in &machine_orders {
166            for pair in machine_order.windows(2) {
167                adjacency[pair[0]].push(pair[1]);
168                indegree[pair[1]] += 1;
169            }
170        }
171
172        let mut queue = VecDeque::new();
173        for (task_id, &degree) in indegree.iter().enumerate() {
174            if degree == 0 {
175                queue.push_back(task_id);
176            }
177        }
178
179        let mut start_times = vec![0u64; num_tasks];
180        let mut processed = 0usize;
181
182        while let Some(task_id) = queue.pop_front() {
183            processed += 1;
184            let finish = start_times[task_id].checked_add(flattened.lengths[task_id])?;
185
186            for &next_task in &adjacency[task_id] {
187                start_times[next_task] = start_times[next_task].max(finish);
188                indegree[next_task] -= 1;
189                if indegree[next_task] == 0 {
190                    queue.push_back(next_task);
191                }
192            }
193        }
194
195        if processed != num_tasks {
196            return None;
197        }
198
199        Some(start_times)
200    }
201}
202
203impl Problem for JobShopScheduling {
204    const NAME: &'static str = "JobShopScheduling";
205    type Value = Min<u64>;
206
207    fn variant() -> Vec<(&'static str, &'static str)> {
208        crate::variant_params![]
209    }
210
211    fn dims(&self) -> Vec<usize> {
212        self.flatten_tasks()
213            .machine_task_ids
214            .into_iter()
215            .flat_map(|machine_tasks| super::lehmer_dims(machine_tasks.len()))
216            .collect()
217    }
218
219    fn evaluate(&self, config: &[usize]) -> Min<u64> {
220        let flattened = self.flatten_tasks();
221        match self.schedule_from_config_inner(config, &flattened) {
222            Some(start_times) => {
223                let makespan = start_times
224                    .iter()
225                    .enumerate()
226                    .map(|(i, &s)| s + flattened.lengths[i])
227                    .max()
228                    .unwrap_or(0);
229                Min(Some(makespan))
230            }
231            None => Min(None),
232        }
233    }
234}
235
236crate::declare_variants! {
237    default JobShopScheduling => "factorial(num_tasks)",
238}
239
240#[cfg(feature = "example-db")]
241pub(crate) fn canonical_model_example_specs() -> Vec<crate::example_db::specs::ModelExampleSpec> {
242    vec![crate::example_db::specs::ModelExampleSpec {
243        id: "job_shop_scheduling",
244        instance: Box::new(JobShopScheduling::new(
245            2,
246            vec![
247                vec![(0, 3), (1, 4)],
248                vec![(1, 2), (0, 3), (1, 2)],
249                vec![(0, 4), (1, 3)],
250                vec![(1, 5), (0, 2)],
251                vec![(0, 2), (1, 3), (0, 1)],
252            ],
253        )),
254        // Machine 0 order [0,3,5,8,9,11] => [0,0,0,0,0,0]
255        // Machine 1 order [2,7,1,6,10,4] => [1,3,0,1,1,0]
256        optimal_config: vec![0, 0, 0, 0, 0, 0, 1, 3, 0, 1, 1, 0],
257        optimal_value: serde_json::json!(19),
258    }]
259}
260
261#[cfg(test)]
262#[path = "../../unit_tests/models/misc/job_shop_scheduling.rs"]
263mod tests;
problemreductions/models/misc/job_shop_scheduling.rs

problemreductions/models/misc/
job_shop_scheduling.rs
