Job Shop Scheduling Problem and Solution Algorithms: A Review - Çebi, Ceren; Ataç, Enes; ŞAHİNGÖZ, ÖZGÜR KORAY (Institute of Electrical and Electronics Engineers Inc., 2020)
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.
2020 11th International Conference on Computing, Communication and Networking Technologies, ICCCNT 2020
Keywords: Job Shop Scheduling; Gantt-Chart; Resource Allocation; Genetic Algorithm; Ant Colony Optimization; Simulated Annealing