Skip to content

fontanf/shopschedulingsolver

BranchesTags

Repository files navigation

ShopSchedulingSolver

Research code for flow shop, job shop and open shop scheduling problems.

scheduleexample

Usage

Compile the code:

cmake -S . -B build -DCMAKE_BUILD_TYPE=Release cmake --build build --config Release --parallel && cmake --install build --config Release --prefix install

Setup Python environment to use the Python scripts:

python3 -m venv .venv source .venv/bin/activate pip install -r requirements.txt

Download data files:

python scripts/download_data.py

Run:

./install/bin/shopschedulingsolver --verbosity-level 1 --input ./data/vallada2015/Small/VFR10_10_1_Gap.txt --format flow-shop --objective makespan --algorithm tree-search --certificate certificate.json

Visualize solution:

python scripts/visualize.py certificate.json

Implemented algorithms

Permutation flow shop

Objective makespan

$F_m \mid \text{prmu} \mid C_{\max}$

  • Positional MILP --algorithm milp-positional
  • Constraint programming OptalCP --algorithm constraint-programming-optalcp
  • Tree search --algorithm tree-search

$F_m \mid \text{prmu}, \text{mixed no-idle} \mid C_{\max}$

  • Positional MILP --algorithm milp-positional
  • Constraint programming OptalCP --algorithm constraint-programming-optalcp

$F_m \mid \text{prmu}, \text{blocking} \mid C_{\max}$

  • Positional MILP --algorithm milp-positional
  • Constraint programming OptalCP --algorithm constraint-programming-optalcp

Objective total flow time

$F_m \mid \text{prmu} \mid \sum C_j$

  • Positional MILP --algorithm milp-positional
  • Constraint programming OptalCP --algorithm constraint-programming-optalcp
  • Tree search --algorithm tree-search

$F_m \mid \text{prmu}, \text{mixed no-idle} \mid \sum C_j$

  • Positional MILP --algorithm milp-positional
  • Constraint programming OptalCP --algorithm constraint-programming-optalcp

$F_m \mid \text{prmu}, \text{blocking} \mid \sum C_j$

  • Positional MILP --algorithm milp-positional
  • Constraint programming OptalCP --algorithm constraint-programming-optalcp

Objective total tardiness

$F_m \mid \text{prmu} \mid \sum T_j$

  • Positional MILP --algorithm milp-positional
  • Constraint programming OptalCP --algorithm constraint-programming-optalcp

$F_m \mid \text{prmu}, \text{mixed no-idle} \mid \sum T_j$

  • Positional MILP --algorithm milp-positional
  • Constraint programming OptalCP --algorithm constraint-programming-optalcp

$F_m \mid \text{prmu}, \text{blocking} \mid \sum T_j$

  • Positional MILP --algorithm milp-positional
  • Constraint programming OptalCP --algorithm constraint-programming-optalcp

Job shop

Objective makespan

$J_m \mid \mid C_{\max}$

  • Disjunctive MILP --algorithm milp-disjunctive
  • Constraint programming OptalCP --algorithm constraint-programming-optalcp

$J_m \mid \text{no-wait} \mid C_{\max}$

  • Disjunctive MILP --algorithm milp-disjunctive
  • Constraint programming OptalCP --algorithm constraint-programming-optalcp

$J_m \mid \text{mixed no-idle} \mid C_{\max}$

  • Disjunctive MILP --algorithm milp-disjunctive
  • Constraint programming OptalCP --algorithm constraint-programming-optalcp

$J_m \mid \text{blocking} \mid C_{\max}$

  • Disjunctive MILP --algorithm milp-disjunctive
  • Constraint programming OptalCP --algorithm constraint-programming-optalcp

Objective total flow time

$J_m \mid \mid \sum w_j C_j$

  • Disjunctive MILP --algorithm milp-disjunctive
  • Constraint programming OptalCP --algorithm constraint-programming-optalcp

$J_m \mid \text{no-wait} \mid \sum w_j C_j$

  • Disjunctive MILP --algorithm milp-disjunctive
  • Constraint programming OptalCP --algorithm constraint-programming-optalcp

