CS202 Project: Optimising Resource-Constrained Scheduling

Python implementation of a heuristic solver for the RCPSP group project.

The repository now also includes an exact branch-and-bound solver for proving optimality

Team: G1T2

• Chai Yi Khuen (01469570)
• Chong Wei Choon (01485701)
• Lau Wei Bin (01469625)
• Win Lei Thawdar (01513787)
• Yeo Ben Shin (01479845)

Repository Layout

Solver entry points

• scripts/solvers/rcpsp_solver.py: heuristic RCPSP solver for one instance
• scripts/solvers/eval_fast.py: fast batch evaluator for the heuristic solver
• scripts/solvers/optimal_rcpsp.py: exact branch-and-bound solver for one instance
• scripts/solvers/batch_optimal_updated.py: batch runner for the exact solver on data/updated
• scripts/solvers/compare_solvers.py: runs both solvers and writes a comparison CSV

PSPLIB utilities

• scripts/psplib/download_psplib.py: downloads and extracts held-out PSPLIB archives
• scripts/psplib/convert_psplib_sm.py: flattens extracted .sm archives into instance folders
• scripts/psplib/eval_psplib.py: evaluates the solver on held-out PSPLIB instances
• scripts/psplib/summarize_psplib.py: summarizes held-out PSPLIB results against references

Shared solver code

• helpers/parser.py: parses .SCH / .sm instance files
• helpers/solver.py: heuristic search and schedule construction
• helpers/exact_solver.py: exact branch-and-bound search engine
• helpers/validator.py: schedule validation and output formatting
• helpers/instance.py: RCPSP instance data model
• helpers/helper.py: low-level feasibility and scheduling helpers

Data folders

• data/updated/: current benchmark instances used by the main solver workflows
• data/updated/sm_j10/: updated J10 instances with 10 real jobs plus source/sink
• data/updated/sm_j20/: updated J20 instances with 20 real jobs plus source/sink
• data/old/: older benchmark copy kept for reference only
• heldout/psplib/: downloaded PSPLIB held-out data and generated evaluation artifacts
• heldout/psplib/downloads/: downloaded archives
• heldout/psplib/raw/: extracted raw .sm files
• heldout/psplib/reference/: PSPLIB reference files and bounds
• heldout/psplib/instances/: flattened instance folders generated from the raw archives
• heldout/psplib/manifests/: manifest files produced during conversion
• heldout/psplib/results/: JSONL or other evaluation outputs for held-out PSPLIB runs

Analysis and outputs

• data_analysis/: notebooks for comparisons and experiment writeups
• data_analysis/comparsion.ipynb: quick notebook comparing two J20 runs
• data_analysis/experiment_1.ipynb: heuristic vs. optimal solver analysis notebook
• data_analysis/experiment_2.ipynb: tradeoff analysis notebook across dataset sizes
• results/: generated CSV files, plots, and solver outputs
• project_instructions/: project PDFs and submission guidelines

Heuristic Solver: One Instance

Run command:

python3 scripts/solvers/rcpsp_solver.py data/updated/sm_j10/PSP1.SCH

Expected output (single line of comma-separated start times for real jobs):

0,0,2,5,7,8,13,15,20,22

Optional flags:

• --validate: validate schedule before printing
• --show_makespan: print makespan to stderr
• --output PATH: save solver output to file
• --legacy_output: print one job start_time per line

Example with optional flags:

python3 scripts/solvers/rcpsp_solver.py data/updated/sm_j10/PSP1.SCH --validate --show_makespan

Expected output pattern:

Makespan: 25
0,0,2,5,7,8,13,15,20,22

Heuristic Solver: All Instances Under data/updated

Run command (full evaluation set):

python3 scripts/solvers/eval_fast.py --full

Optional flags:

• --time_limit FLOAT: per-instance heuristic runtime budget
• --seed INT: random seed
• --j10_only: evaluate only data/updated/sm_j10
• --j20_only: evaluate only data/updated/sm_j20

Example with optional flags:

python3 scripts/solvers/eval_fast.py --full --time_limit 2.0 --j10_only

Expected output pattern:

sm_j10/PSP1.SCH             VALID    mk=  25 t=0.03s  OK
sm_j10/PSP2.SCH             VALID    mk=  45 t=0.04s  OK
...
METRIC: total_makespan=XXXXX valid=YYY unsolved=Z invalid=W infeasible=V total=T time=SS.Ss

Exact Solver: One Instance

Run command:

python3 scripts/solvers/optimal_rcpsp.py data/updated/sm_j10/PSP1.SCH --validate

Expected output pattern:

Instance : PSP1.SCH
Status   : OK
Makespan : 25
Jobs     : 10
Nodes    : 22657
Pruned   : 35
Time(s)  : 0.47XX
Schedule : 0,0,2,5,7,8,13,15,20,22

