problemreductions/models/misc/

job_shop_scheduling.rs

//! Job Shop Scheduling problem implementation.
//!
//! Given `m` processors and a set of jobs, each job consisting of an ordered
//! sequence of processor-length tasks, find a schedule that minimizes the
//! makespan (completion time of the last task) while respecting both within-job
//! precedence and single-processor capacity constraints.

use crate::registry::{CreateSpec, ProblemSchemaEntry};
use crate::traits::Problem;
use crate::types::Min;
use serde::{Deserialize, Serialize};
use std::collections::VecDeque;

inventory::submit! {
    ProblemSchemaEntry {
        name: "JobShopScheduling",
        display_name: "Job-Shop Scheduling",
        aliases: &[],
        dimensions: &[],
        category: crate::registry::ProblemCategory::Misc,
        module_path: module_path!(),
        description: "Minimize the makespan of a job-shop schedule",
        fields: JobShopSchedulingCreateSpec::FIELDS,
    }
}

#[derive(Debug, Clone, Serialize, Deserialize)]
#[serde(try_from = "JobShopSchedulingData")]
pub struct JobShopScheduling {
    num_processors: usize,
    jobs: Vec<Vec<(usize, i64)>>,
}

#[derive(Deserialize)]
struct JobShopSchedulingData {
    num_processors: usize,
    jobs: Vec<Vec<(usize, i64)>>,
}

impl TryFrom<JobShopSchedulingData> for JobShopScheduling {
    type Error = crate::registry::ConstructionError;

    fn try_from(data: JobShopSchedulingData) -> Result<Self, Self::Error> {
        Self::try_new(data.num_processors, data.jobs)
    }
}

#[derive(Debug, Deserialize, crate::CreateSpec)]
struct JobShopSchedulingCreateSpec {
    /// Jobs expressed as ordered processor-duration operations.
    #[create(codec = "semicolon-separated")]
    jobs: Vec<Vec<(usize, i64)>>,
    /// Optional processor count; omitted values are inferred from the jobs.
    num_processors: Option<usize>,
}

impl TryFrom<JobShopSchedulingCreateSpec> for JobShopScheduling {
    type Error = crate::registry::ConstructionError;

    fn try_from(spec: JobShopSchedulingCreateSpec) -> Result<Self, Self::Error> {
        let inferred_processors = spec
            .jobs
            .iter()
            .flatten()
            .map(|(processor, _)| *processor)
            .max()
            .map(|processor| {
                processor
                    .checked_add(1)
                    .ok_or_else(|| "inferred processor count overflows usize".to_string())
            })
            .transpose()?;
        let num_processors = spec.num_processors.or(inferred_processors).ok_or_else(|| {
            "cannot infer processor count from an empty job list; provide num_processors"
                .to_string()
        })?;
        if num_processors == 0 {
            return Err("num_processors must be positive".to_string().into());
        }

        Self::try_new(num_processors, spec.jobs)
    }
}

struct FlattenedTasks {
    job_task_ids: Vec<Vec<usize>>,
    machine_task_ids: Vec<Vec<usize>>,
    lengths: Vec<i64>,
}

impl JobShopScheduling {
    pub fn new(num_processors: usize, jobs: Vec<Vec<(usize, i64)>>) -> Self {
        Self::try_new(num_processors, jobs).unwrap_or_else(|error| panic!("{error}"))
    }

    fn try_new(
        num_processors: usize,
        jobs: Vec<Vec<(usize, i64)>>,
    ) -> Result<Self, crate::registry::ConstructionError> {
        if jobs.iter().any(|job| !job.is_empty()) && num_processors == 0 {
            return Err("num_processors must be positive when tasks are present".into());
        }
        if jobs.iter().flatten().any(|&(_, length)| length < 0) {
            return Err("operation lengths must be nonnegative".into());
        }

        for (job_index, job) in jobs.iter().enumerate() {
            for (task_index, &(processor, _length)) in job.iter().enumerate() {
                if processor >= num_processors {
                    return Err(format!("job {job_index} task {task_index} uses processor {processor}, but num_processors = {num_processors}").into());
                }
            }

            for (task_index, pair) in job.windows(2).enumerate() {
                if pair[0].0 == pair[1].0 {
                    return Err(format!(
                        "job {job_index} tasks {task_index} and {} must use different processors",
                        task_index + 1
                    )
                    .into());
                }
            }
        }

        Ok(Self {
            num_processors,
            jobs,
        })
    }

    pub fn num_processors(&self) -> usize {
        self.num_processors
    }

    pub fn jobs(&self) -> &[Vec<(usize, i64)>] {
        &self.jobs
    }

    pub fn num_jobs(&self) -> usize {
        self.jobs.len()
    }

    pub fn num_tasks(&self) -> usize {
        self.jobs.iter().map(Vec::len).sum()
    }

    fn flatten_tasks(&self) -> FlattenedTasks {
        let mut job_task_ids = Vec::with_capacity(self.jobs.len());
        let mut machine_task_ids = vec![Vec::new(); self.num_processors];
        let mut lengths = Vec::with_capacity(self.num_tasks());
        let mut task_id = 0usize;

        for job in &self.jobs {
            let mut ids = Vec::with_capacity(job.len());
            for &(processor, length) in job {
                ids.push(task_id);
                machine_task_ids[processor].push(task_id);
                lengths.push(length);
                task_id += 1;
            }
            job_task_ids.push(ids);
        }

        FlattenedTasks {
            job_task_ids,
            machine_task_ids,
            lengths,
        }
    }