$J_m \mid \text{mixed no-idle} \mid \sum w_j C_j$

  • Disjunctive MILP --algorithm milp-disjunctive
  • Constraint programming OptalCP --algorithm constraint-programming-optalcp

$J_m \mid \text{blocking} \mid \sum w_j C_j$

  • Disjunctive MILP --algorithm milp-disjunctive
  • Constraint programming OptalCP --algorithm constraint-programming-optalcp

Objective total tardiness

$J_m \mid \mid \sum w_j T_j$

  • Disjunctive MILP --algorithm milp-disjunctive
  • Constraint programming OptalCP --algorithm constraint-programming-optalcp

$J_m \mid \text{no-wait} \mid \sum w_j T_j$

  • Disjunctive MILP --algorithm milp-disjunctive
  • Constraint programming OptalCP --algorithm constraint-programming-optalcp

$J_m \mid \text{mixed no-idle} \mid \sum w_j T_j$

  • Disjunctive MILP --algorithm milp-disjunctive
  • Constraint programming OptalCP --algorithm constraint-programming-optalcp

$J_m \mid \text{blocking} \mid \sum w_j T_j$

  • Disjunctive MILP --algorithm milp-disjunctive
  • Constraint programming OptalCP --algorithm constraint-programming-optalcp

Flexible job shop

Objective makespan

$FJ_m \mid \mid C_{\max}$

  • Disjunctive MILP --algorithm milp-disjunctive
  • Constraint programming OptalCP --algorithm constraint-programming-optalcp

$FJ_m \mid \text{no-wait} \mid C_{\max}$

  • Disjunctive MILP --algorithm milp-disjunctive
  • Constraint programming OptalCP --algorithm constraint-programming-optalcp

$FJ_m \mid \text{mixed no-idle} \mid C_{\max}$

  • Disjunctive MILP --algorithm milp-disjunctive
  • Constraint programming OptalCP --algorithm constraint-programming-optalcp

$FJ_m \mid \text{blocking} \mid C_{\max}$

  • Disjunctive MILP --algorithm milp-disjunctive
  • Constraint programming OptalCP --algorithm constraint-programming-optalcp

Objective total flow time

$FJ_m \mid \mid \sum w_j C_j$

  • Disjunctive MILP --algorithm milp-disjunctive
  • Constraint programming OptalCP --algorithm constraint-programming-optalcp

$FJ_m \mid \text{no-wait} \mid \sum w_j C_j$

  • Disjunctive MILP --algorithm milp-disjunctive
  • Constraint programming OptalCP --algorithm constraint-programming-optalcp

$FJ_m \mid \text{mixed no-idle} \mid \sum w_j C_j$

  • Disjunctive MILP --algorithm milp-disjunctive
  • Constraint programming OptalCP --algorithm constraint-programming-optalcp

$FJ_m \mid \text{blocking} \mid \sum w_j C_j$

  • Disjunctive MILP --algorithm milp-disjunctive
  • Constraint programming OptalCP --algorithm constraint-programming-optalcp

Objective total tardiness

$FJ_m \mid \mid \sum w_j T_j$

  • Disjunctive MILP --algorithm milp-disjunctive
  • Constraint programming OptalCP --algorithm constraint-programming-optalcp

$FJ_m \mid \text{no-wait} \mid \sum w_j T_j$

  • Disjunctive MILP --algorithm milp-disjunctive
  • Constraint programming OptalCP --algorithm constraint-programming-optalcp

$FJ_m \mid \text{mixed no-idle} \mid \sum w_j T_j$

  • Disjunctive MILP --algorithm milp-disjunctive
  • Constraint programming OptalCP --algorithm constraint-programming-optalcp

$FJ_m \mid \text{blocking} \mid \sum w_j T_j$

  • Disjunctive MILP --algorithm milp-disjunctive
  • Constraint programming OptalCP --algorithm constraint-programming-optalcp

Open shop

Objective makespan

$O_m \mid \mid C_{\max}$

  • Disjunctive MILP --algorithm milp-disjunctive
  • Constraint programming OptalCP --algorithm constraint-programming-optalcp

$O_m \mid \text{no-wait} \mid C_{\max}$

  • Disjunctive MILP --algorithm milp-disjunctive
  • Constraint programming OptalCP --algorithm constraint-programming-optalcp

