Cellular Manufacturing — Graph Theoretic Approach
Full-stack solver for the cellular manufacturing cell formation problem. FastAPI backend parses a CSV machine-part incidence matrix, constructs a bipartite NetworkX graph, runs Louvain community detection, and computes grouping efficiency metrics (exceptional elements, void elements, η).
Role
Full-stack Developer
Team
Solo
Company/Organization
Personal Project
The Problem
Cell formation in cellular manufacturing requires grouping machines and parts into cells to minimise inter-cell material flow — manual assignment on...
Existing academic tools are offline MATLAB scripts or Excel macros with no interactive visualisation — engineers cannot inspect the graph topology or...
Grouping efficiency evaluation (η) requires computing exceptional elements (parts needing machines outside their cell) and void elements (unused...
The bipartite structure of the machine-part graph (two disjoint node sets: machines and parts) requires careful graph construction to ensure Louvain...
No standard CSV format exists for machine-part incidence matrices — the parser needed to handle variable column counts, arbitrary machine/part naming...
The Solution
Built a clean full-stack architecture separating graph construction, clustering, metrics, and API routing into distinct backend modules, with a React...
Backend (Python 3.11 + FastAPI)
graph_builder.py — Parses the uploaded CSV into a pandas DataFrame (first column = part names, remaining columns = machine names). Constructs a...
clustering.py — Applies python-louvain (community.best_partition) to the bipartite graph to detect communities (manufacturing cells). Returns a...
metrics.py — Computes grouping efficiency from the partition and incidence DataFrame:
Exceptional elements: parts whose required machines belong to a different community (inter-cell dependencies).
Void elements: machine-part slots within a cell where the incidence value is 0 (unused capacity inside a cell).
η = 1 − (exceptional + void) / total incidence entries. η = 1.0 means perfect cell formation with no inter-cell movement and no wasted capacity.
schemas.py — Pydantic request/response models: CellFormationResponse containing a list of Cell objects (cell_id, machines[], parts[]) and a...
main.py — FastAPI app with two endpoints: GET / (health check) and POST /upload-matrix (accepts multipart CSV, runs full pipeline, returns...
Frontend (React 18 + Vite + D3.js)
CSVUpload.jsx — File input component with drag-and-drop support. Validates CSV format client-side (checks header row structure), POSTs to...
GraphVisualization.jsx — D3.js force-directed graph rendered in an SVG. Nodes are coloured by community ID (cell assignment). Machine nodes...
App.jsx — Orchestrates upload state, API response, and conditional rendering of upload form vs graph + metrics view.
Design Decisions
Separated graph_builder, clustering, metrics, schemas, and main into distinct modules — each layer is independently testable and the pipeline (parse...
python-louvain (community.best_partition) over METIS, spectral clustering, or manual CFE algorithms — Louvain is well-established for community...
NetworkX bipartite graph over a plain adjacency matrix — NetworkX's bipartite utilities handle the two-node-set structure correctly, and the graph...
pandas for CSV parsing over raw csv module — pandas handles variable column counts, missing values, and header inference cleanly; the incidence...
D3.js force-directed graph over a static chart library (Chart.js, Recharts) — force simulation communicates the graph topology and cell structure...
Single POST /upload-matrix endpoint returning the full pipeline result — avoids client-side orchestration of multiple API calls (build graph, then...
Tradeoffs & Constraints
Louvain community detection is non-deterministic — repeated uploads of the same matrix may produce slightly different cell assignments due to random...
The cell count is determined automatically by Louvain's modularity optimisation — there is no UI control to specify a desired number of cells....
Grouping efficiency η is a single scalar — it does not distinguish between a solution with many small exceptional elements vs one with fewer large...
The force-directed graph layout is non-deterministic across renders — D3 force simulation starts from random initial positions, so the visual layout...
No support for weighted incidence matrices — the current parser treats all 1-entries equally. Real manufacturing data often includes operation times...
Would improve: Add cell count constraint input, implement weighted incidence matrix support, add per-cell efficiency breakdown, use a deterministic...
Outcome & Impact
End-to-end cellular manufacturing cell formation solver: CSV upload → bipartite graph construction → Louvain community detection → grouping...
Backend pipeline: graph_builder.py (bipartite NetworkX graph from incidence matrix), clustering.py (Louvain community detection), metrics.py...
Grouping efficiency η = 1 − (exceptional + void) / total — computed per upload with breakdown of exceptional elements (inter-cell part dependencies)...
D3.js force-directed graph with machine nodes (squares) and part nodes (circles) colour-coded by community/cell ID, hover tooltips, and a co-rendered...
GitHub Actions CI/CD pipeline running backend (Python 3.11 + pip install) and frontend (Node 20 + Vite build) checks on every push and PR to main.
Tech Stack
Backend: Python 3.11, FastAPI, Uvicorn
Graph: NetworkX (bipartite graph construction), python-louvain (Louvain community detection)
Data: pandas (CSV parsing and incidence matrix handling), Pydantic (request/response schemas)
Frontend: React 18, Vite, D3.js (force-directed graph visualisation)
CI/CD: GitHub Actions (Python 3.11 backend + Node 20 frontend jobs)
Automation: Makefile (install, run, stop, backend, frontend, test, status)