Job Sequencing Optimization using Genetic Algorithm & Simulated Annealing

This project implements and benchmarks the Job Sequencing Problem using two metaheuristic optimization algorithms:

• Genetic Algorithm (GA)
• Simulated Annealing (SA)

The algorithms are implemented in both Python and C++ to study runtime performance, scalability, and solution quality differences across languages and algorithms.

---

Overview

This project explores and compares evolutionary and stochastic optimization techniques to solve the Job Sequencing Problem, where the goal is to determine an optimal job order that minimizes total completion time, lateness, or cost.

The application provides an intuitive graphical interface built with Tkinter, allowing users to input jobs, visualize scheduling results, and compare the performance of Genetic Algorithm and Simulated Annealing in real-time.

---

Key Features

Optimization Algorithms

• Simulated Annealing (SA)

  • Designed to escape local optima by probabilistically accepting worse solutions early on.
  • Produces higher-quality schedules compared to baseline heuristics.
  • Offers temperature-based control for exploration vs. exploitation trade-off.

• Genetic Algorithm (GA)

  • Employs custom chromosome encoding for representing job sequences.
  • Implements tailored crossover and mutation operators optimized for scheduling problems.
  • Achieves faster convergence and superior global exploration compared to greedy approaches.

---

Tech Stack

Component	Technology
Languages	Python, C++
Algorithms	Genetic Algorithm, Simulated Annealing
Data Handling	CSV
Benchmarking	Python subprocess, C++ chrono
Analysis	Pure Python (no external libraries)

---

Implementation Highlights

• Implemented Simulated Annealing-based scheduling, enabling escape from local optima and improving solution quality over traditional heuristics.

• Applied Genetic Algorithm with:

  • Custom chromosome encoding for job sequences.
  • Innovative crossover and mutation strategies.
  • Strong balance between exploration and exploitation.

• Comparative analysis shows GA tends to find global optima faster, while SA offers strong local refinement capabilities.

Parameter Settings

Algorithm	Key Parameters
Genetic Algorithm	Population = N, Generations = 1000, Mutation = swap
Simulated Annealing	T0 = 10000, Cooling Rate = 0.99, Tmin = 1

Benchmarking Framework

The project includes a full benchmarking pipeline:

• Synthetic dataset generator (datasets/generate_test.py)
• Automated runners for:
  • Python (python/runner.py)
  • C++ (cpp/runner.cpp)
• Results stored in CSV format:
  • results/python_results.csv
  • results/cpp_results.csv
• Comparison and analysis scripts (results/compare.py)

Project Structure

├── cpp/
│   ├── genetic_algorithm.cpp
│   ├── simulated_annealing.cpp
│   ├── runner.cpp
│   └── compiled binaries
├── python/
│   ├── genetic_algorithm.py
│   ├── simulated_annealing.py
│   ├── runner.py
│   └── Job.py
├── datasets/
│   ├── generate_test.py
│   └── jobs_*.csv
├── results/
│   ├── python_results.csv
│   ├── cpp_results.csv
│   └── compare.py
└── README.md

---

Running Experiments

Everything is put together in a bash script:

chmod +x run_all.sh
.\run_all.sh

1 Generate Datasets

python datasets/generate_test.py

---

2 Compile C++ Algorithms

cd cpp
g++ genetic_algorithm.cpp -O2 -o genetic_algorithm
g++ simulated_annealing.cpp -O2 -o simulated_annealing
g++ runner.cpp -O2 -o runner

---

3 Run Benchmarks

Python

cd python
python runner.py

C++

cd cpp
./runner

---

4 Compare Results

cd results

---

PYTHON vs C++ BENCHMARK TABLE

Algo	N	Py Time(s)	Cpp Time(s)	Speedup	Py Cost	Cpp Cost	Cost Diff
Genetic Algorithm	50	0.103172	0.020544	5.02	61804	62466	-662
Genetic Algorithm	100	0.214701	0.055349	3.88	406334	408252	-1918
Genetic Algorithm	500	2.693362	0.361522	7.45	16144610	15793170	351440
Genetic Algorithm	1000	10.339104	1.843790	5.61	69555680	70696186	-1140506
Genetic Algorithm	5000	278.730233	34.838100	8.00	1873107197	1869843581	3263616
Simulated Annealing	50	0.070282	0.005370	13.09	121893	76380	45513
Simulated Annealing	100	0.122606	0.004281	28.64	628376	567988	60388
Simulated Annealing	500	0.737110	0.027021	27.28	19865766	19805083	60683
Simulated Annealing	1000	2.095279	0.055030	38.08	79928133	79859914	68219
Simulated Annealing	5000	32.945668	0.391417	84.17	1956433803	1956363867	69936