Use evolutionary solver to assign Jobs to Machines in a factory.

main.rs

//! Factory scheduling

use std::collections::HashMap;

use galapagos::{Config, Goal};
use rand::{thread_rng, Rng};
use textplots::{Chart, Plot};

type JobId = i32;
type MacId = i32;

#[derive(Debug)]
struct Job {
    id: JobId,
    duration_hrs: f32,
    due_in_hrs: f32,
}

#[derive(Debug)]
struct Schedule {
    machines: Vec<Vec<Job>>,
}

// Simulating factory data that would be available somewhere like a data
// warehouse.
#[derive(Debug)]
struct Database {
    duration_hrs: Vec<f32>,
    due_in_hrs: Vec<f32>,
}

const JOB_COUNT: i32 = 50;
const MACHINE_COUNT: i32 = 20;

fn decode(db: &Database, xs: &[f32]) -> Schedule {
    // First five values are machine sort IDs
    let sort = &xs[..JOB_COUNT as usize];
    let mut jobs: Vec<(JobId, f32)> = (0..JOB_COUNT).map(|i| (i, sort[i as usize])).collect();
    jobs.sort_by(|x, y| x.1.partial_cmp(&y.1).unwrap());

    // Next five values are machine assignments
    let asgt = &xs[JOB_COUNT as usize..];
    // Maps Job ID to Machine ID
    let job_asgt: HashMap<JobId, MacId> = (0..JOB_COUNT)
        .map(|i| (i, (asgt[i as usize] * (MACHINE_COUNT - 1) as f32).floor() as i32))
        .collect::<HashMap<_, _>>();
    let mut machines = Vec::with_capacity(MACHINE_COUNT as usize);
    for _ in 0..MACHINE_COUNT {
        machines.push(Vec::with_capacity(jobs.len()));
    }

    for (job, _) in jobs.into_iter() {
        match job_asgt.get(&job) {
            Some(x) => {
                if true {
                    machines[*x as usize].push(Job {
                        id: job + 1,
                        duration_hrs: db.duration_hrs[job as usize],
                        due_in_hrs: db.due_in_hrs[job as usize],
                    })
                } else {
                    unreachable!("Unsupported Machine ID: {x:?}");
                }
            }
            None => {
                unreachable!("Every job should be assignment to a machine");
            }
        }
    }

    Schedule { machines }
}

fn makespan(schedule: &Schedule) -> f32 {
    // calculate make span
    let mut spans = Vec::with_capacity(MACHINE_COUNT as usize);
    for i in 0..MACHINE_COUNT {
        let span: f32 = schedule.machines[i as usize].iter().map(|x| x.duration_hrs).sum();
        spans.push(span);
    }
    spans.into_iter().max_by(|x, y| x.partial_cmp(&y).unwrap()).unwrap()
}

fn lateness(schedule: &Schedule) -> f32 {
    let mut result = 0.0;
    for jobs in schedule.machines.iter() {
        let mut ends = vec![0.0; jobs.len() + 1];
        for (i, job) in jobs.iter().enumerate() {
            // previous job's end time plus job-duration
            ends[i + 1] = ends[i] + job.duration_hrs;
            result += ends[i + 1] - job.duration_hrs;
        }
    }
    result
}

fn throughput(schedule: &Schedule) -> f32 {
    let num_jobs = schedule.machines.iter()
        .map(|jobs| jobs.len())
        .fold(0, |acc, x| acc + x);
    let total_time = schedule.machines.iter()
        .map(|jobs| jobs.iter().fold(0.0, |acc, x| acc + x.duration_hrs))
        .fold(0.0, |acc, x| acc + x);
    num_jobs as f32 / total_time as f32
}

fn format_schedule(schedule: &Schedule) -> String {
    let mut strings = Vec::with_capacity(MACHINE_COUNT as usize);
    for i in 0..MACHINE_COUNT {
        let string = schedule.machines[i as usize].iter().map(|x| format!("J{} ({:.1}h)", x.id, x.duration_hrs)).collect::<Vec<_>>().join(", ");
        strings.push(format!("M{}: {}", i + 1, string));
    }
    let ms = makespan(&schedule);
    let lt = lateness(&schedule);
    let tp = throughput(&schedule);
    [
        format!("{}", strings.join("\n")),
        format!("Makespan: {ms:.1}h"),
        format!("Lateness: {lt:.1}h"),
        format!("Throughput: {tp:.1} QPS"),
    ].join("\n")
}

fn main() {
    // generate data at runtime
    let mut rng = thread_rng();
    let db = Database {
        duration_hrs: (0..JOB_COUNT).map(|_| rng.gen_range(1.0..=4.5)).collect(),
        due_in_hrs: (0..JOB_COUNT).map(|_| rng.gen_range(1.0..=48.0)).collect(),
    };

    let mut sliders = Vec::with_capacity(MACHINE_COUNT as usize);
    let jobs = (0..JOB_COUNT).map(|_| (0.0, 1.0)).collect::<Vec<_>>();
    let machines = (0..JOB_COUNT).map(|_| (0.0, 1.0)).collect::<Vec<_>>();
    sliders.extend_from_slice(&jobs);
    sliders.extend_from_slice(&machines);

    let solution = galapagos::solve(
        |xs| {
            let schedule = decode(&db, xs);
            lateness(&schedule)
        },
        &sliders,
        Goal::Minimize,
        Config {
            population_size: 250,
            generation_count: 500,
            record_history: true,
            print_progress: true,
            ..Default::default()
        },

    );
    let downsample = 0.10;
    let history = solution.history.unwrap()
        .into_iter()
        .step_by((1.0 / downsample as f32).ceil() as usize)
        .collect::<Vec<_>>();

    Chart::new(120, 40, 0.0, history.len() as f32 / downsample)
        .lineplot(&textplots::Shape::Lines(&history))
        .nice();

    let schedule = decode(&db, &solution.champion.values[..]);
    println!("{}", &format_schedule(&schedule));
}