$O_m \mid \text{mixed no-idle} \mid C_{\max}$

  • Disjunctive MILP --algorithm milp-disjunctive
  • Constraint programming OptalCP --algorithm constraint-programming-optalcp

$O_m \mid \text{blocking} \mid C_{\max}$

  • Disjunctive MILP --algorithm milp-disjunctive
  • Constraint programming OptalCP --algorithm constraint-programming-optalcp

Objective total flow time

$O_m \mid \mid \sum w_j C_j$

  • Disjunctive MILP --algorithm milp-disjunctive
  • Constraint programming OptalCP --algorithm constraint-programming-optalcp

$O_m \mid \text{no-wait} \mid \sum w_j C_j$

  • Disjunctive MILP --algorithm milp-disjunctive
  • Constraint programming OptalCP --algorithm constraint-programming-optalcp

$O_m \mid \text{mixed no-idle} \mid \sum w_j C_j$

  • Disjunctive MILP --algorithm milp-disjunctive
  • Constraint programming OptalCP --algorithm constraint-programming-optalcp

$O_m \mid \text{blocking} \mid \sum w_j C_j$

  • Disjunctive MILP --algorithm milp-disjunctive
  • Constraint programming OptalCP --algorithm constraint-programming-optalcp

Objective total tardiness

$O_m \mid \mid \sum w_j T_j$

  • Disjunctive MILP --algorithm milp-disjunctive
  • Constraint programming OptalCP --algorithm constraint-programming-optalcp

$O_m \mid \text{no-wait} \mid \sum w_j T_j$

  • Disjunctive MILP --algorithm milp-disjunctive
  • Constraint programming OptalCP --algorithm constraint-programming-optalcp

$O_m \mid \text{mixed no-idle} \mid \sum w_j T_j$

  • Disjunctive MILP --algorithm milp-disjunctive
  • Constraint programming OptalCP --algorithm constraint-programming-optalcp

$O_m \mid \text{blocking} \mid \sum w_j T_j$

  • Disjunctive MILP --algorithm milp-disjunctive
  • Constraint programming OptalCP --algorithm constraint-programming-optalcp

Flexible open shop

Objective makespan

$FO_m \mid \mid C_{\max}$

  • Disjunctive MILP --algorithm milp-disjunctive
  • Constraint programming OptalCP --algorithm constraint-programming-optalcp

$FO_m \mid \text{no-wait} \mid C_{\max}$

  • Disjunctive MILP --algorithm milp-disjunctive
  • Constraint programming OptalCP --algorithm constraint-programming-optalcp

$FO_m \mid \text{mixed no-idle} \mid C_{\max}$

  • Disjunctive MILP --algorithm milp-disjunctive
  • Constraint programming OptalCP --algorithm constraint-programming-optalcp

$FO_m \mid \text{blocking} \mid C_{\max}$

  • Disjunctive MILP --algorithm milp-disjunctive
  • Constraint programming OptalCP --algorithm constraint-programming-optalcp

Objective total flow time

$FO_m \mid \mid \sum w_j C_j$

  • Disjunctive MILP --algorithm milp-disjunctive
  • Constraint programming OptalCP --algorithm constraint-programming-optalcp

$FO_m \mid \text{no-wait} \mid \sum w_j C_j$

  • Disjunctive MILP --algorithm milp-disjunctive
  • Constraint programming OptalCP --algorithm constraint-programming-optalcp

$FO_m \mid \text{mixed no-idle} \mid \sum w_j C_j$

  • Disjunctive MILP --algorithm milp-disjunctive
  • Constraint programming OptalCP --algorithm constraint-programming-optalcp

$FO_m \mid \text{blocking} \mid \sum w_j C_j$

  • Disjunctive MILP --algorithm milp-disjunctive
  • Constraint programming OptalCP --algorithm constraint-programming-optalcp

Objective total tardiness

$FO_m \mid \mid \sum w_j T_j$

  • Disjunctive MILP --algorithm milp-disjunctive
  • Constraint programming OptalCP --algorithm constraint-programming-optalcp