    fn decode_machine_orders(
        &self,
        config: &[usize],
        flattened: &FlattenedTasks,
    ) -> Option<Vec<Vec<usize>>> {
        if config.len() != flattened.lengths.len() {
            return None;
        }

        let mut offset = 0usize;
        let mut orders = Vec::with_capacity(flattened.machine_task_ids.len());

        for machine_tasks in &flattened.machine_task_ids {
            let k = machine_tasks.len();
            let perm = super::decode_lehmer(&config[offset..offset + k], k)?;
            orders.push(perm.into_iter().map(|i| machine_tasks[i]).collect());
            offset += k;
        }

        Some(orders)
    }

    /// Compute start times from a Lehmer-code config. Returns `None` if the
    /// config is invalid or induces a cycle in the precedence DAG.
    pub fn schedule_from_config(&self, config: &[usize]) -> Option<Vec<i64>> {
        self.schedule_from_config_inner(config, &self.flatten_tasks())
    }

    fn schedule_from_config_inner(
        &self,
        config: &[usize],
        flattened: &FlattenedTasks,
    ) -> Option<Vec<i64>> {
        let machine_orders = self.decode_machine_orders(config, flattened)?;
        let num_tasks = flattened.lengths.len();

        if num_tasks == 0 {
            return Some(Vec::new());
        }

        let mut adjacency = vec![Vec::<usize>::new(); num_tasks];
        let mut indegree = vec![0usize; num_tasks];

        for job_ids in &flattened.job_task_ids {
            for pair in job_ids.windows(2) {
                adjacency[pair[0]].push(pair[1]);
                indegree[pair[1]] += 1;
            }
        }

        for machine_order in &machine_orders {
            for pair in machine_order.windows(2) {
                adjacency[pair[0]].push(pair[1]);
                indegree[pair[1]] += 1;
            }
        }

        let mut queue = VecDeque::new();
        for (task_id, &degree) in indegree.iter().enumerate() {
            if degree == 0 {
                queue.push_back(task_id);
            }
        }

        let mut start_times = vec![0i64; num_tasks];
        let mut processed = 0usize;

        while let Some(task_id) = queue.pop_front() {
            processed += 1;
            let finish = start_times[task_id].checked_add(flattened.lengths[task_id])?;

            for &next_task in &adjacency[task_id] {
                start_times[next_task] = start_times[next_task].max(finish);
                indegree[next_task] -= 1;
                if indegree[next_task] == 0 {
                    queue.push_back(next_task);
                }
            }
        }

        if processed != num_tasks {
            return None;
        }

        Some(start_times)
    }
}

impl Problem for JobShopScheduling {
    const NAME: &'static str = "JobShopScheduling";
    type Solution = Vec<usize>;
    type Value = Min<i64>;

    crate::problem_parameters![
        ("num_processors", num_processors),
        ("num_jobs", num_jobs),
        ("num_tasks", num_tasks),
    ];

    fn variant() -> Vec<(&'static str, &'static str)> {
        crate::variant_params![]
    }

    fn evaluate(
        &self,
        config: &Self::Solution,
    ) -> Result<Min<i64>, crate::traits::EvaluationError> {
        let flattened = self.flatten_tasks();
        if config.len() != flattened.lengths.len() {
            return Err(crate::traits::EvaluationError::InvalidConfiguration(
                "machine-order encoding length does not match the tasks".into(),
            ));
        }
        let dimensions = flattened
            .machine_task_ids
            .iter()
            .flat_map(|machine_tasks| super::lehmer_dims(machine_tasks.len()));
        if config
            .iter()
            .zip(dimensions)
            .any(|(&digit, radix)| digit >= radix)
        {
            return Err(crate::traits::EvaluationError::InvalidConfiguration(
                "machine-order encoding contains an out-of-range digit".into(),
            ));
        }
        Ok({
            match self.schedule_from_config_inner(config, &flattened) {
                Some(start_times) => {
                    let makespan = start_times
                        .iter()
                        .enumerate()
                        .map(|(i, &s)| s + flattened.lengths[i])
                        .max()
                        .unwrap_or(0);
                    Min(Some(makespan))
                }
                None => Min(None),
            }
        })
    }
}

impl crate::solvers::BruteForceProblem for JobShopScheduling {
    fn dimensions(&self) -> Vec<usize> {
        self.flatten_tasks()
            .machine_task_ids
            .into_iter()
            .flat_map(|machine_tasks| super::lehmer_dims(machine_tasks.len()))
            .collect()
    }
}

crate::declare_variants! {
    default JobShopScheduling => "factorial(num_tasks)" create JobShopSchedulingCreateSpec,
}

crate::register_brute_force! {
    JobShopScheduling,
}

#[cfg(feature = "example-db")]
pub(crate) fn canonical_model_example_specs() -> Vec<crate::example_db::specs::ModelExampleSpec> {
    vec![crate::example_db::specs::ModelExampleSpec {
        id: "job_shop_scheduling",
        instance: Box::new(JobShopScheduling::new(
            2,
            vec![
                vec![(0, 3), (1, 4)],
                vec![(1, 2), (0, 3), (1, 2)],
                vec![(0, 4), (1, 3)],
                vec![(1, 5), (0, 2)],
                vec![(0, 2), (1, 3), (0, 1)],
            ],
        )),
        // Machine 0 order [0,3,5,8,9,11] => [0,0,0,0,0,0]
        // Machine 1 order [2,7,1,6,10,4] => [1,3,0,1,1,0]
        optimal_config: serde_json::json!(vec![0, 0, 0, 0, 0, 0, 1, 3, 0, 1, 1, 0]),
        optimal_value: serde_json::json!(19),
    }]
}

#[cfg(test)]
#[path = "../../unit_tests/models/misc/job_shop_scheduling.rs"]
mod tests;