Job Shop Scheduling Problem and Solution Algorithms: A Review

Abstract

Job Shop Scheduling Problem (JSSP), which aims to schedule several jobs over some machines in which each job has a unique machine route, is one of the NP-hard optimization problems researched over decades for finding optimal sequences over machines. Optimization mainly focused on minimizing the maximum completion time (which is also named as makespan) of whole tasks. According to the size of the problem, JSSP can be defined as Gantt-Chart, Disjunctive Graph, and binary representation forms. This type of scheduling problem is solved with various optimization algorithms such as the Genetic Algorithm, Ant Colony Optimization Algorithm, Particle Swarm Optimization, Tabu Search, or with linear programming models. In this paper, we explain the main characteristics of JSSP and the solution methodologies of this type of problem.