Fix #507: Add FlowShopScheduling model by zazabap · Pull Request #629 · CodingThrust/problem-reductions

zazabap · 2026-03-13T08:38:18Z

Summary

Add the FlowShopScheduling satisfaction problem model — a classic NP-complete scheduling problem from Garey & Johnson (A5 SS15).

Given m processors and n jobs (each consisting of m tasks that must be processed in fixed processor order), determine if all jobs can complete by a global deadline D.

Fixes #507

Co-Authored-By: Claude Opus 4.6 <[email protected]>

zazabap · 2026-03-13T08:45:53Z

Implementation Summary

Changes

src/models/misc/flow_shop_scheduling.rs — New FlowShopScheduling satisfaction problem model. Encodes the classic flow-shop scheduling decision problem: given m processors, n jobs (each with m tasks in fixed processor order), and deadline D, determine if a feasible schedule exists. Uses permutation encoding (config[job] = position in sequence).
src/unit_tests/models/misc/flow_shop_scheduling.rs — 12 unit tests covering creation, feasible/infeasible evaluation, invalid configs (non-permutation), serialization, brute-force solver (satisfiable + unsatisfiable), edge cases (empty, single job), and makespan computation.
src/models/misc/mod.rs — Register module and re-export.
src/models/mod.rs — Add FlowShopScheduling to misc re-exports.
src/lib.rs — Add to prelude.
problemreductions-cli/src/dispatch.rs — Add load_problem and serialize_any_problem entries (satisfaction problem).
problemreductions-cli/src/problem_name.rs — Add lowercase alias mapping.
problemreductions-cli/src/commands/create.rs — Add creation handler with --task-lengths and --deadline flags (reuses --m for num_processors).
problemreductions-cli/src/cli.rs — Add --task-lengths and --deadline flags, update help table.

Deviations from Plan

None

Open Questions

None

codecov · 2026-03-13T08:48:15Z

Codecov Report

❌ Patch coverage is 98.12500% with 3 lines in your changes missing coverage. Please review.
✅ Project coverage is 96.82%. Comparing base (3811aff) to head (8f99365).
⚠️ Report is 1 commits behind head on main.

Files with missing lines	Patch %	Lines
src/models/misc/flow_shop_scheduling.rs	95.58%	3 Missing ⚠️

Additional details and impacted files

@@           Coverage Diff            @@
##             main     #629    +/-   ##
========================================
  Coverage   96.81%   96.82%            
========================================
  Files         240      242     +2     
  Lines       31305    31464   +159     
========================================
+ Hits        30308    30464   +156     
- Misses        997     1000     +3

☔ View full report in Codecov by Sentry.
📢 Have feedback on the report? Share it here.

🚀 New features to boost your workflow:

❄️ Test Analytics: Detect flaky tests, report on failures, and find test suite problems.

Copilot

Pull request overview

Adds a new FlowShopScheduling satisfaction model (G&J A5 SS15) and wires it through the library exports, CLI dispatch/creation, and unit tests so instances can be created/serialized/solved via existing solvers.

Changes:

Introduce FlowShopScheduling model with schema registration, evaluation, and makespan computation.
Add unit tests covering creation, evaluation, makespan, (de)serialization, and brute-force solving.
Integrate the model into public exports and the CLI (alias resolution, dispatch load/serialize, pred create flags).

Reviewed changes

Copilot reviewed 9 out of 9 changed files in this pull request and generated 7 comments.

Show a summary per file

File	Description
`src/models/misc/flow_shop_scheduling.rs`	New model implementation + schema registration + variants metadata + tests module hookup.
`src/unit_tests/models/misc/flow_shop_scheduling.rs`	New unit tests for the model (valid/invalid configs, makespan, solver).
`src/models/misc/mod.rs`	Register module and re-export `FlowShopScheduling` from `misc`.
`src/models/mod.rs`	Re-export `FlowShopScheduling` from top-level `models`.
`src/lib.rs`	Add `FlowShopScheduling` to the public prelude re-exports.
`problemreductions-cli/src/problem_name.rs`	Add alias resolution for `flowshopscheduling`.
`problemreductions-cli/src/dispatch.rs`	Add CLI load/serialize dispatch arms for `FlowShopScheduling`.
`problemreductions-cli/src/commands/create.rs`	Add `pred create FlowShopScheduling` parsing and instance construction.
`problemreductions-cli/src/cli.rs`	Add `--task-lengths` and `--deadline` flags to `CreateArgs` and help text.

