problemreductions/models/misc/

staff_scheduling.rs

//! Staff Scheduling problem implementation.
//!
//! Given a collection of schedule patterns, period staffing requirements, and a
//! worker budget, determine whether workers can be assigned to schedules so that
//! all requirements are met without exceeding the budget.

use crate::registry::{CreateSpec, ProblemSchemaEntry};
use crate::traits::Problem;
use serde::{Deserialize, Serialize};

inventory::submit! {
    ProblemSchemaEntry {
        name: "StaffScheduling",
        display_name: "Staff Scheduling",
        aliases: &[],
        dimensions: &[],
        category: crate::registry::ProblemCategory::Misc,
        module_path: module_path!(),
        description: "Assign workers to schedule patterns to satisfy per-period staffing requirements within a worker budget",
        fields: StaffSchedulingCreateSpec::FIELDS,
    }
}

/// The Staff Scheduling problem.
///
/// Each variable represents how many workers adopt a particular schedule
/// pattern. A configuration is satisfying iff the total assigned workers does
/// not exceed `num_workers` and every period's staffing requirement is met.
#[derive(Debug, Clone, Serialize, Deserialize)]
pub struct StaffScheduling {
    shifts_per_schedule: usize,
    schedules: Vec<Vec<bool>>,
    requirements: Vec<i64>,
    num_workers: i64,
}

#[derive(Debug, Deserialize, crate::CreateSpec)]
struct StaffSchedulingCreateSpec {
    /// Required number of active periods in each schedule pattern.
    k: usize,
    /// Binary schedule patterns available to workers.
    schedules: Vec<Vec<bool>>,
    /// Minimum staffing requirement for each period.
    requirements: Vec<i64>,
    /// Maximum number of workers available.
    num_workers: i64,
}

impl TryFrom<StaffSchedulingCreateSpec> for StaffScheduling {
    type Error = crate::registry::ConstructionError;

    fn try_from(spec: StaffSchedulingCreateSpec) -> Result<Self, Self::Error> {
        if usize::try_from(spec.num_workers)
            .ok()
            .and_then(|workers| workers.checked_add(1))
            .is_none()
        {
            return Err("num_workers must be nonnegative and encodable by dims()"
                .to_string()
                .into());
        }
        for (schedule_index, schedule) in spec.schedules.iter().enumerate() {
            if schedule.len() != spec.requirements.len() {
                return Err(format!(
                    "schedules[{schedule_index}] has {} periods, expected {}",
                    schedule.len(),
                    spec.requirements.len()
                )
                .into());
            }
            let active_periods = schedule.iter().filter(|&&active| active).count();
            if active_periods != spec.k {
                return Err(format!(
                    "schedules[{schedule_index}] has {active_periods} active periods, expected {}",
                    spec.k
                )
                .into());
            }
        }
        Ok(Self::new(
            spec.k,
            spec.schedules,
            spec.requirements,
            spec.num_workers,
        ))
    }
}

impl StaffScheduling {
    /// Create a new Staff Scheduling instance.
    ///
    /// # Panics
    ///
    /// Panics if `num_workers` does not fit in `usize`, if any schedule has a
    /// different number of periods than `requirements.len()`, or if any
    /// schedule has a number of active periods different from
    /// `shifts_per_schedule`.
    pub fn new(
        shifts_per_schedule: usize,
        schedules: Vec<Vec<bool>>,
        requirements: Vec<i64>,
        num_workers: i64,
    ) -> Self {
        assert!(
            usize::try_from(num_workers)
                .ok()
                .and_then(|workers| workers.checked_add(1))
                .is_some(),
            "num_workers must be nonnegative and encodable by dims()"
        );

        let num_periods = requirements.len();
        for (index, schedule) in schedules.iter().enumerate() {
            assert_eq!(
                schedule.len(),
                num_periods,
                "schedule {} has {} periods, expected {}",
                index,
                schedule.len(),
                num_periods
            );
            let ones = schedule.iter().filter(|&&active| active).count();
            assert_eq!(
                ones, shifts_per_schedule,
                "schedule {} has {} active periods, expected {}",
                index, ones, shifts_per_schedule
            );
        }

        Self {
            shifts_per_schedule,
            schedules,
            requirements,
            num_workers,
        }
    }

    /// Get the number of periods.
    pub fn num_periods(&self) -> usize {
        self.requirements.len()
    }

