Job Shop Scheduling Problem and Solution Algorithms: A Review

Cebi C., Atac E., Sahingoz O. K.

11th International Conference on Computing, Communication and Networking Technologies, ICCCNT 2020, Kharagpur, India, 1 - 03 July 2020, (Full Text) identifier

  • Publication Type: Conference Paper / Full Text
  • Doi Number: 10.1109/icccnt49239.2020.9225581
  • City: Kharagpur
  • Country: India
  • Keywords: Ant Colony Optimization, Gantt-Chart, Genetic Algorithm, Job shop scheduling, resource allocation, Simulated Annealing
  • Istanbul Kültür University Affiliated: Yes

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.