Job Shop Optimization Through Multiple Independent Particle Swarms

Abstract

This study examines the optimization of the Job Shop Problem (JSP) by a search space division scheme and use of the meta-heuristic method of Particle Swarm Optimization (PSO) to solve it. The JSP is a well known combinatorial problem from the field of Deterministic Scheduling. It is considered the one of the hardest in the class of NP-Hard problems. The PSO algorithm is a meta-heuristic optimization method modeled after the behavior of a flock of birds. "Particles" are initialized in the search space of a problem by assigning them a position, which represents a solution to the objective function, and a velocity. They "fly" through the search space with out direct control, but are given both a personal component and a social component of the best positions found. The proposed method uses this meta-heuristic to solve the JSP by assigning each machine in a JSP an independent swarm of particles.