Metaheuristic Optimization for Job Shop Scheduling (NP-hard)

Metaheuristic Optimization for Job Shop Scheduling (NP-hard)

This project focuses on solving a complex production scheduling problem in a metal-mechanical manufacturing environment, where multiple jobs must be processed across different machines under strict delivery deadlines.

The objective of the system was to minimize total tardiness in a Job Shop Scheduling Problem (JSP), a combinatorial optimization problem classified as strongly NP-hard. Due to the computational complexity of the problem, traditional exact optimization methods become impractical for real-world scenarios, making heuristic and metaheuristic approaches necessary.

The solution was developed as part of an academic research collaboration and implemented as a computational optimization engine capable of generating efficient production schedules within reasonable computational times.

The proposed methodology integrates several metaheuristic strategies, including:

- GRASP (Greedy Randomized Adaptive Search Procedure)
- Variable Neighborhood Search (VNS)
- Iterated Local Search (ILS)
- Hybrid metaheuristic models combining construction and local search phases

The system evaluates candidate schedules using performance metrics such as:

- Total tardiness reduction
- Convergence time
- Exploration capacity
- Statistical significance of results

A statistical validation framework was implemented using the Tukey test to determine whether differences between metaheuristic approaches were statistically significant, ensuring methodological rigor in the evaluation process.

Experimental results demonstrated that hybrid metaheuristic approaches combining GRASP and VNS consistently achieved superior performance compared to standalone methods, particularly for larger problem instances.

The system was implemented using Python and executed in a controlled computational environment to ensure reproducibility and performance evaluation.

This project represents an applied optimization and algorithm design effort that integrates operations research, algorithm engineering, and industrial decision-support systems.

Programming Language

Python 3.x
Main programming language used for implementing metaheuristic optimization algorithms and experimental simulations in Job Shop Scheduling environments.

Core Python Libraries

pandas

Used for:

Data manipulation
Experimental result storage
Scheduling representation
CSV export
Performance tracking

NumPy

Used for:

Numerical computation
Matrix initialization
Scheduling simulation
Vectorized operations

sqlite3

Used for:

Persistent storage of benchmark instances
Structured data retrieval
Database-driven experimentation

random

Used for:

Stochastic solution generation
GRASP candidate selection
VNS neighborhood exploration

time

Used for:

Runtime control
Convergence measurement
Stopping criteria implementation

math

Used for:

Mathematical computations
Numerical evaluation
Visualization

Matplotlib

Used for:

Gantt chart generation
Makespan visualization
Scheduling performance analysis
System Architecture Style

Scientific Computing Application

Characteristics:

Algorithmic experimentation
Metaheuristic optimization
Iterative simulation
Performance benchmarking


Metaheuristic Algorithms
GRASP
Variable Neighborhood Search (VNS)
Iterated Local Search (ILS)
Combinatorial Optimization
Operations Research
Statistical Analysis
Scheduling Algorithms


The source code is not publicly available. This project is presented as a technical case study describing the system design, methodology, and performance results.

Technology Stack:

Python | Pandas | pip | Sqlite3 | Numpy | time | math | matplotlib | Seaborn

About Team