💡 Add Copilot custom instructions for smarter, more guided reviews. Learn how to get started.

problemreductions-cli/src/commands/create.rs

+            let task_lengths: Vec<Vec<u64>> = task_str
+                .split(';')
+                .map(|row| util::parse_comma_list(row.trim()))
+                .collect::<Result<Vec<_>>>()?;
+            let num_processors = if let Some(m) = args.m {
+                m
+            } else if let Some(first) = task_lengths.first() {
+                first.len()
+            } else {
+                bail!("Cannot infer num_processors from empty task list; use --m");
+            };
+            (
+                ser(FlowShopScheduling::new(num_processors, task_lengths, deadline))?,
+                resolved_variant.clone(),
+            )


src/unit_tests/models/misc/flow_shop_scheduling.rs

+fn test_flow_shop_scheduling_evaluate_infeasible() {
+    // Same instance, tight deadline of 22 (below the best makespan of 23)
+    let problem = FlowShopScheduling::new(
+        3,
+        vec![
+            vec![3, 4, 2],
+            vec![2, 3, 5],
+            vec![4, 1, 3],
+            vec![1, 5, 4],
+            vec![3, 2, 3],
+        ],
+        15, // Very tight deadline, likely infeasible
+    );


problemreductions-cli/src/commands/create.rs

+        // FlowShopScheduling
+        "FlowShopScheduling" => {
+            let task_str = args.task_lengths.as_deref().ok_or_else(|| {
+                anyhow::anyhow!(
+                    "FlowShopScheduling requires --task-lengths and --deadline\n\n\
+                     Usage: pred create FlowShopScheduling --task-lengths \"3,4,2;2,3,5;4,1,3\" --deadline 25 --m 3"
+                )
+            })?;
+            let deadline = args.deadline.ok_or_else(|| {
+                anyhow::anyhow!(
+                    "FlowShopScheduling requires --deadline\n\n\
+                     Usage: pred create FlowShopScheduling --task-lengths \"3,4,2;2,3,5;4,1,3\" --deadline 25 --m 3"
+                )
+            })?;
+            let task_lengths: Vec<Vec<u64>> = task_str
+                .split(';')
+                .map(|row| util::parse_comma_list(row.trim()))
+                .collect::<Result<Vec<_>>>()?;
+            let num_processors = if let Some(m) = args.m {
+                m
+            } else if let Some(first) = task_lengths.first() {
+                first.len()
+            } else {
+                bail!("Cannot infer num_processors from empty task list; use --m");
+            };
+            (
+                ser(FlowShopScheduling::new(num_processors, task_lengths, deadline))?,
+                resolved_variant.clone(),
+            )


src/models/misc/flow_shop_scheduling.rs

+impl SatisfactionProblem for FlowShopScheduling {}
+
+crate::declare_variants! {
+    FlowShopScheduling => "3^num_jobs",


src/models/misc/flow_shop_scheduling.rs

+    fn dims(&self) -> Vec<usize> {
+        let n = self.num_jobs();
+        vec![n; n]
+    }


src/models/misc/flow_shop_scheduling.rs

+    /// Compute the makespan for a given job ordering.
+    ///
+    /// The job_order slice must be a permutation of `0..num_jobs`.
+    /// Returns the completion time of the last job on the last machine.
+    pub fn compute_makespan(&self, job_order: &[usize]) -> u64 {
+        let n = job_order.len();
+        let m = self.num_processors;
+        if n == 0 || m == 0 {
+            return 0;
+        }
+
+        // completion[k][i] = completion time of the k-th job in sequence on machine i
+        let mut completion = vec![vec![0u64; m]; n];
+
+        for (k, &job) in job_order.iter().enumerate() {
+            for i in 0..m {
+                let prev_machine = if i == 0 { 0 } else { completion[k][i - 1] };
+                let prev_job = if k == 0 { 0 } else { completion[k - 1][i] };
+                let start = prev_machine.max(prev_job);
+                completion[k][i] = start + self.task_lengths[job][i];
+            }


problemreductions-cli/src/commands/create.rs

+                     Usage: pred create FlowShopScheduling --task-lengths \"3,4,2;2,3,5;4,1,3\" --deadline 25 --m 3"
+                )
+            })?;
+            let deadline = args.deadline.ok_or_else(|| {
+                anyhow::anyhow!(
+                    "FlowShopScheduling requires --deadline\n\n\
+                     Usage: pred create FlowShopScheduling --task-lengths \"3,4,2;2,3,5;4,1,3\" --deadline 25 --m 3"
+                )
+            })?;
+            let task_lengths: Vec<Vec<u64>> = task_str
+                .split(';')
+                .map(|row| util::parse_comma_list(row.trim()))
+                .collect::<Result<Vec<_>>>()?;
+            let num_processors = if let Some(m) = args.m {
+                m
+            } else if let Some(first) = task_lengths.first() {
+                first.len()
+            } else {
+                bail!("Cannot infer num_processors from empty task list; use --m");


…eduling # Conflicts: # problemreductions-cli/src/commands/create.rs # problemreductions-cli/src/dispatch.rs # src/lib.rs # src/models/mod.rs

- Switch dims() from vec![n;n] to Lehmer code encoding [n,n-1,...,1] - Update evaluate() to decode Lehmer code into permutations - Fix complexity from "3^num_jobs" to "num_jobs^num_jobs" - Add validation to compute_makespan() for out-of-bounds indices - Add --num-processors CLI flag instead of overloading --m - Validate task_lengths row lengths in CLI with bail! instead of panic - Fix test comment about deadline value Co-Authored-By: Claude Opus 4.6 <[email protected]>

Add concrete example of how Lehmer code configs map to job orderings in the struct doc comment, improving discoverability for new users. Co-Authored-By: Claude Opus 4.6 <[email protected]>

Fixes clippy::unused_enumerate_index warning. Co-Authored-By: Claude Opus 4.6 <[email protected]>

zazabap · 2026-03-13T15:40:52Z

Review Pipeline Report

Check	Result
Merge conflicts	resolved (4 files)
Copilot comments	7 addressed (Lehmer encoding, complexity, validation, CLI flags, docs)
Issue/human comments	2 checked, 0 actionable
CI	green (1 clippy fix)
Agentic test	passed
Board	review-agentic → In Review

Changes made:

Resolved merge conflicts with main (LongestCommonSubsequence, SubgraphIsomorphism, PartitionIntoTriangles)
Switched dims() from vec![n;n] to Lehmer code encoding [n, n-1, ..., 1]
Updated evaluate() to decode Lehmer codes into permutations
Fixed complexity from 3^num_jobs to num_jobs^num_jobs
Added validation to compute_makespan() for out-of-bounds indices
Added --num-processors CLI flag (avoids overloading --m)
Added row-length validation in CLI with bail! instead of panic
Added Lehmer code encoding explanation to struct doc comment
Fixed clippy unused_enumerate_index warning

🤖 Generated by review-pipeline

…complexity - Add FlowShopScheduling problem-def and display-name to docs/paper/reductions.typ - Add FlowShopScheduling to trait_consistency test - Fix complexity from "num_jobs^num_jobs" to "factorial(num_jobs)" (n! is the exact search space) - Relax check_problem_trait assertion from >= 2 to >= 1 (Lehmer code encoding produces trailing dim of 1) Co-Authored-By: Claude Opus 4.6 <[email protected]>

…paper Replace the simple 2-machine example with the issue's canonical 3-machine, 5-job example. Add a CeTZ Gantt chart showing the feasible schedule with job order (j4, j1, j5, j3, j2) achieving makespan 23 within deadline 25. Co-Authored-By: Claude Opus 4.6 <[email protected]>

Resolve conflicts with ShortestCommonSupersequence model added on main. Keep both FlowShopScheduling and SCS in all import/dispatch/CLI locations. Co-Authored-By: Claude Opus 4.6 <[email protected]>

* Add plan for #244: [Model] IsomorphicSpanningTree Co-Authored-By: Claude Opus 4.6 <[email protected]> * feat: add IsomorphicSpanningTree satisfaction problem model (#244) Implements the Isomorphic Spanning Tree decision problem: given a graph G and a tree T with |V(G)| = |V(T)|, determine if G contains a spanning tree isomorphic to T. NP-complete (Garey & Johnson ND8). - Model with SatisfactionProblem (Metric = bool), permutation-based config - Constructor validates tree connectivity and edge count - CLI support with --graph and --tree flags - 11 unit tests covering evaluation, solver, serialization, edge cases Co-Authored-By: Claude Opus 4.6 <[email protected]> * chore: remove plan file after implementation Co-Authored-By: Claude Opus 4.6 <[email protected]> * Fix #412: Add ShortestCommonSupersequence model (#627) * Add plan for #412: ShortestCommonSupersequence model * Implement #412: Add ShortestCommonSupersequence model * style: apply rustfmt formatting * Address review: fix docs, add --alphabet-size flag, add edge case tests * chore: remove plan file after implementation * Address Copilot review comments - Align docs/schema wording: bound is exact config length, equivalent to |w| ≤ B via padding - Add alphabet_size > 0 validation in constructor - Handle empty string segments in --strings CLI parsing - Add --alphabet-size to CLI help text - Regenerate problem_schemas.json Co-Authored-By: Claude Opus 4.6 <[email protected]> * Fix agentic test issues: add SCS to prelude, fix CLI duplicate fields - Add ShortestCommonSupersequence to prelude re-exports (was missing unlike all other misc models) - Fix duplicate CLI struct fields (strings, bound) by sharing between LCS/SCS and RuralPostman/SCS with i64 type and casts at usage sites Co-Authored-By: Claude Opus 4.6 <[email protected]> * chore: trigger CI Co-Authored-By: Claude Opus 4.6 <[email protected]> * style: apply rustfmt formatting Co-Authored-By: Claude Opus 4.6 <[email protected]> --------- Co-authored-by: Claude Opus 4.6 <[email protected]> Co-authored-by: GiggleLiu <[email protected]> * Fix #507: Add FlowShopScheduling model (#629) * Add plan for #507: FlowShopScheduling model * Implement #507: Add FlowShopScheduling model Co-Authored-By: Claude Opus 4.6 <[email protected]> * chore: remove plan file after implementation * fix: address Copilot review comments on FlowShopScheduling - Switch dims() from vec![n;n] to Lehmer code encoding [n,n-1,...,1] - Update evaluate() to decode Lehmer code into permutations - Fix complexity from "3^num_jobs" to "num_jobs^num_jobs" - Add validation to compute_makespan() for out-of-bounds indices - Add --num-processors CLI flag instead of overloading --m - Validate task_lengths row lengths in CLI with bail! instead of panic - Fix test comment about deadline value Co-Authored-By: Claude Opus 4.6 <[email protected]> * docs: add Lehmer code encoding explanation to FlowShopScheduling Add concrete example of how Lehmer code configs map to job orderings in the struct doc comment, improving discoverability for new users. Co-Authored-By: Claude Opus 4.6 <[email protected]> * fix: remove unused enumerate in Lehmer code decoding Fixes clippy::unused_enumerate_index warning. Co-Authored-By: Claude Opus 4.6 <[email protected]> * fix: add missing paper section, trait_consistency entry, and correct complexity - Add FlowShopScheduling problem-def and display-name to docs/paper/reductions.typ - Add FlowShopScheduling to trait_consistency test - Fix complexity from "num_jobs^num_jobs" to "factorial(num_jobs)" (n! is the exact search space) - Relax check_problem_trait assertion from >= 2 to >= 1 (Lehmer code encoding produces trailing dim of 1) Co-Authored-By: Claude Opus 4.6 <[email protected]> * docs: add Gantt chart visualization and use issue's 5-job example in paper Replace the simple 2-machine example with the issue's canonical 3-machine, 5-job example. Add a CeTZ Gantt chart showing the feasible schedule with job order (j4, j1, j5, j3, j2) achieving makespan 23 within deadline 25. Co-Authored-By: Claude Opus 4.6 <[email protected]> --------- Co-authored-by: Claude Opus 4.6 <[email protected]> Co-authored-by: GiggleLiu <[email protected]> * Add paper section, trait_consistency entry, and formatting fixes for IsomorphicSpanningTree - Add display-name and problem-def entry in docs/paper/reductions.typ with formal definition, background (Garey & Johnson ND8), and CeTZ figure - Add bibliography entry for Papadimitriou & Yannakakis 1982 - Add check_problem_trait for IsomorphicSpanningTree in trait_consistency.rs - Apply cargo fmt formatting fixes from merge Co-Authored-By: Claude Opus 4.6 <[email protected]> --------- Co-authored-by: Claude Opus 4.6 <[email protected]> Co-authored-by: GiggleLiu <[email protected]>

zazabap and others added 3 commits March 13, 2026 08:38

Add plan for #507: FlowShopScheduling model

043edd9

Implement #507: Add FlowShopScheduling model

5239ba2

Co-Authored-By: Claude Opus 4.6 <[email protected]>

chore: remove plan file after implementation

a1aebc4

zazabap requested a review from Copilot March 13, 2026 14:57

Copilot started reviewing on behalf of zazabap March 13, 2026 14:58 View session

Copilot AI reviewed Mar 13, 2026

View reviewed changes

zazabap and others added 4 commits March 13, 2026 15:18

Merge remote-tracking branch 'origin/main' into issue-507-flowshopsch…

4edd0b1

…eduling # Conflicts: # problemreductions-cli/src/commands/create.rs # problemreductions-cli/src/dispatch.rs # src/lib.rs # src/models/mod.rs

docs: add Lehmer code encoding explanation to FlowShopScheduling

52e8ca0

Add concrete example of how Lehmer code configs map to job orderings in the struct doc comment, improving discoverability for new users. Co-Authored-By: Claude Opus 4.6 <[email protected]>

fix: remove unused enumerate in Lehmer code decoding

03ce50f

Fixes clippy::unused_enumerate_index warning. Co-Authored-By: Claude Opus 4.6 <[email protected]>

GiggleLiu and others added 4 commits March 14, 2026 01:48

Merge origin/main into issue-507-flowshopscheduling

0167cca

Merge origin/main into issue-507-flowshopscheduling

8f99365

Resolve conflicts with ShortestCommonSupersequence model added on main. Keep both FlowShopScheduling and SCS in all import/dispatch/CLI locations. Co-Authored-By: Claude Opus 4.6 <[email protected]>

GiggleLiu merged commit 1a923f0 into main Mar 13, 2026
5 checks passed

GiggleLiu deleted the issue-507-flowshopscheduling branch April 12, 2026 00:53

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

Fix #507: Add FlowShopScheduling model#629

Fix #507: Add FlowShopScheduling model#629
GiggleLiu merged 11 commits intomainfrom
issue-507-flowshopscheduling

zazabap commented Mar 13, 2026

Uh oh!

zazabap commented Mar 13, 2026

Uh oh!

codecov bot commented Mar 13, 2026 •

edited

Loading

Uh oh!

Copilot AI left a comment

Uh oh!

zazabap commented Mar 13, 2026

Uh oh!

Uh oh!

Reviewers

Assignees

Labels

Projects

Milestone

Development

Uh oh!

3 participants

Conversation

zazabap commented Mar 13, 2026

Summary

Uh oh!

zazabap commented Mar 13, 2026

Implementation Summary

Changes

Deviations from Plan

Open Questions

Uh oh!

codecov bot commented Mar 13, 2026 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Codecov Report

Uh oh!

Copilot AI left a comment

Choose a reason for hiding this comment

Pull request overview

Reviewed changes

Uh oh!

zazabap commented Mar 13, 2026

Review Pipeline Report

Changes made:

Uh oh!

Uh oh!

Reviewers

Assignees

Labels

Projects

Milestone

Development

Uh oh!

3 participants

codecov bot commented Mar 13, 2026 •

edited

Loading