Flow Shop Scheduling Problem (FSSP) Optimization Using Simulated annealing Algorithm

Project Overview:

The Flow Shop Scheduling Problem (FSSP) is a classic optimization problem in operations research, used to model manufacturing and production planning scenarios. The objective is to schedule a set of jobs on a series of machines to minimize the total completion time, known as the makespan. This project focused on the permutation variant, where jobs are processed in a fixed sequence on each machine.

Problem Definition:

Jobs: 5

Machines: 3

Objective: Minimize the total completion time (makespan)

Constraints:

Processing operations cannot be interrupted.

Respect minimum and maximum machine idle times.

Start each operation only after the previous one is completed on the same job and machine.

Approach:

Developed a mathematical formulation of the FSSP.

Analyzed the computational complexity of the problem.

Implemented a solution using Gantt charts to visualize schedules.

Applied a metaheuristic algorithm (Simulated Annealing) to find the optimal job sequence.

Technical Implementation:

Language: Python

Libraries: NumPy, random, Matplotlib

Algorithm: Simulated Annealing

Visualization: Gantt chart for schedule representation

Key Results:

Optimal Sequence: [[4, 2, 1, 5, 3], [4, 2, 1, 5, 3], [2, 1, 5, 3, 4]]

Best Makespan: 18.0

Gantt Chart Visualization: Displayed the optimal schedule graphically.

Conclusion:

This project demonstrates expertise in operations research, algorithm development, and optimization techniques. The successful application of Simulated Annealing to solve the FSSP highlights the ability to handle complex scheduling problems efficiently.