Using Simulated Annealing in Job-Shop problem-solving

7 min readFeb 20, 2019

The aim of this post is to explain the implementation and usage of Simulated Annealing heuristic algorithm in Job-Shop problem. Further below we will describe the studied problem and the solving algorithm. We will also summarize the results and their execution time as well as compare these with the results obtained while solving the problem using the GRASP algorithm(Greedy randomized adaptive search procedure).

Problem description

The Job-shop scheduling problem is an optimization problem in which tasks are assigned to resources at particular times.

As input data, we are given a file, consisting of n jobs of varying processing times(tasks), which need to be scheduled on m machines. Using this information we need to find the shortest scheduling length possible, that will allow executing these tasks in the correct order.

The important detail is that these operations are atomic, which means that every assigned task has to be executed from the beginning to the end. The bottom line is that a single machine can not execute operations simultaneously.

It is easily noticed that this problem can get very complicated really fast, which resulted in many different approaches. In this post, we will use the Simulated Annealing method.

Algorithm Description

Simulated annealing searching for a maximum — hill climbing (source)

Simulated Annealing is a heuristic algorithm that searches through the space of alternative problem solutions to find the ones with the best results. The algorithm derives its name from the fact that his behaviour resembles annealing in metallurgy. This heuristics approximates the global optimum for a given optimization problem.

For each transition (step), the algorithm takes into account a certain neighbourhood sn of the current state sc and then decides on the basis of a new result and probability whether it should be in the sc state or go to the sn state. This step is repeated until the system has reached the required state or until the time limit has been reached.

This probability, and hence — how often the algorithm agrees to change the state to sn depends on the temperature, which is the parameter of our algorithm. The formula for this probability is: P= exp (- (sn - so) / T)

Implementing the algorithm

We present our data in the form of a disjunction graph (acyclic and directed), where each vertex (except initial and final) is an operation (task). Afterwards, we create cliques for operations seeking access to the same machines:

Example of a disjunction graph with created cliques (2.1)

Now the whole problem comes down to giving such a turn to the edges that connect the conflict vertices so that the graph still has no cycles. How we arrange these phrases determines the quality of the solution.

In our algorithm, we start with the warming mode, which means we randomly search for the best result, and then after reaching a certain threshold, switch to the cooling mode, where as a result of temperature reduction our model selectively applies changes to the graph in order to improve the result achieved in heating mode.(3.1)

Algorithm Steps

The algorithm was defined as follows (3.2) :

Start with the WARMING mode (temperature increases) and set the temperature to the given initial_temperature(one of the parameters)
Fill in the disjunction graph with values read from the input file, whereas each vertex (except the initial and final) is an operation (task). Then for operations that compete for access to the same machine, create an acyclic clique.
Pick random edge present in the critical path of the graph that does not combine subsequent operations and does not start at the beginning node, nor end at the end node. In other words, find the edge that connects the two conflict vertices.
Reverse the direction of the chosen edge. If by doing so we do not create a cycle in the graph, continue. Otherwise, restore the graph to its previous state and retry step 3.
If the inversion of the chosen edge did not increase the cmax value (the longest path from the beginning to the end of the graph, i.e. the length of the scheduling), and therefore the result is the same or better — accept the change of edge direction. Otherwise, calculate P(T)= exp (-(sn-so)/T). If our likelihood P is greater than the random value random(0,1), then accept the change in edge direction. Otherwise, discard the change and restore the graph to its previous state.
(If in WARMING mode:) If we reject the change after accepting n iterations, where n >10% of the cooling_lengthparameter (this means that our algorithm is too “fussy” in the heating phase), increase the temperature by the product of alpha_warmingand initial_temperature.
(If in WARMING mode:) If the percentage of the accepted changes against the last n changes is greater than the parameter warming_treshold, proceed to cooling mode and start counting the number of accepted changes again.
(If in COOLING mode:) If the number of accepted changes is greater than the parameter cooling_length, reduce the temperature by (temperature*(1-alpha_cooling)) and start counting the number of accepted changes again.
If the number of changes in the graph without improving the result exceeds the set value or the time has been exceeded (5 minutes), end the program. Otherwise, go back to step 3.

Tuning the Parameters

The algorithm uses the values of these 6 parameters:

initial_temperature– the starting temperature at which the algorithm starts,
alpha_warming– the percentage that determines how quickly the temperature increases in the warming mode,
alpha_cooling– the percentage that determines how quickly the temperature decreases in cooling mode,
cooling_length– the value which determines after how many accepted changes in the graph will we reduce the temperature
warming_threshold– the percentage which determines how many of the last moves must be accepted in order to increase the temperature in the warming mode
max_moves_without_improvement– the value which determines, after how many changes without improving the result, will we end the algorithm.

To tune the parameters, and thus adjust their values so that the cost function is as small as possible, the Grid Search method is used, which finds the best parameter values by manually passing through the values from the selected range for each parameter and then choosing those for which the best result was achieved.

This method is seemingly ineffective, but it offers a quite easy and convenient method of tuning. You can also perform parallel tuning on several computers and even processor cores, which significantly reduces the tuning time.

Grid search allows tuning for various types of data, not only for the Job-Shop problem, which allows us to state that this is a universal solution for choosing the parameters of our algorithm.

Results

The algorithm can read and solve Taillard and Orlib instances (1.1 and 1.2). We tested the performance of the algorithm on 10 Taillard instances.

In the case of solving the tai20 — tai30 instance for all jobs (20 jobs), the algorithm stops working when the time limit is reached — 5 minutes because the algorithm still does not achieve the best potential result when the time limit is reached.

The result is the longest path from the beginning to the end of the graph, i.e. the length of the scheduling (2.3).

The results achieved by the Simulated Annealing algorithm for these instances:

The result of the program was compared to the result of the lower bound and upper bound given in the data file, as well as the result obtained when solving the problem using GRASP algorithm.

The results of the program are not the best but close to the upper bound, which is satisfying. Our algorithm solves the problem much slower than GRASP because usually after 5 minutes it still does not achieve the potentially shortest possible length of the scheduling, whereas GRASP achieves results in less than 1 second. A cause for this is GRASP being a greedy algorithm.

Conclusions

The Simulated Annealing algorithm is pretty effective but not the fastest method of solving the Jobshop problem. It is worth noting that the algorithm ends not only when it exceeds the time limit, but also when it does not notice an improvement in the result after a specified number of changes in the graph.

This solution can be especially useful when you want to get a better result, regardless of the time spent on finding a solution. If necessary, we can also manipulate the number of maximum changes in the graph without improving the result, in order to obtain shorter solving time.

Feel free to check out my code for the algorithm discussed in this article:

https://github.com/Uxell/SimulatedAnnealing_JobShop