Flow Shop Scheduling Problem — A Comparative Study of Optimisation Methods

This repository presents a structured, comparative study of optimisation methods applied to the Flow Shop Scheduling Problem (FSP), a classical NP-hard combinatorial optimisation problem in operations research.

Problem statement. Given $n$ jobs and $m$ machines, where every job must be processed on every machine in the same order $M_1 \to M_2 \to \cdots \to M_m$, find the job sequence that minimises the makespan $C_{max}$ — the time at which the last job finishes on the last machine. With $n!$ possible orderings, the problem is intractable to brute force beyond a small number of jobs and is proven NP-hard for $m \geq 3$ machines.

The repository walks through four complementary optimisation paradigms, each isolated in its own notebook, progressing from provably optimal but expensive exact methods to increasingly scalable approximate methods:

Phase	Notebook	Paradigm	Guarantees
1	branch___bound_FSP.ipynb	Exact methods — Branch & Bound, Dynamic Programming	Provably optimal
2	Heuristics_FSP.ipynb	Constructive & improvement heuristics	Fast, near-optimal
3	Metaheuristics_FSP_neighborhoud.ipynb	Single-solution (trajectory) metaheuristics	Near-optimal, escapes local optima
4	GA_ACO_FSP_Final.ipynb	Population-based metaheuristics	Near-optimal, global exploration

A fifth phase — applying machine learning to optimisation — is developed as a separate project and is not included in this repository.

---

Repository Structure

.
├── branch___bound_FSP.ipynb                 # Phase 1 — Exact methods
├── Heuristics_FSP.ipynb                     # Phase 2 — Heuristics
├── Metaheuristics_FSP_neighborhoud.ipynb    # Phase 3 — Neighborhood metaheuristics
├── GA_ACO_FSP_Final.ipynb                   # Phase 4 — Population-based metaheuristics
└── README.md

Each notebook is self-contained: it loads its own benchmark instances, defines every algorithm it uses, runs the full set of experiments, and produces its own tables and charts. Later phases reuse building blocks (NEH, CDS, the makespan recurrence, TAI/VRF instance parsers) that were introduced and validated in earlier ones, so it is recommended to read the notebooks in order.

---

Phase 1 — Exact Methods (branch___bound_FSP.ipynb)

Establishes the ground truth against which every later phase is measured.

• Branch & Bound (B&B) with two search strategies — Best-First Search (priority queue / min-heap) and Depth-First Search with backtracking (stack) — and four lower bounds of increasing tightness (LB0 → LB3), including the classical Ignall–Schrage bound.
• NEH as a warm-start upper bound to accelerate pruning.
• Brute-force enumeration on a small instance to certify correctness.
• Dynamic Programming via a bitmask shortest-path formulation, with an explicit discussion of its scalability limits.
• A full cross-instance comparison of nodes visited, runtime, and correctness against certified optimal makespans on TAI benchmark instances.

Phase 2 — Heuristics (Heuristics_FSP.ipynb)

Addresses the intractability of exact search through polynomial-time approximate methods, organised into three families:

• Construction heuristics: Johnson (optimal for $m=2$), Gupta, Palmer (slope index), CDS, Weighted CDS, NEH, and Rajendran (Total Flow Time).
• Improvement heuristics (local search): Swap, Insertion, 2-OPT, and Or-OPT, each studied along two axes — neighborhood size (simple vs. extended) and exploration strategy (best vs. first improvement).
• Hybrid strategies: multi-stage pipelines combining a constructive seed with an improvement phase (e.g. NEH + Insertion, Palmer + 2-OPT).
• All methods are benchmarked against the exact B&B solver from Phase 1 (BFS + LB2 + NEH), reported as an optimality gap.

Phase 3 — Neighborhood Metaheuristics (Metaheuristics_FSP_neighborhoud.ipynb)

Introduces single-solution (trajectory) metaheuristics capable of escaping the local optima that plain local search (Phase 2) cannot avoid:

• Tabu Search (TS), Simulated Annealing (SA), Iterated Local Search (ILS), and Variable Neighborhood Search (VNS).
• A controlled 32-combination factorial protocol: 2 initial solutions ($S_0$ = NEH / CDS) × 2 move engines (Insertion / 2-OPT) × 2 exploration strategies (Best / First Improvement) × 4 algorithms.
• Part A — free convergence on Taillard (TAI) instances, measuring gap to the certified lower bound.
• Part B — fixed time budget on VRF instances, measuring efficiency under a CPU cap.
• A synthesis section (radar chart, heatmaps) answering: does a weak initial solution hurt the final result? Which move engine is best? Is exhaustive best-improvement worth its cost?

Phase 4 — Population-Based Metaheuristics (GA_ACO_FSP_Final.ipynb)

Moves from refining a single candidate to evolving an entire population simultaneously:

• Genetic Algorithm (GA): full operator suite — random / NEH-seeded initialisation, four selection strategies (roulette, rank, tournament, elitism), five crossover operators (1-point, 2-point, OX, PMX, CX), five mutation operators (swap, insert, inversion, scramble, shift), three replacement strategies, and an optional memetic (local-search) hybridisation.
• Ant Colony Optimization (ACO) and its elitist variant, the Elitist Ant System (EAS).
• Automated hyperparameter tuning for both algorithms using Optuna (TPE sampler).
• Experiments on Taillard instances of increasing size (20×5, 50×10, 100×10), operator-comparison grids, parameter sensitivity sweeps, and a final head-to-head comparison of GA, ACO, and EAS.

---

Benchmark Instances

The notebooks draw on two standard FSP benchmark families:

• Taillard (TAI) — the standard reference set for makespan minimisation, providing certified upper/lower bounds (and, for the smaller instances used here, known optimal sequences).
• VRF (Vallada, Ruiz & Framinan) — a larger, more recent benchmark set used in Phase 3 for time-constrained evaluation.

Instance files are not redistributed in this repository; each notebook's configuration cell documents the expected file paths and format so they can be downloaded from their original sources and placed accordingly.

---

Requirements

numpy
pandas
matplotlib
optuna
plotly

Install with:

pip install numpy pandas matplotlib optuna plotly

Each notebook can be run independently, provided the relevant benchmark files are placed in the paths indicated in its configuration cell.

---

How to Read This Repository

1. Start with Phase 1 to understand the problem formulation and obtain certified optimal values.
2. Move to Phase 2 to see how much of that optimality can be recovered in polynomial time.
3. Proceed to Phase 3 to see how far a single solution can be pushed with a controlled escape mechanism.
4. Finish with Phase 4 to see what is gained by searching with a population instead of a single trajectory.

Across the four phases, the same evaluation conventions are used throughout — the makespan recurrence $C_{i,j} = p_{\sigma(i),j} + \max(C_{i-1,j}, C_{i,j-1})$ and the optimality gap $\text{Gap}(%) = (C_{max} - C_{ref})/C_{ref} \times 100$ — so that results are directly comparable from one notebook to the next.