Optional flags:

• --time_limit FLOAT: exact-search timeout per instance (default 60.0 seconds)
• --heuristic_time FLOAT: time used to build initial incumbent
• --progress_seconds FLOAT: print progress every N seconds
• --validate: validate schedule
• --save_dir PATH: save schedule files
• --strict_exit: non-zero exit code if any instance errors out

Example with optional flags:

python3 scripts/solvers/optimal_rcpsp.py data/updated/sm_j20/PSP10.SCH --validate --time_limit 60 --progress_seconds 1

Expected output pattern:

[progress] instance=PSP10.SCH elapsed=1.0s nodes=61440 pruned=6483 best=53
...
Instance : PSP10.SCH
Status   : TIMEOUT
Makespan : 53
Jobs     : 20
Nodes    : NNNNN
Pruned   : MMMM
Time(s)  : 60.0XXX
Schedule : 53,0,12,...

Note: the exact solver stops at 60 seconds by default to prevent computational overload.

Exact Solver: All Instances Under data/updated

Run command:

python3 scripts/solvers/batch_optimal_updated.py --validate

Optional flags:

• --root PATH: root folder to scan recursively (default data/updated)
• --time_limit FLOAT: per-instance exact timeout (default 60.0)
• --heuristic_time FLOAT: incumbent generation time
• --progress_seconds FLOAT: per-instance progress print interval
• --seed INT: base random seed
• --save_dir PATH: save per-instance schedules
• --csv PATH: summary CSV path
• --max_instances INT: run only first N instances (smoke test)

Example with optional flags:

python3 scripts/solvers/batch_optimal_updated.py --time_limit 60 --progress_seconds 2 --validate --csv results/optimal_updated_summary.csv

Expected output pattern:

INSTANCE      STATUS   MK  JOBS  NODES   PRUNED  TIME(s)
------------  -------  --  ----  ------  ------  -------
PSP1.SCH      OK       25  10    22657   35      0.4897
PSP10.SCH     TIMEOUT  53  20    123456  12000   60.0123
...

Solver Comparison: Heuristic vs. Optimal

Generate a comprehensive comparison CSV containing results from both solvers on the full dataset.

Evaluation Setup and Rationale

To evaluate solution quality, we compare our heuristic solver against the exact branch-and-bound solver on the J10 and J20 test sets.

• Heuristic solver timeout: 15s per instance
• Optimal solver timeout: 60s per instance

The exact branch-and-bound solver has factorial worst-case behavior (often described as exploring job-order combinations with complexity on the order of O(n!)), so full exhaustive runs are computationally expensive. Because of runtime constraints, we did not extend the heuristic budget to 30s and instead used 15s for the heuristic and 60s for the optimal baseline.

For each instance, we record:

• heuristic makespan and runtime
• optimal makespan and runtime
• failure cases for both solvers

Failure cases are tracked in the CSV as *_failure_reason fields. In particular, for the optimal solver:

• TIMEOUT means the solver consumed the full 60s budget without finishing proof of optimality
• INFEASIBLE means no feasible schedule found
• other non-empty values indicate invalid schedule or runtime error

Run command:

python3 scripts/solvers/compare_solvers.py --output results/solver_comparison.csv

This script processes all instances under data/updated with:

• Heuristic solver: 1.0 second time limit per instance
• Optimal solver: 60.0 second time limit per instance

Optional flags:

• --root PATH: root folder containing instances (default data/updated)
• --heuristic_time FLOAT: time limit for heuristic solver (default 1.0)
• --optimal_time FLOAT: time limit for optimal solver (default 60.0)
• --output PATH: output CSV path (default results/solver_comparison.csv)
• --seed INT: random seed (default 0)
• --progress: print progress to stderr

Example with custom time limits:

python3 scripts/solvers/compare_solvers.py \
    --heuristic_time 1.0 \
    --optimal_time 60.0 \
    --output results/my_comparison.csv \
    --progress

Output CSV format:

job_instance,num_jobs,heuristic_makespan,heuristic_time,heuristic_failure_reason,optimal_makespan,optimal_time,optimal_failure_reason
PSP1.SCH,10,25,1.0000,,25,0.4759,
PSP10.SCH,10,28,1.0001,,28,0.2002,
PSP100.SCH,10,39,1.0001,,39,0.2838,

Columns:

• job_instance: path to instance file (relative to root)
• num_jobs: number of real jobs (excluding source/sink)
• heuristic_makespan: makespan from heuristic solver, or blank if failed
• heuristic_time: wall-clock time for heuristic solver
• heuristic_failure_reason: empty if successful, otherwise TIMEOUT, INFEASIBLE, INVALID_SCHEDULE, or error message
• optimal_makespan: makespan from exact solver, or blank if failed
• optimal_time: wall-clock time for exact solver
• optimal_failure_reason: empty if successful, otherwise TIMEOUT, INFEASIBLE, INVALID_SCHEDULE, or error message

