PSO-Based Algorithm for Constrained Flow Shop Scheduling

Introduction

Motivated by its practical relevance in manufacturing systems, this research investigates the two-machine flow shop scheduling problem (FSSP) with a single transport robot and raw material constraints. This problem is a new extension of the FSSP. The objective of this research is to develop an effective scheduling approach that minimizes the makespan while addressing the complexities arising from the movement of jobs between the two machines and the limited availability of raw materials that are supplied from external suppliers at different time moments.

Methodology

To address the computational complexity of the proposed problem, a customized Particle Swarm Optimization (PSO) approach is suggested for its resolution. Since we are in the context of solving a FSSP, we are looking for the permutation of jobs that minimizes the makespan under the constraints imposed by the transport robots and the raw materials' availability. Hence, in order to customize PSO for a discrete problem, we maintain a job-permutation-based encoding scheme. The swarm is initialized randomly, and the particle positions and velocities are updated using crossover and mutation operators borrowed from Genetic Algorithms (GAs) and guided by the personnel and the best global positions, with mutations applied to prevent stagnation. This approach refines the solutions iteratively, optimizing the job scheduling performance under the considered constraints.

Results

The proposed approach was examined on a series of newly developed benchmarks including various configurations of the resource availability and the transportation times between machines. The results show that the approach achieves makespans close to the optimal values reported by a developed ILP model for small instances and reduces the makespans by 5-10% on medium to large instances compared to the standard GAs.

Conclusions

This study proposed a customized PSO approach that addressed the two-machine FSSP with transport robot and raw material constraints. The results demonstrated that the proposed approach is capable of providing a good performance, particularly in challenging scenarios with multiple constraints.