BatchSchedulingSolver

Research code for batch scheduling problems.

Compilation

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/batchschedulingsolver  --verbosity-level 1  --input ./data/alfieri2021/inst_10_1_1.dat --format alfieri2021  --algorithm greedy-longest-processing-time  --certificate solution.json

Visualize solution:

python scripts/visualize.py solution.json

Implemented algorithms

$1 \mid \text{p-batch}, \text{size}_j \mid C_{\max}$

• Greedy, longest processing-time greedy-longest-processing-time

$P_m \mid \text{p-batch}, B_i, \text{size}_j \mid C_{\max}$

• MILP, three-index milp-rank-based-three-index-no-starts
• MILP, two-index milp-rank-based-two-index-no-starts

$P_m \mid \text{p-batch}, B_i, \text{size}_j, r_j \mid C_{\max}$

• MILP, three-index milp-rank-based-three-index
• MILP, two-index milp-rank-based-two-index

$R_m \mid \text{p-batch}, B_i, \text{size}_j \mid C_{\max}$

• MILP, three-index milp-rank-based-three-index-no-starts

$R_m \mid \text{p-batch}, B_i, \text{size}_j, r_j \mid C_{\max}$

• MILP, three-index milp-rank-based-three-index

$R_m \mid \text{p-batch}, B_i, \text{size}_j, r_j \mid \sum w_j C_j$

• MILP, three-index milp-rank-based-three-index

$R_m \mid \text{p-batch}, B_i, \text{size}_j, r_j \mid \sum w_j T_j$

• MILP, three-index milp-rank-based-three-index

Generate test instances list for each algorithm:

python scripts/solve_test_data.py  --algorithm greedy-longest-processing-time  --output test/algorithms/greedy_longest_processing_time_test.txt  --instances \
        data/test_makespan_identical_sizes.txt
python scripts/solve_test_data.py  --algorithm milp-rank-based-three-index-no-starts  --output test/algorithms/milp_rank_based_three_index_no_starts_test.txt  --instances \
        data/test_makespan_single.txt \
        data/test_makespan_parallel.txt \
        data/test_makespan_unrelated.txt
python scripts/solve_test_data.py  --algorithm milp-rank-based-three-index  --output test/algorithms/milp_rank_based_three_index_test.txt  --instances \
        data/test_makespan_single.txt \
        data/test_makespan_single_release_dates.txt \
        data/test_makespan_parallel.txt \
        data/test_makespan_parallel_release_dates.txt \
        data/test_makespan_unrelated.txt \
        data/test_makespan_unrelated_release_dates.txt \
        data/test_tft_single.txt \
        data/test_tft_single_release_dates.txt \
        data/test_tft_parallel.txt \
        data/test_tft_parallel_release_dates.txt \
        data/test_tft_unrelated.txt \
        data/test_tft_unrelated_release_dates.txt \
        data/test_twft_single.txt \
        data/test_twft_single_release_dates.txt \
        data/test_twft_parallel.txt \
        data/test_twft_parallel_release_dates.txt \
        data/test_twft_unrelated.txt \
        data/test_twft_unrelated_release_dates.txt \
        data/test_tt_single.txt \
        data/test_tt_single_release_dates.txt \
        data/test_tt_parallel.txt \
        data/test_tt_parallel_release_dates.txt \
        data/test_tt_unrelated.txt \
        data/test_tt_unrelated_release_dates.txt \
        data/test_twt_single.txt \
        data/test_twt_single_release_dates.txt \
        data/test_twt_parallel.txt \
        data/test_twt_parallel_release_dates.txt \
        data/test_twt_unrelated.txt \
        data/test_twt_unrelated_release_dates.txt
python scripts/solve_test_data.py  --algorithm milp-rank-based-two-index-no-starts  --output test/algorithms/milp_rank_based_two_index_no_starts_test.txt  --instances \
        data/test_makespan_single.txt \
        data/test_makespan_parallel.txt
python scripts/solve_test_data.py  --algorithm milp-rank-based-two-index  --output test/algorithms/milp_rank_based_two_index_test.txt  --instances \
        data/test_makespan_single.txt \
        data/test_makespan_single_release_dates.txt \
        data/test_makespan_parallel.txt \
        data/test_makespan_parallel_release_dates.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