Use experiment_1.ipynb for Analysis

After generating the comparison CSV, open and run experiment_1.ipynb to reproduce Experiment 1 plots and summary analysis.

Suggested flow:

1. Generate CSV:
2. Open experiment_1.ipynb.
3. Update the input CSV path in the notebook if needed (for example results/my_comparison.csv).
4. Run all cells to produce quality comparison figures and aggregate metrics.

Experiment 2

Trade Off between Runtime and Solution Quality

Goal

Analyse runtime versus solution quality by running the heuristic solver at timeouts 0.1s, 1s, 5s, and 10s, and comparing each to the 15s configuration.

The 15s configuration is used as the baseline in this experiment because it showed strong performance in Experiment 1 (including outperforming the 60s optimal solver under our evaluation setting).

In addition to local j10 and j20 datasets, this experiment includes held-out PSPLIB groups j30, j60, j90, and j120 to evaluate larger problem sizes. For each timeout configuration, we record makespan values for comparison.

Step 1: Generate j10 and j20 benchmark CSVs

Run eval_fast.py once per time budget:

python3 eval_fast.py --full --output --time_limit 0.1
python3 eval_fast.py --full --output --time_limit 1.0
python3 eval_fast.py --full --output --time_limit 5.0
python3 eval_fast.py --full --output --time_limit 10.0
python3 eval_fast.py --full --output --time_limit 15.0

Expected outputs:

• results/j10/0.1.csv, results/j10/1.0.csv, ..., results/j10/15.0.csv
• results/j20/0.1.csv, results/j20/1.0.csv, ..., results/j20/15.0.csv

Step 2: Held-out procedure

1. Download and unpack the external PSPLIB single-mode archives plus their reference files using:

   python3 scripts/psplib/download_psplib.py

2. Flatten the extracted .sm files into per-set folders and generate manifests:

   python3 scripts/psplib/convert_psplib_sm.py --copy

Step 3: Generate j30, j60, j90, j120 benchmark CSVs

Run scripts/psplib/eval_psplib.py per dataset and budget (use --output to write CSV):

python3 scripts/psplib/eval_psplib.py --set j30  --time_limit 0.1   --output
python3 scripts/psplib/eval_psplib.py --set j30  --time_limit 1.0   --output
python3 scripts/psplib/eval_psplib.py --set j30  --time_limit 5.0   --output
python3 scripts/psplib/eval_psplib.py --set j30  --time_limit 10.0  --output
python3 scripts/psplib/eval_psplib.py --set j30  --time_limit 15.0  --output

python3 scripts/psplib/eval_psplib.py --set j60  --time_limit 0.1   --output
python3 scripts/psplib/eval_psplib.py --set j60  --time_limit 1.0   --output
python3 scripts/psplib/eval_psplib.py --set j60  --time_limit 5.0   --output
python3 scripts/psplib/eval_psplib.py --set j60  --time_limit 10.0  --output
python3 scripts/psplib/eval_psplib.py --set j60  --time_limit 15.0  --output

python3 scripts/psplib/eval_psplib.py --set j90  --time_limit 0.1   --output
python3 scripts/psplib/eval_psplib.py --set j90  --time_limit 1.0   --output
python3 scripts/psplib/eval_psplib.py --set j90  --time_limit 5.0   --output
python3 scripts/psplib/eval_psplib.py --set j90  --time_limit 10.0  --output
python3 scripts/psplib/eval_psplib.py --set j90  --time_limit 15.0  --output

python3 scripts/psplib/eval_psplib.py --set j120 --time_limit 0.1   --output
python3 scripts/psplib/eval_psplib.py --set j120 --time_limit 1.0   --output
python3 scripts/psplib/eval_psplib.py --set j120 --time_limit 5.0   --output
python3 scripts/psplib/eval_psplib.py --set j120 --time_limit 10.0  --output
python3 scripts/psplib/eval_psplib.py --set j120 --time_limit 15.0  --output

Expected outputs (examples):

• results/j30/0.1.csv ... results/j30/15.0.csv
• results/j60/0.1.csv ... results/j60/15.0.csv
• results/j90/0.1.csv ... results/j90/15.0.csv
• results/j120/0.1.csv ... results/j120/15.0.csv

Step 4: Run notebook analysis

Open and run all cells in experiment_2.ipynb.

Notebook pipeline:

1. Import plotting/data libraries.
2. Load all CSVs from results/j10, results/j20, results/j30, results/j60, results/j90, results/j120.
3. Build merged comparison tables against each family's 15.0s baseline.
4. Render charts (combined tradeoff line chart, heatmaps, scatter, average-gap-by-budget).
5. Save generated figures.