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.
Scheduling is one of the essential activities in industries, especially manufacturing industries. It is important for planning the duration of the job or processes and how it can handle the resources or machines. This planning activity calculates the completion time of the tasks and the relationship between the job activities. Below figure shows the general representation of job shop scheduling.
The benefits of the job shop scheduling are stable planning and production, real-time production feedback, and control of the capabilities. Especially, managers can control their production plants in an optimized way. According to this scheduling, they can arrange their resources, material, machines, and personnel. The job shop scheduling has these advantages :
· Decreasing of completion time/makespan
· Decreasing of the bottleneck resource
· Improving delivery time
· Decreasing of idle time
Because the scheduling has lots of constraints, it is a numerical problem, which is an NP-Hard problem. These restrictions are as followed.
1. Each job has some operations to be processed.
2. Each operation can be processed only one machine at a given time.
3. The processing time of each operation is determined in each machine.
4. All jobs are available at time zero.
5. Each machine can handle at most one operation.
6. All operations must be completed on a set of machines.
Job shop scheduling tries to solve constraints and utilize the resources efficiently. The job shop scheduling problem has 2 main factors: the path of the jobs and processing time of the jobs on each machine. The aim of this problem is to determine the completion time of the jobs on machines in an optimal way.
Types of JSSP
The aim of the scheduling problem is the timing of the jobs within the machines and/or resources. Depending on the capacity of the machines, the processing time of jobs, and due dates of the jobs, there are some constraints of the operations. The aim of this type of problem is “minimizing the total completion time” in an optimal way. It is emphasized that there are 2 types of job shop scheduling problems: static and dynamic.
Static Job Shop Scheduling Problem: All jobs are assumed to be available simultaneously is called static job shop scheduling problem.
Dynamic Job Shop Scheduling Problem: In this problem, jobs are processed at different times at machines because the scheduling of jobs changes at any time. Dynamic job shop scheduling problem is more difficult than static job shop scheduling problem. Because this type of problem includes multiple machines with different sequences. The processing overtime of the jobs can be changed and so that estimations of processes are inaccurate. Dynamic scheduling can be categorized into three scheduling completely reactive scheduling, predictive-reactive scheduling, and robust pro-active scheduling.
In completely reactive scheduling, there is no scheduling for processing order of the jobs which are processed according to real-time dynamic events. The priority of this approach is the dispatching rule. Below figure shows the processing of tasks based on the dispatching rule. The path of the jobs influences this rule. Another research is for dispatching rule is based on the mean job cost and delay of job, which are essential for machine selection rule.
Predictive-reactive scheduling is produced to optimize the performance of jobs without considering some interruptions. If the interruption occurs, the predictive schedule is changed to find the optimal solution. In robust scheduling, the aim is to consider the future interruptions and planning the schedule for minimizing the effect of disruptions. This scheduling is based on the previous experiences and disruptions of tasks, which are shown in below figure. For this planning, researchers focused on minimizing the lateness of the processed and idle time of the processes. This type of problem is generally solved with the Hybrid Genetic Algorithm (HGA).
The flexible job shop scheduling problem is a large version of job shop scheduling where any machine can process any operation of a job from an available machine set. Flexible job shop problem is known as strongly NP-Hard. In this problem, the main goal is to determine machines that will process each operation and order of this process so that makespan makes smaller.
On the contrary to job shop scheduling, in flow shop scheduling, the order of job processes must be the same. Every time, flow shop executes the same order in a sequence, which is represented as in below figure. In this scheduling model, while each machine must process a maximum one job, also each job must be handled by only one machine. Flow shop problems are generally faced in mechanical manufacturing and industrial production areas. Because of the stability and iteration of the flow shop, it is easy to apply this method to robotics. But this method does not have flexibility. So, it is hard to change the continuous production line.
Literature Survey
Today, the job shop scheduling problem is an important issue. Most of the literature research focuses on minimizing the completion time of the jobs and increasing utilization. Because of the size of the problem and constraint, today, most of the studies focus on the usage of heuristics and metaheuristics techniques such as simulated annealing, particle swarm optimization, fuzzy logic, etc. Most of the used techniques are the Genetic Algorithm and Ant Colony Optimization Algorithm.
According to researches, the local search genetic algorithm is efficient for solving job-shop scheduling problems with the multi-agent system. Unless the genetic Algorithm was developed by John Holland in 1975, the usage of genetic algorithms in JSS problems was suggested by Davis. The aim of another GA research is to find the optimal solution for the JSS problem and effect of mutation and crossover stages on the result of this Algorithm. In researches, GA was suggested for scheduling the jobs and rescheduling the new jobs. In this search, 15 benchmark instances used for analysis to minimize the makespan. Another search, Genetic Algorithm was implemented using “Python” language. This search consists of 4 datasets. GA was executed 10 times for each dataset. The size of the datasets is different from each of them according to types of the operations and number of machines. The knowledge model of Ant Colony Optimization model was integrated Knowledge-Based Ant Colony Optimization (KBACO) to solve flexible job shop scheduling problems. Unless generally GA was used, another efficient algorithm is the Hybrid Algorithm. This Algorithm is combining of Genetic Algorithm (GA) and Tabu Search (TS). This Algorithm was proposed with six benchmark instances. According to the result, this Algorithm does not provide an optimal result for all instances.
The research showed that machine learning is essential for solving JSSP with learning-based methods. The aim of these methods is to improve the efficiency of optimization. In this research, a hybrid dynamic preemptive and competitive approach was used to classify the requirements of the system. Another research is a statistical study for the relationship between JSSP and optimal makespan with using the artificial neural network-based heuristic method. To optimize job shop scheduling, it is crucial to classify the job level also. For this reason, this research is used to polynomial-time dynamic programming for the job level. Another job shop scheduling problem is 3 x 3 problem, which is solved by a Genetic Algorithm. The output was obtained at the 100th iteration, and the result is shown with Gantt-Chart.
The aim of the scheduling is minimizing of completion time of all jobs, or another saying is minimizing the makespan. The visualization of the path of the operations and the processing time of each operation are important for analyzing the optimization.
Gantt-Chart Representation
The aim of the scheduling is minimizing of completion time of all jobs, or another saying is minimizing the makespan. The visualization of the path of the operations and the processing time of each operation is important for analyzing the optimization. In this example, there are 3 jobs and 3 machines to schedule them so that it called 3 x 3 JSSP. Table I shows that the routing of jobs and processing time(h) of each operation.
Gantt- Chart is a visualization of the solution of this JSSP. This chart shows that the total completion time of the jobs and usage of the machine’s optimal way. Below figure shows that the Gantt-Chart representation of this dataset. According to this chart, the total completion time of the jobs is 12.
Disjunctive Graph
The job shop scheduling problem can be described as a disjunctive graph. The general formulation of disjunctive representation is G= (V, C U D) where;
· V is a set of nodes in graph representation and it represents the jobs
· C is a set of conjunctive arcs and it represents the path of the operations
· D is a set of disjunctive arcs and it represents the relationship of operations that must be processed on same machine.
According to above dataset, the graph representation is shown in below figure.
Binary Representation
The binary representation was proposed by Nakano and Yamada. This representation is important for genetic operators, such as crossovers. In this disjunctive representation arcs are represented by 0 or 1 according to its direction. Because of the binary direction, scheduling can be represented mn(n-1)/2 binary strength of length. Below figure shows that the representation of the binary representation of above dataset.
This section gives a detailed explanation of datasets that are proposed in some research before and how the datasets are used in algorithms are shown in below table, there are four datasets. The explanations of these datasets are as follows.
· Dataset 1: This dataset has 40 problem cases. These cases categorized into eight different types according to several machines and the number of operations. It is represented as n x m, which n is a job, and m is the machine. An example of this is depicted in below figure.
· Dataset 2: In this dataset, problem cases are with 10 jobs and 10 machines.
· Dataset 3: According to the number of jobs and number of machines, problem instances are 6x6, 10x10 and 20x15.
· Dataset 4: The problem instances are size with 10 x10 and 20 x15.
These numbers have different information. In the 1st line, 10 represents the number of jobs, and 5 represents the number of machines for this dataset. In the 2nd line explains that sequences of the sub-operations on which machine and processing time of each machine to process the sub-operation. This information is “Except first-line jobs are ordered 0 to 9, from 2nd line to 3rd line” and “Each line should be read from left to right. It is the sequence of sub-operations of any job. For instance, for job 6 in the 8th line, 3 69 4 77 1 87 2 87 0 93, is explained the first sub-operation of job 6 is on machine 3 with processing time unit of 69”.
According to the chromosome representation result of the Genetic Algorithm, the job sequences and machine sequences are created. Job sequence is like for Job8:
[ (2, 0, 38), (0, 104, 164), (1, 241, 282), (3, 282, 306), (4, 546, 629)]
This representation shows that Job 8 is processed at timing slot 0 to 38. The machine sequence shows that the job number and time of between processed. For example, for Job 9 is processed time slot 0 to 77-unit time according to this sequence:
[(9, 0, 77), (6, 77, 154), (5, 154, 233), (1, 233, 249), (0, 249, 344), (8,344, 369), (3, 369, 448), (2, 448, 546), (7, 546, 629), (4, 629, 666)]
These results are shown in Gantt-Chart to analyze all jobs and sub-process with makespan clearly. This dataset 1 and the other datasets are compared according to GA at the end of 200th iteration.
JSSP is one of the prevalent optimization problems that not only have an attraction for the operations research field but also for computational intelligence and optimization field. In the literature, there are many approaches to solving this problem.
Genetic Algorithm
The Genetic Algorithm (GA) is a stochastic search and optimization method which is based on Darwin’s Principle of Natural Selection. The underlying basic idea of natural selection is “Select the Best, Discard the Rest”. The genetic Algorithm was first introduced by John Holland at the University of Michigan in 1975. In applications of Genetic Algorithm for job shop scheduling problems, schedules are represented as an individual in the population. These individuals who are schedules have their own fitness values, which is calculated by the objective function. The process works iteratively. This iterative procedure is generation. Each generation composes of individuals. These individuals are the ones who survived and passed from previous generations. Below algorithm represents the general algorithm pseudocode of the Genetic Algorithm.
Generally, the size of the population stays stable between the previous and next generations. As it is seen in below figure, the flowchart of the genetic Algorithm consists of several steps. The process starts with the initialization of the random population. After that, computing fitness, selection, crossover, mutation, local optimization steps are processed. If the termination process is started algorithm returns result, otherwise Algorithm goes back compute fitness step.
Ant Colony Optimization Algorithm
Ant Colony Optimization is a stochastic search technique based on population. The basic idea in an ant colony is to copy the pheromone trails. The pheromone is the communication system for searching food used by real ants. Use of ant colony optimization is also suitable for parallel implementations, especially on CUDA platforms , multi-core implementations, or multi colony based implementations.
In an ant colony, pheromone trails are initialized according to first generated solutions. Each ant begins with a blank sequence and then selects one of the jobs. These processes continue iteratively for all ants until a complete good solution is built. Once all colony constructs their solution, the pheromone trails are updated by applying the global rule to increase the performance quality. These steps can be seen in below algorithm, which shows pseudocode of the ant colony optimization algorithm.
The general structure of the ant colony starts with setting parameters. Then, the base solution is generated, and the pheromone trails are initialized. Until iteration meets the termination condition, each ant construct solution. In a repeated manner, they improve their solutions with local search and update the best solution. After that, the pheromone trails are modified by updating rules, and they are limited with minimum and maximum bounds. In the end, the Algorithm returns the best solution, which is found because of iterations.
Simulated Annealing Algorithm
Simulated annealing is an approach to solve combinatorial and continuous optimization problems. As its introduction, independently by Kirkpatrick, Gelatt, and Vecchi (1983) and Cern (1985), simulated annealing searches the set of all possible solutions for problems. The name of this Algorithm refers to a process in metallurgy. The process is heating the object and cools it slowly. Liquids freeze and crystallize, or metals cool and anneal are key examples of this method.
In the simulated annealing using for job shop scheduling problem, chromosomes generate the schedule. Although chromosome representation can be an integer, binary or real numbers, in the job priority relation sequence, chromosomes are represented by an integer string that stands for job identity. The job priority relation-based representation is chosen for the flexibility of simulated annealing operators and their application. The number of jobs and machine sequences of that job is taken by the fitness function. An integer is assigned to chromosome genes. Then operations start to get a job sequence of genes. After that process, the objective function generates the makespan value of the sequence. Simulated annealing is used to generate optimal chromosomes in the job shop scheduling problem. The pseudocode of this Algorithm is shown in below algorithm.
Fuzzy Logic
Fuzzy logic is a method that is based on the fuzzy set theory, which uses approximate reasoning rather than exact. On the contrary, crispy logic that uses binary logic, the fuzzy logic values are not only 0 or 1. It is not constrained to two truth values, and it results in a range between 0 and 1. Fuzzy set theory is used to solve job shop scheduling problems with uncertain setup and processing times. These approximations are represented by fuzzy numbers.
Tabu Search
Tabu search idea is defined as exploring space of all feasible solutions with sequence move by Glover (1990). This movement between schedules is made with evaluating all candidates and selecting the best. In this process, some moves are called tabu, which means forbidden. This classification represents either trap in local optimum or cycling part of the search. These moves put into Tabu List. Tabu search techniques are applied in job shop scheduling problems with solving mixed-integer programming problems. Below algorithm shows the general Algorithm of tabu search.
As a result, the job shop scheduling problem is an important optimization problem. In literature, there are a lot of different heuristic algorithms used to solve job shop scheduling problems. According to the size of the dataset, not only the representation of this problem but also its solution methodologies can be changed. In the operations research concept, this problem generally is visualized as a Gantt- Chart to see the relationship between the operations and machines clearly. In addition, the disjunctive Graph and binary representations are used.
However, in computational intelligence, there are many evolutionary optimization techniques for this type of problems. In this paper, we focused on the evolutionary solution models for the job shop scheduling optimization problems by investigating the formulization of the problem. The most used technique is seen as the Genetic Algorithm, which has 3 main generator operators: selection, crossover, and mutation. These operators have an important effect on the performance of GA. Moreover, Ant Colony Optimization and Simulated Annealing techniques are used to find an optimal solution. With this work, we try to collect a review about the job shop scheduling problems and its derivatives by giving related formulization and dataset information, which will help the new researchers on this topic for understanding the important design metrics of the problem.
You can find the original IEEE link of this article below.