$FO_m \mid \text{no-wait} \mid \sum w_j T_j$

  • Disjunctive MILP --algorithm milp-disjunctive
  • Constraint programming OptalCP --algorithm constraint-programming-optalcp

$FO_m \mid \text{mixed no-idle} \mid \sum w_j T_j$

  • Disjunctive MILP --algorithm milp-disjunctive
  • Constraint programming OptalCP --algorithm constraint-programming-optalcp

$FO_m \mid \text{blocking} \mid \sum w_j T_j$

  • Disjunctive MILP --algorithm milp-disjunctive
  • Constraint programming OptalCP --algorithm constraint-programming-optalcp

Generate test instances list for each algorithm:

python scripts/solve_test_data.py --algorithm milp-positional --output test/algorithms/milp_positional_test.txt --instances \ data/test_pfss_makespan.txt \ data/test_pfss_makespan_no_idle.txt \ data/test_pfss_makespan_blocking.txt \ data/test_pfss_tft.txt \ data/test_pfss_tft_no_idle.txt \ data/test_pfss_tft_blocking.txt \ data/test_pfss_tt.txt \ data/test_pfss_tt_no_idle.txt \ data/test_pfss_tt_blocking.txt python scripts/solve_test_data.py --algorithm milp-disjunctive --output test/algorithms/milp_disjunctive_test.txt --instances \ data/test_jss_makespan.txt \ data/test_jss_makespan_no_wait.txt \ data/test_jss_makespan_blocking.txt \ data/test_jss_tft.txt \ data/test_jss_tft_no_wait.txt \ data/test_jss_tft_blocking.txt \ data/test_jss_twft.txt \ data/test_jss_twft_no_wait.txt \ data/test_jss_twft_blocking.txt \ data/test_jss_tt.txt \ data/test_jss_tt_no_wait.txt \ data/test_jss_tt_blocking.txt \ data/test_jss_twt.txt \ data/test_jss_twt_no_wait.txt \ data/test_jss_twt_blocking.txt \ data/test_fjss_makespan.txt \ data/test_fjss_makespan_no_wait.txt \ data/test_fjss_makespan_blocking.txt \ data/test_fjss_tft.txt \ data/test_fjss_tft_no_wait.txt \ data/test_fjss_tft_blocking.txt \ data/test_fjss_twft.txt \ data/test_fjss_twft_no_wait.txt \ data/test_fjss_twft_blocking.txt \ data/test_fjss_tt.txt \ data/test_fjss_tt_no_wait.txt \ data/test_fjss_tt_blocking.txt \ data/test_fjss_twt.txt \ data/test_fjss_twt_no_wait.txt \ data/test_fjss_twt_blocking.txt \ data/test_oss_makespan.txt \ data/test_oss_makespan_no_wait.txt \ data/test_oss_makespan_blocking.txt \ data/test_oss_tft.txt \ data/test_oss_tft_no_wait.txt \ data/test_oss_tft_blocking.txt \ data/test_oss_twft.txt \ data/test_oss_twft_no_wait.txt \ data/test_oss_twft_blocking.txt \ data/test_oss_tt.txt \ data/test_oss_tt_no_wait.txt \ data/test_oss_tt_blocking.txt \ data/test_oss_twt.txt \ data/test_oss_twt_no_wait.txt \ data/test_oss_twt_blocking.txt \ data/test_foss_makespan.txt \ data/test_foss_makespan_no_wait.txt \ data/test_foss_makespan_blocking.txt \ data/test_foss_tft.txt \ data/test_foss_tft_no_wait.txt \ data/test_foss_tft_blocking.txt \ data/test_foss_twft.txt \ data/test_foss_twft_no_wait.txt \ data/test_foss_twft_blocking.txt \ data/test_foss_tt.txt \ data/test_foss_tt_no_wait.txt \ data/test_foss_tt_blocking.txt \ data/test_foss_twt.txt \ data/test_foss_twt_no_wait.txt \ data/test_foss_twt_blocking.txt python scripts/solve_test_data.py --algorithm constraint-programming-optalcp --output test/algorithms/constraint_programming_optalcp_test.txt --instances \ data/test_pfss_makespan.txt \ data/test_pfss_makespan_no_idle.txt \ data/test_pfss_makespan_blocking.txt \ data/test_pfss_tft.txt \ data/test_pfss_tft_no_idle.txt \ data/test_pfss_tft_blocking.txt \ data/test_pfss_tt.txt \ data/test_pfss_tt_no_idle.txt \ data/test_pfss_tt_blocking.txt \ data/test_jss_makespan.txt \ data/test_jss_makespan_no_wait.txt \ data/test_jss_makespan_blocking.txt \ data/test_jss_tft.txt \ data/test_jss_tft_no_wait.txt \ data/test_jss_tft_blocking.txt \ data/test_jss_twft.txt \ data/test_jss_twft_no_wait.txt \ data/test_jss_twft_blocking.txt \ data/test_jss_tt.txt \ data/test_jss_tt_no_wait.txt \ data/test_jss_tt_blocking.txt \ data/test_jss_twt.txt \ data/test_jss_twt_no_wait.txt \ data/test_jss_twt_blocking.txt \ data/test_fjss_makespan.txt \ data/test_fjss_makespan_no_wait.txt \ data/test_fjss_makespan_blocking.txt \ data/test_fjss_tft.txt \ data/test_fjss_tft_no_wait.txt \ data/test_fjss_tft_blocking.txt \ data/test_fjss_twft.txt \ data/test_fjss_twft_no_wait.txt \ data/test_fjss_twft_blocking.txt \ data/test_fjss_tt.txt \ data/test_fjss_tt_no_wait.txt \ data/test_fjss_tt_blocking.txt \ data/test_fjss_twt.txt \ data/test_fjss_twt_no_wait.txt \ data/test_fjss_twt_blocking.txt \ data/test_oss_makespan.txt \ data/test_oss_makespan_no_wait.txt \ data/test_oss_makespan_blocking.txt \ data/test_oss_tft.txt \ data/test_oss_tft_no_wait.txt \ data/test_oss_tft_blocking.txt \ data/test_oss_twft.txt \ data/test_oss_twft_no_wait.txt \ data/test_oss_twft_blocking.txt \ data/test_oss_tt.txt \ data/test_oss_tt_no_wait.txt \ data/test_oss_tt_blocking.txt \ data/test_oss_twt.txt \ data/test_oss_twt_no_wait.txt \ data/test_oss_twt_blocking.txt \ data/test_foss_makespan.txt \ data/test_foss_makespan_no_wait.txt \ data/test_foss_makespan_blocking.txt \ data/test_foss_tft.txt \ data/test_foss_tft_no_wait.txt \ data/test_foss_tft_blocking.txt \ data/test_foss_twft.txt \ data/test_foss_twft_no_wait.txt \ data/test_foss_twft_blocking.txt \ data/test_foss_tt.txt \ data/test_foss_tt_no_wait.txt \ data/test_foss_tt_blocking.txt \ data/test_foss_twt.txt \ data/test_foss_twt_no_wait.txt \ data/test_foss_twt_blocking.txt python scripts/solve_test_data.py --algorithm tree-search-pfss-makespan --output test/algorithms/tree_search_pfss_makespan_test.txt --instances \ data/test_pfss_makespan.txt python scripts/solve_test_data.py --algorithm tree-search-pfss-tft --output test/algorithms/tree_search_pfss_tft_test.txt --instances \ data/test_pfss_tft.txt cmake --build build --config Release --target clean cmake --build build --config Release --parallel && cmake --install build --config Release --prefix install ctest --parallel --output-on-failure --test-dir build/test

About

Research code for flow shop, job shop and open shop scheduling problems

Topics

scheduling job-shop flow-shop jobshop jobshop-scheduling job-shop-scheduling-problem flowshop job-shop-scheduling permutation-flowshop open-shop flowshop-problem job-shop-problem flowshop-scheduling open-shop-scheduling-problem flexible-job-shop-scheduling flexible-job-shop permutation-flow-shop flexible-job-shop-problem flow-shop-scheduling-problem flow-shop-scheduling

Resources

Readme

License

MIT license
Activity

Stars

4 stars

Watchers

0 watching

Forks

0 forks
Report repository

Releases

No releases published

Packages

 
 
 

Contributors

Languages