problemreductions/models/misc/
flow_shop_scheduling.rs

1//! Flow Shop Scheduling problem implementation.
2//!
3//! Given m processors and a set of jobs, each consisting of m tasks (one per processor)
4//! that must be processed in processor order 1, 2, ..., m, determine if all jobs can
5//! be completed by a global deadline D.
6
7use crate::registry::{FieldInfo, ProblemSchemaEntry};
8use crate::traits::Problem;
9use serde::{Deserialize, Serialize};
10
11inventory::submit! {
12    ProblemSchemaEntry {
13        name: "FlowShopScheduling",
14        display_name: "Flow Shop Scheduling",
15        aliases: &[],
16        dimensions: &[],
17        category: crate::registry::ProblemCategory::Misc,
18        module_path: module_path!(),
19        description: "Determine if a flow-shop schedule for jobs on m processors meets a deadline",
20        fields: &[
21            FieldInfo { name: "num_processors", type_name: "usize", description: "Number of machines m" },
22            FieldInfo { name: "task_lengths", type_name: "Vec<Vec<i64>>", description: "task_lengths[j][i] = length of job j's task on machine i" },
23            FieldInfo { name: "deadline", type_name: "i64", description: "Global deadline D" },
24        ],
25    }
26}
27
28/// The Flow Shop Scheduling problem.
29///
30/// Given `m` processors and a set of `n` jobs, each job `j` consists of `m` tasks
31/// `t_1[j], t_2[j], ..., t_m[j]` with specified lengths. Tasks must be processed
32/// in processor order: job `j` cannot start on machine `i+1` until its task on
33/// machine `i` is completed. The question is whether there exists a schedule such
34/// that all jobs complete by deadline `D`.
35///
36/// # Representation
37///
38/// Configurations use Lehmer code encoding with `dims() = [n, n-1, ..., 1]`.
39/// A config `[c_0, c_1, ..., c_{n-1}]` where `c_i < n - i` is decoded by
40/// maintaining a list of available jobs and picking the `c_i`-th element:
41///
42/// For 3 jobs, config `[2, 0, 0]`: available=`[0,1,2]`, pick index 2 → job 2;
43/// available=`[0,1]`, pick index 0 → job 0; available=`[1]`, pick index 0 → job 1.
44/// Result: job order `[2, 0, 1]`.
45///
46/// Given a job order, start times are determined greedily (as early as possible).
47///
48/// # Example
49///
50/// ```
51/// use problemreductions::models::misc::FlowShopScheduling;
52/// use problemreductions::{Problem, BruteForce};
53///
54/// // 2 machines, 3 jobs, deadline 10
55/// let problem = FlowShopScheduling::new(2, vec![vec![2, 3], vec![3, 2], vec![1, 4]], 10);
56/// let solver = BruteForce::new();
57/// let solution = solver.solve(&problem).unwrap();
58/// assert!(solution.is_some());
59/// ```
60#[derive(Debug, Clone, Serialize, Deserialize)]
61pub struct FlowShopScheduling {
62    /// Number of processors (machines).
63    num_processors: usize,
64    /// Task lengths: `task_lengths[j][i]` is the processing time of job `j` on machine `i`.
65    task_lengths: Vec<Vec<i64>>,
66    /// Global deadline.
67    deadline: i64,
68}
69
70impl FlowShopScheduling {
71    /// Create a new Flow Shop Scheduling instance.
72    ///
73    /// # Arguments
74    /// * `num_processors` - Number of machines m
75    /// * `task_lengths` - `task_lengths[j][i]` = processing time of job j on machine i.
76    ///   Each inner Vec must have length `num_processors`.
77    /// * `deadline` - Global deadline D
78    ///
79    /// # Panics
80    /// Panics if any job does not have exactly `num_processors` tasks.
81    pub fn new(num_processors: usize, task_lengths: Vec<Vec<i64>>, deadline: i64) -> Self {
82        for (j, tasks) in task_lengths.iter().enumerate() {
83            assert_eq!(
84                tasks.len(),
85                num_processors,
86                "Job {} has {} tasks, expected {}",
87                j,
88                tasks.len(),
89                num_processors
90            );
91        }
92        assert!(
93            task_lengths.iter().flatten().all(|&length| length >= 0),
94            "task lengths must be nonnegative"
95        );
96        assert!(deadline >= 0, "deadline must be nonnegative");
97        Self {
98            num_processors,
99            task_lengths,
100            deadline,
101        }
102    }
103
104    /// Get the number of processors.
105    pub fn num_processors(&self) -> usize {
106        self.num_processors
107    }
108
109    /// Get the task lengths matrix.
110    pub fn task_lengths(&self) -> &[Vec<i64>] {
111        &self.task_lengths
112    }
113
114    /// Get the deadline.
115    pub fn deadline(&self) -> i64 {
116        self.deadline
117    }
118
119    /// Get the number of jobs.
120    pub fn num_jobs(&self) -> usize {
121        self.task_lengths.len()
122    }
123
124    /// Compute the makespan for a given job ordering.
125    ///
126    /// The job_order slice must be a permutation of `0..num_jobs`.
127    /// Returns the completion time of the last job on the last machine.
128    pub fn compute_makespan(
129        &self,
130        job_order: &[usize],
131    ) -> Result<i64, crate::traits::EvaluationError> {
132        let n = job_order.len();
133        let m = self.num_processors;
134        assert_eq!(
135            n,
136            self.task_lengths.len(),
137            "job_order length ({}) does not match num_jobs ({})",
138            n,
139            self.task_lengths.len()
140        );
141        for (k, &job) in job_order.iter().enumerate() {
142            assert!(
143                job < self.task_lengths.len(),
144                "job_order[{}] = {} is out of range (num_jobs = {})",
145                k,
146                job,
147                self.task_lengths.len()
148            );
149        }
150        if n == 0 || m == 0 {
151            return Ok(0);
152        }
153
154        // completion[k][i] = completion time of the k-th job in sequence on machine i
155        let mut completion = vec![vec![0i64; m]; n];
156
157        for (k, &job) in job_order.iter().enumerate() {
158            for i in 0..m {
159                let prev_machine = if i == 0 { 0 } else { completion[k][i - 1] };
160                let prev_job = if k == 0 { 0 } else { completion[k - 1][i] };
161                let start = prev_machine.max(prev_job);
162                completion[k][i] =
163                    start
164                        .checked_add(self.task_lengths[job][i])
165                        .ok_or_else(|| {
166                            crate::traits::EvaluationError::IntegerOverflow(
167                                "computing flow-shop completion time".to_string(),
168                            )
169                        })?;
170            }
171        }
172
173        Ok(completion[n - 1][m - 1])
174    }
175}
176
177impl Problem for FlowShopScheduling {
178    const NAME: &'static str = "FlowShopScheduling";
179    type Solution = Vec<usize>;
180    type Value = crate::types::Or;
181
182    crate::problem_parameters![("num_jobs", num_jobs), ("num_processors", num_processors),];
183
184    fn variant() -> Vec<(&'static str, &'static str)> {
185        crate::variant_params![]
186    }
187
188    fn evaluate(
189        &self,
190        config: &Self::Solution,
191    ) -> Result<crate::types::Or, crate::traits::EvaluationError> {
192        let n = self.num_jobs();
193        if config.len() != n {
194            return Err(crate::traits::EvaluationError::InvalidConfiguration(
195                "job ordering length does not match the jobs".into(),
196            ));
197        }
198        if config.iter().any(|&job| job >= n) {
199            return Err(crate::traits::EvaluationError::InvalidConfiguration(
200                "job ordering contains an out-of-range job".into(),
201            ));
202        }
203        Ok({
204            crate::types::Or({
205                let Some(job_order) = super::decode_permutation(config, self.num_jobs()) else {
206                    return Ok(crate::types::Or(false));
207                };
208
209                let makespan = self.compute_makespan(&job_order)?;
210                makespan <= self.deadline
211            })
212        })
213    }
214}
215
216impl crate::solvers::BruteForceProblem for FlowShopScheduling {
217    fn dimensions(&self) -> Vec<usize> {
218        super::lehmer_dims(self.num_jobs())
219    }
220}
221
222crate::declare_variants! {
223    default FlowShopScheduling => "factorial(num_jobs)",
224}
225
226crate::register_brute_force! {
227    FlowShopScheduling decode |problem: &FlowShopScheduling, indices: Vec<usize>| super::decode_lehmer(&indices, problem.num_jobs()).expect("enumerated Lehmer digits are valid"),
228}
229
230#[cfg(feature = "example-db")]
231pub(crate) fn canonical_model_example_specs() -> Vec<crate::example_db::specs::ModelExampleSpec> {
232    vec![crate::example_db::specs::ModelExampleSpec {
233        id: "flow_shop_scheduling",
234        instance: Box::new(FlowShopScheduling::new(
235            3,
236            vec![
237                vec![3, 4, 2],
238                vec![2, 3, 5],
239                vec![4, 1, 3],
240                vec![1, 5, 4],
241                vec![3, 2, 3],
242            ],
243            25,
244        )),
245        // Job order [3,0,4,2,1] = Lehmer code [3,0,2,1,0], makespan 23
246        optimal_config: serde_json::json!(vec![3, 0, 4, 2, 1]),
247        optimal_value: serde_json::json!(true),
248    }]
249}
250
251#[cfg(test)]
252#[path = "../../unit_tests/models/misc/flow_shop_scheduling.rs"]
253mod tests;
problemreductions/models/misc/flow_shop_scheduling.rs

problemreductions/models/misc/
flow_shop_scheduling.rs
