# Job Shop Scheduling Problem Optimization by Means of Graph-Based Algorithm
## 2 Job Shop Scheduling Problem  
The job shop scheduling problem (JSSP) is about allocating limited resources to a variety of tasks for the purpose of obtaining optimal scheduling solutions. These optimized scheduling solutions are important for achieving an efficient and orderly production process [4]. The JSSP is one of the most well-known problems in the fields of production management and combinatorial optimization. The classical n-by-m JSSP can be described as the flow shop problem generalization or the open shop problem specification: scheduling n jobs on m machines with the objective of minimizing the scheduled completion time (makespan) of all jobs. Each of n jobs consists of several operations on m specified machines, which need an uninterrupted processing time of a given length. Operations of the same job can be performed only on one machine at a time and each job must be processed on each machine exactly once [5].  
In order to increase production efficiency, reduce cost and/or improve product quality, efficient methods for solving the JSSP are required. Additionally, the JSSP is acknowledged as one of the most challenging NP-hard problems--and no algorithms that can solve the JSSP consistently, even on small scale problems, are known to exist [5].  
Nowadays, with the usage of metaheuristic algorithms, new ways of obtaining better results than were possible with classical methods (such as greedy or dispatching heuristic algorithms) have emerged. These metaheuristic algorithms are widely used because of their flexibility and global optimization capabilities [4]. Algorithms for the solution of the JSSP include population-based metaheuristic ones, including particle swarm optimization (detailed description in [6; 7]), genetic algorithms, artificial immune systems and their hybrids (see [8; 9; 10]), construction and improvement heuristics including taboo search (described in [11; 12; 13]) and simulated annealing (described in [14; 15]). Also, heuristic methods can be used for large-scale problems. These include dispatching priority rules (see [16; 17; 18]), the shifting bottleneck approach (detailed description in [19; 20; 21]) and Lagrangian relaxation (see [22; 23; 24]) [5].  
However, each of these methods comes with their own drawback. Simulated annealing has the tendency to generate poor designs that have a high chance of missing local minima; its convergence is also quite slow. The taboo search uses the serial search method and is low-efficiency. Particle swarm optimization has the tendency to become trapped in local minima. Exact techniques, such as branch and bound (described in [25; 26]) and dynamic programming (see [27; 28]) can be used to solve only modest-scale problems, because of the complexity of the JSSP [5].  
As the genetic algorithm can search efficiently through large search spaces and does not explicitly require additional information about the objective function in order to be optimized, it has been applied to many combinatorial problems, including scheduling [29]. Moreover, its architecture makes it well suited for parallel computation. On the other hand, the GA considers only one new solution at a time [4].