    /// Get the required number of active periods per schedule.
    pub fn shifts_per_schedule(&self) -> usize {
        self.shifts_per_schedule
    }

    /// Get the schedule patterns.
    pub fn schedules(&self) -> &[Vec<bool>] {
        &self.schedules
    }

    /// Get the staffing requirements.
    pub fn requirements(&self) -> &[i64] {
        &self.requirements
    }

    /// Get the worker budget.
    pub fn num_workers(&self) -> i64 {
        self.num_workers
    }

    /// Get the number of schedule patterns.
    pub fn num_schedules(&self) -> usize {
        self.schedules.len()
    }

    fn worker_limit(&self) -> usize {
        usize::try_from(self.num_workers)
            .expect("validated nonnegative worker count must fit usize")
    }

    fn worker_counts_valid(&self, config: &[usize]) -> bool {
        config.iter().all(|&count| count <= self.worker_limit())
    }

    fn within_budget(&self, config: &[usize]) -> Result<bool, crate::traits::EvaluationError> {
        let total = config.iter().try_fold(0_i64, |total, &count| {
            let count = i64::try_from(count).map_err(|_| {
                crate::traits::EvaluationError::IntegerOverflow(
                    "converting assigned worker count to i64".into(),
                )
            })?;
            total.checked_add(count).ok_or_else(|| {
                crate::traits::EvaluationError::IntegerOverflow(
                    "summing assigned worker counts".into(),
                )
            })
        })?;
        Ok(total <= self.num_workers)
    }

    fn meets_requirements(&self, config: &[usize]) -> Result<bool, crate::traits::EvaluationError> {
        let mut coverage = vec![0_i64; self.num_periods()];

        for (count, schedule) in config.iter().zip(&self.schedules) {
            if *count == 0 {
                continue;
            }
            let count = i64::try_from(*count).map_err(|_| {
                crate::traits::EvaluationError::IntegerOverflow(
                    "converting scheduled worker count to i64".into(),
                )
            })?;
            for (period, active) in schedule.iter().enumerate() {
                if *active {
                    coverage[period] = coverage[period].checked_add(count).ok_or_else(|| {
                        crate::traits::EvaluationError::IntegerOverflow(
                            "summing staffing coverage".into(),
                        )
                    })?;
                }
            }
        }

        Ok(coverage
            .iter()
            .zip(&self.requirements)
            .all(|(covered, required)| covered >= required))
    }
}

impl Problem for StaffScheduling {
    const NAME: &'static str = "StaffScheduling";
    type Solution = Vec<usize>;
    type Value = crate::types::Or;

    crate::problem_parameters![
        ("num_periods", num_periods),
        ("num_schedules", num_schedules),
        ("num_workers", num_workers),
    ];

    fn evaluate(
        &self,
        config: &Self::Solution,
    ) -> Result<crate::types::Or, crate::traits::EvaluationError> {
        Ok({
            crate::types::Or({
                if config.len() != self.num_schedules() {
                    return Err(crate::traits::EvaluationError::InvalidConfiguration(
                        "staffing vector length does not match the schedules".into(),
                    ));
                }
                self.worker_counts_valid(config)
                    && self.within_budget(config)?
                    && self.meets_requirements(config)?
            })
        })
    }

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

impl crate::solvers::BruteForceProblem for StaffScheduling {
    fn dimensions(&self) -> Vec<usize> {
        vec![self.worker_limit() + 1; self.num_schedules()]
    }
}

crate::declare_variants! {
    default StaffScheduling => "(num_workers + 1)^num_schedules" create StaffSchedulingCreateSpec,
}

crate::register_brute_force! {
    StaffScheduling,
}

#[cfg(feature = "example-db")]
pub(crate) fn canonical_model_example_specs() -> Vec<crate::example_db::specs::ModelExampleSpec> {
    vec![crate::example_db::specs::ModelExampleSpec {
        id: "staff_scheduling",
        instance: Box::new(StaffScheduling::new(
            5,
            vec![
                vec![true, true, true, true, true, false, false],
                vec![false, true, true, true, true, true, false],
                vec![false, false, true, true, true, true, true],
                vec![true, false, false, true, true, true, true],
                vec![true, true, false, false, true, true, true],
            ],
            vec![2, 2, 2, 3, 3, 2, 1],
            4,
        )),
        optimal_config: serde_json::json!(vec![1, 1, 1, 1, 0]),
        optimal_value: serde_json::json!(true),
    }]
}

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