problemreductions/models/misc/
sequencing_to_minimize_maximum_cumulative_cost.rs

1//! Sequencing to Minimize Maximum Cumulative Cost problem implementation.
2//!
3//! Given a set of tasks with integer costs and precedence constraints, find
4//! a valid one-machine schedule that minimizes the maximum cumulative cost
5//! over all prefixes.
6
7use crate::registry::{CreateSpec, ProblemSchemaEntry};
8use crate::traits::Problem;
9use serde::de::Error as _;
10use serde::{Deserialize, Serialize};
11
12inventory::submit! {
13    ProblemSchemaEntry {
14        name: "SequencingToMinimizeMaximumCumulativeCost",
15        display_name: "Sequencing to Minimize Maximum Cumulative Cost",
16        aliases: &[],
17        dimensions: &[],
18        category: crate::registry::ProblemCategory::Misc,
19        module_path: module_path!(),
20        description: "Schedule tasks with precedence constraints to minimize the maximum cumulative cost prefix",
21        fields: SequencingCumulativeCostCreateSpec::FIELDS,
22    }
23}
24
25/// Sequencing to Minimize Maximum Cumulative Cost.
26///
27/// Given a set of tasks `T`, a cost `c(t) in Z` for each task, and a partial
28/// order on the tasks, find a schedule that respects the precedences and
29/// minimizes the maximum cumulative cost over all prefixes.
30///
31/// # Representation
32///
33/// Configurations use Lehmer-code dimensions `[n, n-1, ..., 1]` to encode a
34/// permutation of the task indices.
35#[derive(Debug, Clone, Serialize)]
36pub struct SequencingToMinimizeMaximumCumulativeCost {
37    costs: Vec<i64>,
38    precedences: Vec<(usize, usize)>,
39}
40
41#[derive(Debug, Deserialize, crate::CreateSpec)]
42struct SequencingCumulativeCostCreateSpec {
43    /// Task costs.
44    #[create(codec = "comma-separated")]
45    costs: Vec<i64>,
46    /// Precedence arcs; omitted means no constraints.
47    #[create(codec = "arc-list")]
48    precedences: Option<Vec<(usize, usize)>>,
49}
50
51impl TryFrom<SequencingCumulativeCostCreateSpec> for SequencingToMinimizeMaximumCumulativeCost {
52    type Error = crate::registry::ConstructionError;
53    fn try_from(spec: SequencingCumulativeCostCreateSpec) -> Result<Self, Self::Error> {
54        let precedences = spec.precedences.unwrap_or_default();
55        if let Some(message) = precedence_validation_error(&precedences, spec.costs.len()) {
56            return Err(message.into());
57        }
58        Ok(Self {
59            costs: spec.costs,
60            precedences,
61        })
62    }
63}
64
65#[derive(Debug, Deserialize)]
66struct SequencingToMinimizeMaximumCumulativeCostUnchecked {
67    costs: Vec<i64>,
68    precedences: Vec<(usize, usize)>,
69}
70
71impl SequencingToMinimizeMaximumCumulativeCost {
72    /// Create a new instance.
73    ///
74    /// # Panics
75    ///
76    /// Panics if any precedence endpoint is out of range.
77    pub fn new(costs: Vec<i64>, precedences: Vec<(usize, usize)>) -> Self {
78        validate_precedences(&precedences, costs.len());
79        Self { costs, precedences }
80    }
81
82    /// Return the task costs.
83    pub fn costs(&self) -> &[i64] {
84        &self.costs
85    }
86
87    /// Return the precedence constraints.
88    pub fn precedences(&self) -> &[(usize, usize)] {
89        &self.precedences
90    }
91
92    /// Return the number of tasks.
93    pub fn num_tasks(&self) -> usize {
94        self.costs.len()
95    }
96
97    /// Return the number of precedence constraints.
98    pub fn num_precedences(&self) -> usize {
99        self.precedences.len()
100    }
101
102    fn decode_schedule(&self, config: &[usize]) -> Option<Vec<usize>> {
103        super::decode_permutation(config, self.num_tasks())
104    }
105}
106
107impl<'de> Deserialize<'de> for SequencingToMinimizeMaximumCumulativeCost {
108    fn deserialize<D>(deserializer: D) -> Result<Self, D::Error>
109    where
110        D: serde::Deserializer<'de>,
111    {
112        let unchecked =
113            SequencingToMinimizeMaximumCumulativeCostUnchecked::deserialize(deserializer)?;
114        if let Some(message) =
115            precedence_validation_error(&unchecked.precedences, unchecked.costs.len())
116        {
117            return Err(D::Error::custom(message));
118        }
119        Ok(Self {
120            costs: unchecked.costs,
121            precedences: unchecked.precedences,
122        })
123    }
124}
125
126fn validate_precedences(precedences: &[(usize, usize)], num_tasks: usize) {
127    if let Some(message) = precedence_validation_error(precedences, num_tasks) {
128        panic!("{message}");
129    }
130}
131
132fn precedence_validation_error(precedences: &[(usize, usize)], num_tasks: usize) -> Option<String> {
133    for &(pred, succ) in precedences {
134        if pred >= num_tasks {
135            return Some(format!(
136                "predecessor index {} out of range (num_tasks = {})",
137                pred, num_tasks
138            ));
139        }
140        if succ >= num_tasks {
141            return Some(format!(
142                "successor index {} out of range (num_tasks = {})",
143                succ, num_tasks
144            ));
145        }
146    }
147    None
148}
149
150impl Problem for SequencingToMinimizeMaximumCumulativeCost {
151    const NAME: &'static str = "SequencingToMinimizeMaximumCumulativeCost";
152    type Solution = Vec<usize>;
153    type Value = crate::types::Min<i64>;
154
155    crate::problem_parameters![
156        ("num_precedences", num_precedences),
157        ("num_tasks", num_tasks),
158    ];
159
160    fn variant() -> Vec<(&'static str, &'static str)> {
161        crate::variant_params![]
162    }
163
164    fn evaluate(
165        &self,
166        config: &Self::Solution,
167    ) -> Result<crate::types::Min<i64>, crate::traits::EvaluationError> {
168        let n = self.num_tasks();
169        if config.len() != n {
170            return Err(crate::traits::EvaluationError::InvalidConfiguration(
171                "schedule length does not match the tasks".into(),
172            ));
173        }
174        if config.iter().any(|&task| task >= n) {
175            return Err(crate::traits::EvaluationError::InvalidConfiguration(
176                "schedule contains an out-of-range task".into(),
177            ));
178        }
179        Ok({
180            let Some(schedule) = self.decode_schedule(config) else {
181                return Ok(crate::types::Min(None));
182            };
183
184            let mut positions = vec![0usize; self.num_tasks()];
185            for (position, &task) in schedule.iter().enumerate() {
186                positions[task] = position;
187            }
188            for &(pred, succ) in &self.precedences {
189                if positions[pred] >= positions[succ] {
190                    return Ok(crate::types::Min(None));
191                }
192            }
193
194            let mut cumulative = 0i64;
195            let mut max_cumulative = 0i64;
196            for &task in &schedule {
197                cumulative = cumulative.checked_add(self.costs[task]).ok_or_else(|| {
198                    crate::traits::EvaluationError::IntegerOverflow(
199                        "summing sequencing cumulative costs".into(),
200                    )
201                })?;
202                if cumulative > max_cumulative {
203                    max_cumulative = cumulative;
204                }
205            }
206            crate::types::Min(Some(max_cumulative))
207        })
208    }
209}
210
211impl crate::solvers::BruteForceProblem for SequencingToMinimizeMaximumCumulativeCost {
212    fn dimensions(&self) -> Vec<usize> {
213        super::lehmer_dims(self.num_tasks())
214    }
215}
216
217crate::declare_variants! {
218    default SequencingToMinimizeMaximumCumulativeCost => "factorial(num_tasks)" create SequencingCumulativeCostCreateSpec,
219}
220
221crate::register_brute_force! {
222    SequencingToMinimizeMaximumCumulativeCost decode |problem: &SequencingToMinimizeMaximumCumulativeCost, indices: Vec<usize>| super::decode_lehmer(&indices, problem.num_tasks()).expect("enumerated Lehmer digits are valid"),
223}
224
225#[cfg(feature = "example-db")]
226pub(crate) fn canonical_model_example_specs() -> Vec<crate::example_db::specs::ModelExampleSpec> {
227    vec![crate::example_db::specs::ModelExampleSpec {
228        id: "sequencing_to_minimize_maximum_cumulative_cost",
229        instance: Box::new(SequencingToMinimizeMaximumCumulativeCost::new(
230            vec![2, -1, 3, -2, 1, -3],
231            vec![(0, 2), (1, 2), (1, 3), (2, 4), (3, 5), (4, 5)],
232        )),
233        optimal_config: serde_json::json!(vec![1, 0, 3, 2, 4, 5]),
234        optimal_value: serde_json::json!(3),
235    }]
236}
237
238#[cfg(test)]
239#[path = "../../unit_tests/models/misc/sequencing_to_minimize_maximum_cumulative_cost.rs"]
240mod tests;
problemreductions/models/misc/sequencing_to_minimize_maximum_cumulative_cost.rs

problemreductions/models/misc/
sequencing_to_minimize_maximum_cumulative_cost.rs
